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 = p1p.dot(p1p2);
const crossProd = p1p.cross(p1p2);
return dotProd >= 0
&& dotProd <= p1p2.square() + 1e-1
&& Math.abs(crossProd) < 1e-3;
}
``````