Skip to Content.
Sympa Menu

cgal-discuss - Nice convexity test bug

Subject: CGAL users discussion list

List archive

Nice convexity test bug


Chronological Thread 
  • 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.

Top of Page