Implementing Seperating Axis Theorem

Question

I'm trying to implement the Seperating Axis Theorem by following this article I found on MDN. Unfortunately, I'm not too geometry savvy and I wasn't able to find any good, simple implementation examples around the internet. I've tried to search for the specific concepts that the article mentions, but I'm not sure that I'm on the right track and I've got several doubts about this.

Here's what I did so far:

export class Point {
    
    constructor(x, y) {
        
        this.x = x;
        this.y = y;
    }
    
    rotate(pivot, angle) {
            
        let s = Math.sin(angle);
        let c = Math.cos(angle);
        
        let p = new Point(this.x - pivot.x, this.y - pivot.y);
                
        return new Point((p.x * c - p.y * s) + pivot.x, (p.x * s + p.y * c) + pivot.y);
    }
    
    compare(point) {
        
        // todo
    }
}

import { Point } from "./Point.js";

export class Line {
    
    constructor(p1, p2) {
        
        this.p1 = p1;
        this.p2 = p2;
    }
    
    getSlope() {
        
        return (this.p2.y - this.p1.y) / (this.p2.x - this.p1.x);
    }
    
    getNormal() {
        
        let dx = this.p2.x - this.p1.x;
        let dy = this.p2.y - this.p1.y;
        
        return new Line(new Point(-dy, dx), new Point(dy, -dx));
    }
    
    getYIntercept() {
        
        return this.p1.y - this.getSlope() * this.p1.x;
    }
    
    getPointProjection(point) {
        
        let slope = this.getSlope();
        let yIntercept = this.getYIntercept();
        
        let slope2 = -1 / slope;
        let yIntercept2 = point.y - slope2 * point.x;
        
        let nx = (yIntercept2 - yIntercept) / (slope - slope2);
        
        return new Point(nx, (slope2 * nx) + yIntercept);
    }
}

import { Point } from "./Point.js";
import { Line } from "./Line.js";

export class Polygon {
    
    constructor(...points) {
            
        this.points = points;
    }
    
    overlaps(polygon) {
        
        let side = new Line(this.points[0], this.points[1]);
        
        let axis = side.getNormal();
        
        function findMinAndMaxProjectedPoints(polygon) {
            
            polygon.points.forEach(point => {
            
                let projection = axis.getPointProjection(point);
            
                
            });
        }
        

    }
}

1. Did I implement the various formulas correctly?
2. How should I "keep track of the highest and lowest values" for each polygon? How am I supposed to determine which projected points are the lowest and which are the highest?
3. How do I check for gaps between the highest and lowest projected point of the two polygons?

Answer 1

1. Did I implement the various formulas correctly?

No.

• A normal should be a single direction vector with one x value and one y value, not a line segment joining two points.

• Point projection where you divide by slope will behave badly for horizontal lines where the slope goes to zero.

• Your overlap test checks only one side of one polygon.

2. How should I "keep track of the highest and lowest values" for each polygon? How am I supposed to determine which projected points are the lowest and which are the highest?

Use a vector dot product. Given a vector along your candidate axis axis = (axis.x, axis.y), the projection of a point along that vector is proportional to:

Dot(point, axis) = point.x * axis.x + point.y * axis.y

Technically this gives us a true distance only when the axis is a "unit vector" with length 1 (ie. Dot(axis, axis) = 1), and will give us an exaggerated/scaled result if the axis has a different length. But to check for overlaps this scale factor doesn't matter, so you can save yourself the work of normalizing the vector and just tolerate it.

The result of a dot product is a scalar (a number, not a vector). So we can find the greatest/least with a min/max function.

let least = inf
let greatest = -inf

polygon.points.forEach(point => {            
    let projection = Dot(point, normal)
    least = min(least,  projection)
    greatest = max(greatest, projection)
});

3. How do I check for gaps between the highest and lowest projected point of the two polygons?

After you've computed your least and greatest values as above for each polygon along the same separation vector, you just compare the numbers. If there's a gap, then it means the least value from one polygon is still greater than the greatest value from the other polygon.

if (polygon1.least > polygon2.greatest or polygon1.greatest < polygon2.least)