Selfintersecting

[pshtif]

Does it offer a triangulation or decomposition for selfintersecting polygons?

Since I don't want to reinvent a wheel I am looking for a triangulation library to be used for my framework Genome2D, so far surprisingly Nape has the most robust triangulation/decomposition utilities but its too linked together to be feasible to target Flash SWC with the whole Nape library.

[azrafe7]

Nope. Sorry Peter, but the lib only works with simple polys (and I cannot point you to anything haxe/as3 that does it - with a nice license -, although I'd be curious to know it if you happen to find one).

Does Nape also handle selfintersecting shapes?

[azrafe7]

Oh... Actually there's something called as3polyclip and an haxe port of that (MIT licensed) that seem to support selfintersecting shapes and shapes with holes.

Haven't tested them but maybe you can drop a line to PolyClip's maintainer to get more info.

[pshtif]

Nape definitely can triangulate intersecting, I just don't remember if directly or it needs some kind of poly simplification/decomposition called first. But there is definitely a way how to get triangles from selfintersecting poly using nape methods.

PolyClip doesn't seem to have triangulation at all its just for boolean operations on polygons, but looks useful too.

[azrafe7]

Yeah, I realized that PolyClip does only bool operations on polys after I posted, got caught off by the name.

I'm investigating what algos are out there to convert a selfintersecting polygon into multiple non selfintersecting ones, and if it's feasible to use them and then apply triangulation/decomposition to the results.

[azrafe7]

Hey @pshtif , just to let you know, I've recently found out about libtess2 by @memononen via as3GameGears and ported the js version to Haxe.

From https://github.com/memononen/tess2.js readme:

The tess2.js library performs polygon boolean operations and tesselation to triangles and convex polygons. It is a port of libtess2, which in turn is a cleaned up version of the stock GLU tesselator. The original code was written by Eric Veach in 1994. The greatest thing about tess2.js is that it handles all kinds of input like self-intersecting polygons or any number of holes and contours.

I've also added to hxGeomAlgo a ConnectedComponentsLabeler that can work as a MarchingSquares that also detects holes. I'm still working/testing/refactoring/documenting both, but the combo seems quite promising. Take a look at the original tess2.js demo (rehosted over here).

[pshtif]

Thanks man going to check it out as I had prior work that had to be done first. Looks great from the demo the performance also seems better than Napes from a quick look.

[azrafe7]

My port of tess2.js is much probably slower than the original one, but should have no problem in handling selfintersecting polys as the original.

I've also added an experimental Delaunay refinement ported from a PR in the C repo of libtess2 in case you're interested (https://github.com/memononen/libtess2/pull/7). As of now the count of tris is somewhat high (the same of the default triangulation), but their shape is considerably better.