Subject: CGAL users discussion list
List archive
- From: Camille Wormser <>
- To:
- Subject: Nice convexity test bug
- Date: Wed, 07 Mar 2007 13:21:45 +0100
Thanks to the previous discussion about the convexity test algorithm, I realized the current implementation is buggy: if you consider the following points
p0 (0, 0);
p1 (1, 0);
p2 (.2, .2);
p3 (0, 1);
P0 P1 P2 P3 is not a convex polygon. So, whichever definition of convexity you imagine, you would expect P0 P1 P2 P2 P3 is not a convex polygon either. Stricto sensu, it is not a simple polygon, since two non-incident edges share a vertex (because of the zero length edge P2 P2), however, since the convexity test is designed especially to handle the non-simple case, this is not an excuse.
Consider the attached program, which shows that CGAL returns different results: P0 P1 P2 P2 P3 is convex...
--
Camille
#include <CGAL/basic.h> #include <iostream> #include <CGAL/Exact_predicates_inexact_constructions_kernel.h> #include <CGAL/Polygon_2.h> typedef CGAL::Exact_predicates_inexact_constructions_kernel K; typedef CGAL::Polygon_2<K> P; int main () { K::Point_2 p0 (0, 0); K::Point_2 p1 (1, 0); K::Point_2 p2 (.2, .2); K::Point_2 p3 (0, 1); P p; p.push_back (p0); p.push_back (p1); p.push_back (p2); p.push_back (p2); p.push_back (p3); std::cout << p.is_convex() << std::endl; P q; q.push_back (p0); q.push_back (p1); q.push_back (p2); q.push_back (p3); std::cout << q.is_convex() << std::endl; }
- Nice convexity test bug, Camille Wormser, 03/07/2007
Archive powered by MHonArc 2.6.16.