Re: [Jts-topo-suite-user] Triangulating polygons?

[Martin D. <mb...@re...>]

JTS 1.11 provides Delaunay triangulation and Constrained Delaunay 
triangulation.  In theory you could use CDT to triangulate a polygon, 
but I would probably look at more direct and simpler algorithms first.  
There is a very simple algorithm called Ear-Clipping (aka Ear Cutting or 
Ear Slicing).  This page provides Java code for this:

http://www-cgrl.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/applet1.html

Also have a look at this page - it provides an applet and a paper 
explaining the technique.

http://www.sfu.ca/~cjs/triangulation/

Seems like this would be a nice thing to add to JTS.  Anyone able to 
contribute a patch?

Martin




Ian Turton wrote:
> I have a need for the triangulation of a polygon. These are real world
> polygons so I'm guessing they are not going to be simple or convex.
> Does JTS provide this functionality or does any one have some code I
> can use?
>
> I'm actually calculating the moment of inertia for the polygons so if
> you can point to a better way I'd love to see that too. All the
> references I've found say to go with triangles and summation (and
> leave triangulation as an exercise for the reader).
>
> Thanks
> Ian
>
>   

-- 
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022