Sep 6, 2020

Overlapping Polygons

It is an interesting problem. As I said in an earlier post, there is already a widespread implementation for when the polygons are convex. The question is when dealing with general polygons. In my thinking, which might be wrong, I'm thinking that two polygons overlap when:

  1. One point from one polygon is inside the other polygon
  2. Any line from the two polygons intersect a line from the other polygon at a point that is not an endpoint on both line segments.
  3. The polygons are identical.

This logic seems sound to me. Time will show if these conditions are enough.

Code of the Day

The added requirements does add new requirements on existing methods. For example containsPoint now need a version that checks if the intersect is at the ends or not.

   * Returns if the given point exists on this line segment or not.
   * @param p
  containsPoint(p: Point): boolean {
    const p1p = p.minus(this.p1);
    const p1p2 = this.p2.minus(this.p1);
    const dotProd =;
    const crossProd = p1p.cross(p1p2);
    return dotProd >= 0
    && dotProd <= p1p2.square() + 1e-1
    && Math.abs(crossProd) < 1e-3;