CGAL users discussion list

[Andreas Fabri <>]

Roger House wrote:
> Is there a CGAL function which can compare two polygons and determine if 
> they are the same even when the order of the vertices may differ? 

The order cannot differ that much. There can be a cyclic shift and it
can be clockwise or counterclockwise oriented.


The cyclic shift is already taken care of by CGAL. Let me copy paste
from the manual.

template <class Traits, class Container1, class Container2>
bool    Polygon_2<Traits,Container1> p1 == Polygon_2<Traits,Container2> p2
                Test for equality: two polygons are equal iff there exists a 
cyclic
                permutation of the vertices of p2 such that they are equal to 
the
                vertices of p1. Note that the template argument Container of 
p1 and p2
                may be different.


So it resumes to first check their size, then orient them both the same
way

if(p1.orientation() != p2.orientation()){
  p2.reverse_orientation();
}



> Is 
> there a similar function which compares polygons with holes and which 
> can figure out if two polygons are the same even if the holes appear in 
> a different order?

Finding the lexicographically smallest vertex of each polygon should
help to pair them up.


best regards,

andreas

> Roger House