[abetusk]

I've only skimmed the article so their solution seems like a totally valid way to do polygon intersections for their purposes, but for people that want to do this in a more rigorous way, there's something called the Vatti clipping algorithm which does boolean operations on arbitrary 2D polygons (in polynomial time).

To find polygon intersections, one can do a boolean "intersect" operation to see if the resulting operation has any results. If so, the polygons intersect. If not, then they're disjoint.

Angus Johnson has created ClipperLib [1] which implements Vatti's algorithm and is available in a variety of languages, including C++, with ports to Javascript by others [2].

CGAL [3] can do polygon clipping but, from my own experience, ClipperLib is about 400 times faster.

[0] https://en.wikipedia.org/wiki/Vatti_clipping_algorithm

[1] http://www.angusj.com/clipper2/Docs/Overview.htm

[2] https://github.com/junmer/clipper-lib

[3] https://www.cgal.org/

[vonadz]

Thanks for posting this! I'll look into testing ClipperLib as well. If it's 400x faster, that would be great.