int polygon simplicity

a small library that precisely (when coordinates are integers) determines whether a polygon (or a path) on euclid plane is simple, i.e. doesn't self-intersect.

uses the hamos-hoey algorithm, runs in O(nlogn), but with (hopefully) THE bullet-proof comparator function for the sweepline segment set that i can't find correct elsewhere in open-source codes.

also with a helper function that tries to fix small local self-intersections in piecewise path fragments, useful when dealing with hand-drawn contours.

to install:

npm install a

to use:

const {tryFixPathFrags, isSimplePolygon}=require('int-polygon-simplicity')

// pass in (arrays of) points that look like {x:1,y:2}.

// returns true when no self-intersection detected.
// any duplicate vertex, "needle" and self-contact counts as non-simple.
const b=isSimplePolygon(Pn,isClosed)

// tries to fix problems within 16 points. won't fail, but not guaranteed to fix everything either.
// modifies newFrag, lastFrag in-place, only deleting points that causes small loops.
// thr first and last point passed in always remains.
// newFrag="frags[n-1]", lastFrag="frags[n-2]", lastLastPoint="frags[n-3].last"
// pass in null when one doesn't exist.
// you should call it with ("frags[0]", "frags[n-1]", "frags[n-2].last")
// when the user tries to finish/close the path since it could create new trouble.
// specially, when only one frag exists, pass in ("frags[0]", "frags[0]", null) as a special case.
tryFixPathFrags(newFrag,lastFrag,lastLastPoint)

to play with it: an interactive int-polygon-simplicity-debugger