Re: [Jts-topo-suite-user] Triangulating polygons?
Brought to you by:
dr_jts
Menu
▾
▴
Re: [Jts-topo-suite-user] Triangulating polygons?
|
From: Martin D. <mb...@re...> - 2010-04-27 15:59:56
|
I also notice that in the "4-square-holes" result there is at least one triangle pair which could be improved by edge flipping (the top one). Martin Davis wrote: > Correction - that should be "use the CGAlgorithms.computeOrientation() > predicate". > > Also, is it necessary to removing collinear points too often (or maybe > at all). I notice that in the "4-square-holes" figure, there is at > least one internal "triangle" which actually has 4 sides! (in the > bottom right). I think this must be due to the collinear point removal > code. It seems to me that if you use the robust computeOrientation > predicate, you can just avoid creating triangles which have all 3 points > collinear. > > Martin Davis wrote: > >> One thing I notice is that you're using the covers predicate. This >> should be perfectly robust, but it's always something I'm a little bit >> hesitant to use as a core part of another algorithm. It's also much >> slower than desirable. It's better to achieve the same result via a >> direct test. (I can't provide an substitute algorithm right now, but >> will try to soon). >> >> Also, your test for collinear points isn't going to be robust, since it >> uses mathematical computation and is thus subject to round-off error. >> Better to use the CGAlgorithms.isCCW predicate, which is robust. >> >> All I can suggest right now... will try and do more testing later. >> >> Michael Bedward wrote: >> >> >>> Hi Ian, Martin, >>> >>> I just did a bit more testing of yesterday's code (EarClipping3.java). >>> The following polygon is handled successfully... >>> >>> "POLYGON ((0 0, 0 200, 200 200, 200 0, 0 0), " + >>> "(20 20, 20 40, 40 40, 40 20, 20 20), " + >>> "(20 160, 20 180, 40 180, 40 160, 20 160), " + >>> "(160 160, 160 180, 180 180, 180 160, 160 160), " + >>> "(90 90, 90 110, 110 110, 110 90, 90 90) )"); >>> >>> Here is an image of the result... >>> http://imagebin.org/94614 >>> >>> However, if I add an extra hole near the lower right corner... >>> "(160 20, 160 40, 180 40, 180 20, 160 20), " >>> >>> The algorithm gets stuck. >>> >>> Any ideas ? >>> >>> Michael >>> >>> ------------------------------------------------------------------------------ >>> _______________________________________________ >>> Jts-topo-suite-user mailing list >>> Jts...@li... >>> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user >>> >>> >>> >>> >> ------------------------------------------------------------------------------ >> _______________________________________________ >> Jts-topo-suite-user mailing list >> Jts...@li... >> https://lists.sourceforge.net/lists/listinfo/jts-topo-suite-user >> >> >> > > -- Martin Davis Senior Technical Architect Refractions Research, Inc. (250) 383-3022 |