Incorrect results from bg::equals (problem with closure and collect_vectors?)

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Incorrect results from bg::equals (problem with closure and collect_vectors?)

Boost Geometry mailing list
Hi there,

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.

I found a similar thread back from 2014, but it actually deals with a
different problem, see
http://boost-geometry.203548.n3.nabble.com/Possible-bug-in-boost-geometry-equals-td4025819.html.

And there is this bug report that seems to be equivalent to my use-case:
https://svn.boost.org/trac/boost/ticket/11899

Am i missing something in my custom geometry trait adaptation? is it a
bug in BG, or a known limitation?

Could someone shed some light on this? Any point-out to example,
documentation or archives would be welcome too.

If this is the same bug as #11899, could the fix be as simple as
making range_collect_vectors aware of the closure of the ring, or
maybe simply add a specialisation for rings?

Thanks,
Chris
_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Incorrect results from bg::equals (problem with closure and collect_vectors?)

Boost Geometry mailing list
Hi,

Ch'gans Via Geometry wrote:
Hi there,

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.

I found a similar thread back from 2014, but it actually deals with a
different problem, see
http://boost-geometry.203548.n3.nabble.com/Possible-bug-in-boost-geometry-equals-td4025819.html.

Right, it was something different:
https://github.com/boostorg/geometry/commit/7e3d0571f93b768f091da238f86e123e138d0c19

And there is this bug report that seems to be equivalent to my use-case:
https://svn.boost.org/trac/boost/ticket/11899

Thanks for the heads up. The component of this bug is set wrongly to 'polygon' so we missed it.

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.

Could someone shed some light on this? Any point-out to example,
documentation or archives would be welcome too.

If this is the same bug as #11899, could the fix be as simple as
making range_collect_vectors aware of the closure of the ring, or
maybe simply add a specialisation for rings?

Yes it probably is. You could check the bugfix mentioned above.
As a workaround probably relate() could be used but there probably would be some difference in performance.

Regards,
Adam

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Incorrect results from bg::equals (problem with closure and collect_vectors?)

Boost Geometry mailing list
On 9 April 2017 at 12:05, Adam Wulkiewicz <[hidden email]> wrote:

> Hi,
>
> Ch'gans Via Geometry wrote:
>>
>> Hi there,
>>
>> 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.

Hi Adam,

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!

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?

Chris
_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Incorrect results from bg::equals (problem with closure and collect_vectors?)

Boost Geometry mailing list
Ch'gans wrote:
On 9 April 2017 at 12:05, Adam Wulkiewicz [hidden email] 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

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Incorrect results from bg::equals (problem with closure and collect_vectors?)

Boost Geometry mailing list
> On 9 April 2017 at 22:05, Adam Wulkiewicz <[hidden email]> wrote:
>> Ch'gans wrote:

[...]

>> 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.

Hi Adam,

Thanks again for the quick fix! Another couple of expected failures gone! ;)
Thanks as well for sharing your other ideas on how this can be done,
it's always good to discover new things and get familiar with the
inners of BG.

I have a last bg::equals test marked as expected failure, but i'm not
sure about that one:
If you construct a box with their two corners swapped, eg:
Box(Point(2, 2), Point(1, 1)), then bg::equals with the normalised
version of the box returns false. That is:
bg::equals(Box(Point(2, 2), Point(1, 1)), Box(Point(1, 1), Point(2,
2))) = false;

Conceptually, they are geometrically equals, as boxes don't have a
concept of orientation like ring do.

My Box class doesn't automatically correct for this since the user
might want to create such a box for whatever reason.

Do you think that this is a bug, or is it expected or officially
undefined, as the box is degenerated?
I would like to highlight that bg::area() on such a box, returns the
correct area (positive).
I vaguely remember seeing code in BG that check for equality using
area (may well be ring/polygons), obviously it's not the case for the
box.

Chris

>
> Adam
_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Incorrect results from bg::equals (problem with closure and collect_vectors?)

Boost Geometry mailing list
Hi Chris,

Ch'gans wrote:

I have a last bg::equals test marked as expected failure, but i'm not
sure about that one:
If you construct a box with their two corners swapped, eg:
Box(Point(2, 2), Point(1, 1)), then bg::equals with the normalised
version of the box returns false. That is:
bg::equals(Box(Point(2, 2), Point(1, 1)), Box(Point(1, 1), Point(2,
2))) = false;

Conceptually, they are geometrically equals, as boxes don't have a
concept of orientation like ring do.

Boost.Geometry requires that the coordinates of the min corner of a box has to be lesser or equal to the coordinates of max corner. This is true for all coordinate systems. E.g. in geographic a Box overlapping the antimeridian could contain the points: min_corner: (179, 0), max_corner: (181, 1), even though for other geometries these coordinates would be outside the range of validity.
See also: http://www.opengeospatial.org/standards/sfa page 16 Envelope

So if you're creating Boxes by yourself (not with bg::envelope() function) then I'd suggest to always make sure they're normalized.

My Box class doesn't automatically correct for this since the user
might want to create such a box for whatever reason.

Do you think that this is a bug, or is it expected or officially
undefined, as the box is degenerated?

Boxes are equal-compared by equal-comparison of min and max coordinates.
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/algorithms/equals.hpp#L92
Relational operations for Boxes has to be as quick as possible. Boxes having max < min are considered to be invalid so I think this case shouldn't be handled. Unless you have a good reason for this?

If anything I'd consider to replace math::equals with more strict but faster operator== comparison, both to speed it up and to make it consistent with other relational operations for Boxes which checks coordinates with operators like <= or <, so without math::equals. This could potentially speed-up the rtree::remove().

FYI, Boxes shouldn't be treated as Polygons. In cartesian coordinate system they indeed correspond to each other. But in non-cartesian coordinate systems they're different, e.g. in spherical CS horizontal segments of a Box are fragments of parallels but segments of a polygon are fragments of great circles. BG currently allows to perform various operations for Box/Polygon and treats Boxes as Polygons, but that's incorrect IMO.

I would like to highlight that bg::area() on such a box, returns the
correct area (positive).

Yes, that's possible. Some operations may return valid output even for invalid input but that an exception, not a rule.

I vaguely remember seeing code in BG that check for equality using
area (may well be ring/polygons), obviously it's not the case for the
box.

Yes, it's a check to quickly reject polygons before analysing segments.
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/algorithms/equals.hpp#L199
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/algorithms/equals.hpp#L139

Adam

P.S. I have permission to release the fix with Boost 1.64.

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Loading...