Triangulation of polygons with holes: poly2tri class

I am always been very interested in a solid script to handle triangulation of polygons with holes, because it’s the first step to the generation of a physics destructible terrain with Box2D, something I always wanted to do.

Some time ago I published my attempt to triangulate a polygon but my script did not handle holes.

Now I found a 2D constrained Delaunay triangulation library called poly2tri originally written in C++ and Java but already ported in AS3 which seems to work with holes.

At the moment it needs some changes to perfectly fit to my needs, but it’s a great start to achieve my destructible terrain.

Look at this script:

We have a square as big as the stage, divided into two triangles. Try to click with the mouse inside to create a square hole and see the computed triangulation.

There is no limit to the amount of holes you can do, as long as a hole:

1) is entirely inside the big square

2) does not overlap any other hole

These two points are the ones I am working on now, meanwhile here is the script I made:

As you can see, it’s just a matter of addRectangle and addHole methods provided by VisiblePolygon class.

Download the source code and give it a try.

  • hmm… new ideeas come to mind with this . thx.

  • Ivan

    Error: Sweep.edgeEvent: Collinear not supported!
    at org.poly2tri::Sweep/edgeEventByPoints()
    at org.poly2tri::Sweep/edgeEventByPoints()
    at org.poly2tri::Sweep/edgeEventByEdge()
    at org.poly2tri::Sweep/sweepPoints()
    at org.poly2tri::Sweep/triangulate()
    at org.poly2tri::VisiblePolygon/_triangulateOnce()
    at org.poly2tri::VisiblePolygon/get triangles()
    at org.poly2tri::VisiblePolygon/drawShape()
    at Main/doHole()