Boost logo

Geometry :

Subject: [ggl] Point/Box in Box Test (Border Cases - 3D)
From: Barend Gehrels (barend)
Date: 2011-07-18 02:31:28

On 10-7-2011 15:54, Barend Gehrels wrote:
> Hi Frank, List,
> On 7-7-2011 12:03, Frank Glinka wrote:
>> Amendment to my previous mail:
>> It seems the 'within_code' function returns a different result than
>> intersects or my custom implementation of coveredBy although I
>> wouldn't have expected this.
>> Probably even worse: 'within' now has a different behavior compared
>> to the previous version (before you moved the within_code code).
>> This happens with the micro benchmark and a batch_size of 100000000
>> with 10 iterations. Strange - I have no ad hoc idea yet.
> This is indeed worrying. Can it be related to floating point precision?
> Furthermore, for your information, I've been busy with it. I can
> reproduce your benchmarks and I started with a solution. The
> within_code will (probably) disappear. Instead, there will be some
> specific strategies for implementation of either >= and <= for
> covered_by, or > and < for within, such that they can be implemented
> optimally and therefore will have the same speed as the original
> solution.
> This has some more influence on the design and I will not finish it
> this weekend, but next weekend should be feasable.

OK, ready now. I have:
- removed the detail::within_code
- extent the strategy approach for point/box and box/box
- they now use a flexible system, where either > < or >= <= can be used
- added a covered_by algorithm, conform PostGIS/Oracle, meaning "within
or on the border"
- for point/box and box/box this is all implemented N-dimensional (as it
- added a agnostic point/box strategy which is usable for spherical and
geographic coordinate systems
- they are also usable for within and covered_by
- some smaller changes.

The strategy approach is useful, e.g. for spherical, a point-in-box
could mean: "really in the spherical box", so on the left side of all
(counter clockwise) sides, or "just in the extent", so within the
coordinates specified by that box. The default strategy is the first
one. The second one is similar to the cartesian (dimension agnostic)
strategy, but it would have to take the dateline into account (so this
second described strategy is not yet there - but it could be useful once).

Can you verify your benchmarks on performance and the
behaviour/correctness you reported?

Regards, Barend

Geometry list run by mateusz at