Re: [Jts-topo-suite-user] Triangulating polygons?
Brought to you by:
dr_jts
From: Michael B. <mic...@gm...> - 2010-04-25 04:52:23
|
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 |