Re: [Jts-topo-suite-user] Triangulating polygons?
Brought to you by:
dr_jts
From: Ian T. <ij...@ps...> - 2010-04-23 18:48:22
|
On Fri, Apr 23, 2010 at 2:44 PM, Martin Davis <mtn...@te...> wrote: > Thanks, Michael. I'll try this out ASAP. > > For handling holes I can think of two approaches (neither of which is > trivial, but maybe not too difficult either) > > 1. When selecting an ear to clip, ensure that the clipping line does not > intersect any holes in the polygon. (Although - as I write this I can > think of a simple counterexample - if a hole is *almost* as large as the > shell itself, this won't be able to find a non-intersecting clipping line > > 2. (This one I think is foolproof, but harder). Turn the > shel-with-holes into a self-intersecting-shell, by adding lines which > connect each hole to the outer shell. Then triangulate the resulting > shell as per normal (the self-intersection should not affect the > triangulation algorithm. The tricky part is finding "good" lines to > connect each hole. Possibly an exhaustive approach of trying to connect > each hole vertex to each shell vertex and choosing the shortest line > segment will work. Process each hole sequentially - there can be > situations where a hole connects to a (former) hole. > One option I found is to convert the polygon to trapezoids and then triangulate the trapezoids http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.5877, There is C code at http://www.cs.unc.edu/~dm/CODE/GEM/chapter.html that claims to handle holes. Ian -- Ian Turton |