Triangulation of polygons with holes: poly2tri class

Emanuele Feronato Actionscript 3, Flash

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.

From null to full HTML5 cross platform game

I will take you by hand from the bare bones of JavaScript programming through the creation of a full cross platform HTML5 game, with detailed explainations and source code.

If you don't know where to start, then From null to full HTML5 cross platform game is the book for you.

Comments 2

  1. 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()

Leave a Reply

Your email address will not be published. Required fields are marked *