Geometry Boost List: [geometry] Possible bug in boost::geometry::equals ?

Subject: [geometry] Possible bug in boost::geometry::equals ?
From: yohann.benedic_at_[hidden]
Date: 2014-01-21 05:47:07

Hi there,

To summarize, if two polygons are built spatially equal, then boost::geometry::equals sometimes fails to recognize it.
I hope this post is not a duplicate. I googled around and did not find anything.

Here is an example, tested with 1.54
void test ( void ) {
    typedef boost::geometry::model::d2::point_xy<double> boostPoint;
    typedef boost::geometry::model::polygon< boostPoint > boostPolygon;

    // creating a first polygon: a square with a square-shaped hole in the middle.
    boostPolygon p1;
    boost::geometry::append(p1, boost::geometry::make<boostPoint>(0,0));
    boost::geometry::append(p1, boost::geometry::make<boostPoint>(0,3));
    boost::geometry::append(p1, boost::geometry::make<boostPoint>(3,3));
    boost::geometry::append(p1, boost::geometry::make<boostPoint>(3,0));
    boost::geometry::interior_rings(p1).resize(1);
    boost::geometry::append(p1, boost::geometry::make<boostPoint>(1,1),0); //A
    boost::geometry::append(p1, boost::geometry::make<boostPoint>(2,1),0); //B
    boost::geometry::append(p1, boost::geometry::make<boostPoint>(2,2),0); //C
    boost::geometry::append(p1, boost::geometry::make<boostPoint>(1,2),0); //D
    boost::geometry::correct(p1);

    // creating another polygon : notice it is spatially the same one as p1
    // the difference is that the hole is described starting from another point : CDAB instead of ABCD
    boostPolygon p2;
    boost::geometry::append(p2, boost::geometry::make<boostPoint>(0,0));
    boost::geometry::append(p2, boost::geometry::make<boostPoint>(0,3));
    boost::geometry::append(p2, boost::geometry::make<boostPoint>(3,3));
    boost::geometry::append(p2, boost::geometry::make<boostPoint>(3,0));
    boost::geometry::interior_rings(p2).resize(1);
    boost::geometry::append(p2, boost::geometry::make<boostPoint>(2,2),0); //C
    boost::geometry::append(p2, boost::geometry::make<boostPoint>(1,2),0); //D
    boost::geometry::append(p2, boost::geometry::make<boostPoint>(1,1),0); //A
    boost::geometry::append(p2, boost::geometry::make<boostPoint>(2,1),0); //B
    boost::geometry::correct(p2);

    // the following statement fails.
    assert(boost::geometry::equals(p1,p2));
}

>From my investigations, the problem comes from the building of the "point-direction" vectors, which end up having different sizes. At some point in the algorithm, the direction of the last point is compared to the one of the first point and the latter is removed if equal. Here it happens between the last point of the interior ring and the first of the exterior ring : on p1 they are different but on p2, hence the difference of size that causes equals to fail.

Thanks for your time.

_________________________________________________________________________________________________________________________

Ce message et ses pieces jointes peuvent contenir des informations confidentielles ou privilegiees et ne doivent donc
pas etre diffuses, exploites ou copies sans autorisation. Si vous avez recu ce message par erreur, veuillez le signaler
a l'expediteur et le detruire ainsi que les pieces jointes. Les messages electroniques etant susceptibles d'alteration,
Orange decline toute responsabilite si ce message a ete altere, deforme ou falsifie. Merci.

This message and its attachments may contain confidential or privileged information that may be protected by law;
they should not be distributed, used or copied without authorisation.
If you have received this email in error, please notify the sender and delete this message and its attachments.
As emails may be altered, Orange is not liable for messages that have been modified, changed or falsified.
Thank you.