CGAL users discussion list

[Iosif Pinelis <>]

 wrote:

> Le Mer 7 mars 2007 20:15, Iosif Pinelis a écrit :
>  
>
> > Come on Camille. Your own example, from your latest post, shows that
> > CGAL does not give the right answer.
> >    
>
> In my message, I explicitely mention
> "in the case of non flat polygons, we can assume that three successive
> vertices are never aligned (by removing unnecessary vertices)"
> This is where CGAL fails.
>  
It does appear that the test fails there. That is why I said in my 
comment to this part of your proof that one should be careful even at 
such a comparatively minor point, depending especially on how exactly 
the test deals with such degeneracies (I still don't know all the 
details of how the CGAL test works).

> As for the rest of your message, I think it has nothing to do on such a
> mailing-list.
>  
I don't understand this. On a "micro level", I was analyzing the proof 
that you posted on the list, that is, the proof of the CGAL test (and 
the later additions to/clarifications of the proof), and I used the same 
convenient point-by-point format as you use in your messages.

On a "macro level", the point that I was trying to make -- in general 
and for polygon convexity in particular -- is that we do need (i) exact 
definitions of the geometric traits tested, (ii) exact and complete 
descriptions of the corresponding tests, and (iii) rigorous and complete 
proofs that each test exactly verifies the definition of the 
corresponding tested notion. Related to this was the suggestion that it 
would be great to have for each given notion (such as polygon convexity, 
say) a standard, generally accepted definition -- rather than a 
disparate variety of them with no mutual relations established or 
proved. I believe that the papers at http://arxiv.org/abs/cs.CG/0609141 
and http://arxiv.org/abs/cs.CG/0701045 (and ones referenced therein) 
serve these goals as far as the polygon convexity is concerned. In 
particular, I think that the methods and/or results especially of the 
second one of these two papers can be used to rigorously prove the CGAL 
convexity test. Since convexity tests are also used in other problems, 
both 2D and higher-dimensional, I would expect this to be of interest to 
this forum. 
--
Iosif Pinelis, Professor
Department of Mathematical Sciences
Michigan Technological University
Houghton, MI 49931 USA