Geometry Boost List: Re: [geometry] linestring overlap and hash function for linestring

From: Giorgino R (giorginor21_at_[hidden])
Date: 2020-06-18 14:47:53

Hi Tinko,

Many thanks for your reply along with your valuable suggestions, I
appreciate it.

With respect to hashing, that's the reason (comparing doubles) why I asked
in my first email whether the hashing could be somehow carried out with an
invariant field that potentially two spatially equal linestrings could
have. I am not fully knowledgeable whether such a field exists/stands.
Probably, hashing experts (from boost::hash) could have an idea. I guess
it is like someone wanted to store two-dimensional arrays in an
unordered_set (arrays with inverse order of rows from one another should be
equal). I am thinking that there might be a mathematical way to produce a
quantified invariant by iterating over the rows of the 2D matrix.  In any
case, I will explore further based on your suggestions on hashing, as well.

Now, as far as the tolerance is concerned, I have tried in the past to
define  BOOST_GEOMETRY_NO_ROBUSTNESS macro; however, I didn't see any
difference. I can't use integers for coordinate types, I am afraid. I ve
been using boost::geometry ( I really like Boost::geometry, its design and
flexibility ) for generating multi-dimensional design spaces with scaled
coordinates (0 - 1) or unscaled (real parameter ranges). I am also tracking
paths for particular solution points that result from genetic algorithms.
As such, comparing spatially equal paths/linestrings
(boost::geometry::equals) along with calculating intersections
(boost::geometry::intersection) and linestring differences
(boost::geometry::difference) with some sort of pre-defined tolerance would
be really nice.

In any case, many thanks once again :)

BW
G

On Tue, Jun 16, 2020 at 10:14 PM  Tinko Bartels <tinkobartels_at_[hidden]>
wrote:

> Hi Giorgino,
>
> I am happy to hear that the mask works.
>
> With regard to hashing: As long as two linestrings share the exact same
> points and differ in no way other than maybe having reverse order, I think
> the idea of normalizing the order of points should work. I adapted your
> sample code to put together an example in godbolt, you can observe the
> output on the right side. shash is the sorting hash and it is the same for
> both linestrings in this example: https://godbolt.org/z/QRbTnR .
>
> The crucial point here is "exactly the same", because hashing the points
> like this is in essence similar to comparing doubles or floats like "a ==
> b" which one usually wants to avoid. Usually one checks something like
> "std::abs(a - b) < 0.0001". Of course your hash only looks at individual
> linestrings so I don't see how that could be done here. If two linestrings
> are generated from different calculations they may differ, even if you
> would expect the results to be the same if the computer could use real
> numbers. Unfortunately there are subtle ways in which floating-point (i.e.
> float, double or long double) arithmetics can mess with your results. For
> example, it is well-known that  a + b + c can be different from a + c + b
> and but I have also seen a compiler optimization that can cause  a * b + c
> * d to be different from c * d + a * b.
>
> There may be ways around this with floating point types (such as double,
> float, long double) for your hashing functions but I can't think of any
> right now, maybe somebody else has an idea.
>
> Here are two ideas for alternatives to hashing geometries with
> floating-point coordinates:
>
> 1) Consider the use of integer coordinates (i.e. int, long or long long).
> That is the solution that was chosen in some projects that I participated
> in. Of course, this is only an option if you can work with the limited
> range of integers and if integers are suitable for all calculations that
> you do in your application and there is no other source of roundoff error.
>
> 2) Consider the use of a map/set instead of an
> unordered_map/unordered_set. Of course that would change the time
> complexity of some operations from O(1) to O(log(n)) but it would allow you
> to consider two linestrings at the same time and you could use some
> tolerance threshold, such as one usually does with floating point types.
> Here is a quickly put together illustration (with std::set) of what I mean
> by that: https://godbolt.org/z/DCkXdY . There are probably pathological
> cases that can break this as well, but maybe this works with your intended
> application.
>
> I don't know how one sets tolerances with the rescaling in Boost.Geometry.
> But I have seen examples in which it was helpful to just disable it by
> defining BOOST_GEOMETRY_NO_ROBUSTNESS, so you could try that and see
> whether that helps with your application.
>
> Kind regards
> Tinko Bartels
>