Geometry Boost List: Re: [geometry] Incorrect results from bg::equals (problem with closure and collect_vectors?)

Subject: Re: [geometry] Incorrect results from bg::equals (problem with closure and collect_vectors?)
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2017-04-09 10:05:56

Ch'gans wrote:
> On 9 April 2017 at 12:05, Adam Wulkiewicz <adam.wulkiewicz_at_[hidden]> wrote:
>> Ch'gans Via Geometry wrote:
>>> My custom ring type is defined with an 'open' closure.
>>>
>>> When i try to compare 2 geometrically equivalent ring and box,
>>> bg::equals return false.
>>> While investigating using the debugger, i discovered that the call to
>>> geometry::collect_vectors() returns 4 points for a box, but only 3
>>> points for a ring, so my 2 geometries can never be equal.
>>>
>>> In my case, collect_vectors is dispatched to range_collect_vectors,
>>> and by the look of it range_collect_vectors doesn't care about the
>>> geometry object (and it's closure), since it sees only point
>>> (iterator) range.
> [...]
>>> Am i missing something in my custom geometry trait adaptation? is it a
>>> bug in BG, or a known limitation?
>> It is a bug. I pushed a fix to develop:
>> https://github.com/boostorg/geometry/commit/657a5c80902edc9640a06571c2762a5dee591067
>> I'll try to release it with Boost 1.64.
> Thanks for the fix, this was quick! ;)
> After adding the QVM dependency, and using Geometry devel branch, I
> have removed a couple of expected failure from my test suite, great!

I'm glad to hear that.

> But unfortunately i still have some left: Comparison for geometry
> equivalence of a box and a ring.
>
> The problem is again in collect_vectors, the specialisation for bbox
> always collect the points by following the clockwise direction, if
> your have counterclockwise rings then equals(ring, box) will always
> return false due to different directions.
>
> Not sure what is the best way to fix this, any thoughts?

2 solutions come to mind:

1. Always gather segments/vectors in the same order, like this (pushed 
to develop):
https://github.com/boostorg/geometry/commit/e3ac044400748e23d7a5a708b47bb8fef9b14758

2. In the constructor of collected_vector use lexicographically smaller 
point as the origin point, so always store point-order-invariant 
direction. It'd require to modify these constructors:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/algorithms/detail/equals/collect_vectors.hpp#L89
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/algorithms/detail/equals/collect_vectors.hpp#L179

I've choosen the first solution because it's simpler. I also expect it 
to be faster but haven't done performance tests.

Adam