Re: [Jts-topo-suite-user] Triangulating polygons?
Brought to you by:
dr_jts
From: Martin D. <mtn...@te...> - 2010-04-25 05:07:37
|
You might want to try normalizing the orientation of the shell and hole rings, so that they are compatible (that is, so that they all have the interior on the same side). In the polygon WKT below both the shell and the hole are CCW. In a normalized polygon the shell is CW and the holes are CCW. (There is a method Geometry.normalize() that does this - but be aware that it modifies the geometry it is called on, rather than creating a new one). I think this might solve the problem of the loop in the last shell ring created, which is what is preventing the next triangle from being found. Michael Bedward wrote: > On 25 April 2010 02:33, Martin Davis wrote: > >> I can't visualize a situation where no ear can be found. Can you post >> an example? >> >> > > A house-shaped polygon with a diamond hole... > POLYGON((0 0, 10 0, 10 5, 5 10, 0 5, 0 0), (5 3, 7 5, 5 7, 3 5, 5 3)) > > My algorithm first forms this self-intersecting shell... > {0 0, 10 0, 10 5, 7 5, 5 7, 3 5, 5 3, 7 5, 10 5, 5 10, 0 5, 0 0} > > It then finds three ears... > ear 1 = {0 0, 10 0, 10 5, 0 0} > shell = {0 0, 10 5, 7 5, 5 7, 3 5, 5 3, 7 5, 10 5, 5 10, 0 5, 0 0} > > ear2 = {10 5, 7 5, 5 7, 10 5} > shell = {0 0, 10 5, 5 7, 3 5, 5 3, 7 5, 10 5, 5 10, 0 5, 0 0} > > ear3 = {5 3, 7 5, 10 5, 5 3} > shell = {0 0, 10 5, 5 7, 3 5, 5 3, 10 5, 5 10, 0 5, 0 0} > > But now, scanning this coord array for ears {i, i+1, i+2} fails to > find another ear because all lines from i : i+2 cross the (original) > hole. The next ear I'd like it to find would be {5 7, 10 5, 5 10, 5 7} > but that would require a change to the order of the shell coords. > > It's a nice puzzle :-) Any thoughts ? > > Michael > > ------------------------------------------------------------------------------ > _______________________________________________ > Jts-topo-suite-user mailing list > Jts...@li... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > |