Efficient detection of polygon intersections in Javascript with sweeplines

I needed to be able to detect complex polygon intersections in the browser, so I spent some time exploring and implementing the Bentley–Ottmann sweep line algorithm for detecting crossings in a set of line segments in Javascript. It uses an AVL binary tree and event queue to run in O((n + k) log n) time.  The code on Github is developed to be run on node.js, but it can be easily adapted to run in a browser.

Sweepline Repository on github

Advertisements