Re: [Jts-topo-suite-user] Triangulating polygons?

[Martin D. <mb...@re...>]

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