Re: [Jts-topo-suite-user] Triangulating polygons?
Brought to you by:
dr_jts
From: Martin D. <mtn...@te...> - 2010-04-24 16:37:58
|
By the way, I can definitely visualize situations where the "choose shortest segment to connect hole" algorithm won't work. Eg the following: POLYGON ((50 440, 50 50, 510 50, 510 440, 280 240, 50 440), (105 230, 443 228, 106 208, 105 230), (280 210, 260 190, 310 190, 280 210)) That's ok, though. There always has to be *some* sequence of line segments which validly connects all holes to the shell or to another hole. So if the heuristic of shortest segment fails, I think you just have to delay connecting that hole to the last. Michael Bedward wrote: > On 24 April 2010 14:44, Martin Davis <mtn...@te...> wrote: > >> Ok, great. Let us know how it goes. >> >> > > Made some progress and then got stuck. I'll describe what I've done so > far and then the next idea. > > Get shell coords list > For each hole list: > Get hole coords > Find closest hole - shell vertices > Insert hole coords into shell coords list as: > {shell coords} {join} {hole coords} {join} {remaining shell coords} > > I'm working with a list of coordinates because the self-intersecting > shell is no longer a valid polygon so I can't use the difference > method to subtract ears. That's OK because removing an ear just > involves removing one coordinate from the shell. > > It works well up to a point but then ends up in configurations where > no valid ear can be found because of the order of coordinates being > tested. > > Perhaps the method of joining holes to shell can be improved ? > > In the meantime I'm falling back to a dumber algorithm: > > 1. triangulate ignoring holes > 2. for each ear found in step 1, if it overlaps holes, subtract them > and re-triangulate > > Michael > > ------------------------------------------------------------------------------ > _______________________________________________ > Jts-topo-suite-user mailing list > Jts...@li... > https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user > > |