Shamos and Hoey Intersection Algorithm (Naiive)

README.md

Shamos and Hoey Polygon Intersection Algorithm

This is my very horrific attempt to implement the Shamos and Hoey intersection algorithm. The algorithm is defined in the paper Geometric Intersection Problems (1976).

Thoughts

• For the love of god, don't re-sort the array each time you insert. There's gotta be an O(n) way to do it???
• Verify the algorithm more (I don't actually know if it's correct)
• Next, implement the Bently and Ottmann optimizations

point.ts

export type Point = {
    x: number;
    y: number;
}

export type Segment = {
    p1: Point;
    p2: Point;
}

export function point(x: number, y: number) :Point {
    return {
        x, 
        y,
    };
}

export function segment(x1: number, y1: number, x2: number, y2: number): Segment {
    return {
        p1: {
            x: x1,
            y: y1,
        },
        p2: {
            x: x2,
            y: y2,
        }
    };
}

subdivision.ts

import { Point, Segment } from "./point";

function ccw(p1: Point, p2: Point, p3: Point) {
    return (p3.y - p1.y) * (p2.x - p1.x) > (p2.y - p1.y) * (p3.x - p1.x);
}

function intersects(left: Segment, right: Segment) {
    const A = left.p1;
    const B = left.p2;
    const C = right.p1;
    const D = right.p2;
    return ccw(A,C,D) != ccw(B,C,D) && ccw(A,B,C) != ccw(A,B,D);
}

type Intersection = {
    left: Segment;
    right: Segment;
}

type PointExtended = {
    point: Point;
    segment: Segment;
}

class Tree {
    nodes: Segment[] = [];
    insert(segment: Segment) {
        this.nodes.push(segment);
        // TODO: Sort on insert or something...
        this.nodes.sort((a,b) => {
            return b.p1.y - a.p1.y;
        });
    }

    siblings(segment: Segment): [Segment | null, Segment | null] {

        for (let i = 0; i < this.nodes.length; i++) {
            if (this.nodes[i] === segment) {
                return [
                    this.nodes[i-1],
                    this.nodes[i+1]
                ];
            }
        }

        return [null ,null];
    }


    delete(segment: Segment) {
        for (let i = 0; i < this.nodes.length; i++) {
            if (this.nodes[i] === segment) {
                this.nodes.splice(i, 1);
                break;
            }
        }
    }
    

}

/** A class used to subdivide a self-intersecting polygon. */
export class Subdivision {
    /** A list of points with a pointer to the segment it comes from */
    points: PointExtended[];

    constructor(segments: Segment[]) {
        this.points = [];

        for (const segment of segments) {
            this.points.push({
                point: segment.p1,
                segment,
            }, {
                point: segment.p2,
                segment,
            });
        }

        // Sort the endpoints lexicographically by X axis
        this.points.sort((a,b) => {
            return b.point.x - a.point.x;
        });
    }

    intersections(): Intersection[] {
        const ret: Intersection[] = [];
        const tree = new Tree();

        for (let i = 0; i < this.points.length; i++) {
            const P = this.points[i];
            const isLeft = P.point === P.segment.p1;
            
            if (isLeft) {
                tree.insert(P.segment);
            }

            const [A, B] = tree.siblings(P.segment);

            // Check for intersections
            if (A && isLeft && intersects(A, P.segment)) {
                ret.push({ left: A, right: P.segment });
            } else if (B && isLeft && intersects(B, P.segment)) {
                ret.push({ left: B, right: P.segment });
            } else if (A && B && !isLeft && intersects(A, B)) {
                ret.push({ left: A, right: B });
            }

            if (!isLeft) {
                tree.delete(P.segment);
            }
        }

        return ret;
    }

    /**
     * Build a set of polygons by subdividing the original shape.
     * 
     * @returns The list of simplified and corrected polygons.
     */
    build(): Polygon[] {
        const ret: Polygon[] = [];        
        
        return ret;
    }

}