0
\$\begingroup\$

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?
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$
  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.

  1. 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)
});
  1. 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)
\$\endgroup\$
2
  • \$\begingroup\$ Thank you for this extensive answer, it was very useful. I've just have a doubt left: how do I calculate the normal vector of a side given the two endpoints? I just can't figure that part out. \$\endgroup\$
    – Gian
    Nov 12, 2020 at 12:37
  • \$\begingroup\$ Vector2 alongLine = new Vector2(line.p2.x - line.p1.x, line.p2.y - line.p1.y); Vector2 perpendicular = new Vector2(-alongLine.y, alongLine.x); The first vector points along the line, from p1 to p1 (you could usefully think of a line as being a start point and an offset vector like this). The second vector flips x and y and negates one (arbitrarily) to point perpendicular (or "normal to") the line. You can optionally normalize this vector if you need it to be length 1. I didn't call it a "normal" here since I often reserve that name in my code for unit normals. \$\endgroup\$
    – DMGregory
    Nov 12, 2020 at 12:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .