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

From: Tinko Bartels (tinkobartels_at_[hidden])
Date: 2020-06-15 11:48:55

Hi Giorgino,

here are two ideas for what could be the correct predicate:
1) intersect ( https://postgis.net/docs/ST_Intersects.html ). This is true
if both geometries are not disjoint. Note that the documentation
says: ST_Overlaps, ST_Touches, ST_Within all imply spatial intersection. So
the Within-case is covered in addition to all cases covered by Overlaps.

However, you ask whether the resultant multipoint will have a size greater
than one. I am not entirely sure, what you mean by that. Touches would be
true for cases where the intersection is only one point or finitely many
points so you may want to rule that out.

The intersection could also be multiple points if the linestrings meet at
multiple locations without sharing a common line. I don't know of a way to
check for "touch at more than one point but possibly only finitely many
points". But if you want them to intersect in a way such that they share at
least one common piece of a line with positive length then what you want to
check is whether the dimension of the intersection of their interior is at
least 1. The distinction I am referring to is illustrated here:
https://ibb.co/sJP2mF3

That can be checked via a DE-9IM-mask, see also
https://en.wikipedia.org/wiki/DE-9IM (this is also a useful read because it
lists definitions of many spatial predicates).

So that would be my idea 2):

2) use the relate check with the mask "1********". This checks whether the
intersection of their interior is of dimension 1. I believe this is
equivalent to "overlaps or within(a,b) or within(b,a)" for one-dimensional
geometries like linestrings. I think the correct code would look like this:

    linestring_2d line_test1({ point_2d(0.0, 0.0), point_2d(2.0, 0.0) });
    linestring_2d line_test2({ point_2d(0.0, 0.0), point_2d(1.0, 0.0) });
    boost::geometry::de9im::mask mask("1********");
    bool check = boost::geometry::relate(line_test1, line_test1, mask);

Now, with regard to your hashing issue. I am not an hashing-expert, but I
hope the following considerations are helpful:

You could normalize the orientation input linestrings like this: compare
the start and the end point lexicographically: start < end iff start.x <
end x || (start.x == end.x && start.y < end.y). Reverse the linestring if
start is not smaller than end, then hash as you do now. The reversal does
not need to be stored explicitly, you can just traverse it in the opposite
direction during hashing. However, if start == end, that check is
insufficient, and maybe you can then compare the point after start with end
and so on until you can be sure of the orientation (if all points are the
same, there is nothing do reverse).

This may be sufficient if your linestrings are normalized up to
orientation. However, if you have two linestrings like {a,b,c} and {a,c},
where b is some point on the line [a, c], that hashing mechanism would be
still insufficient to detect spatial equality. You could eliminate that by
normalizing the linestrings in the hashing function by eliminating all such
points b. However, I noted that you use double coordinates, so there may be
surprises with regard to what points are actually collinear (for example,
numbers like 0.2 are not exactly representable in double precision) and
whether that is correctly detected by the side-strategy. Maybe your
geometries are generated in a way that makes this a non-issue, though.

Kind regards
Tinko

Am Mo., 15. Juni 2020 um 10:08 Uhr schrieb Giorgino R <giorginor21_at_[hidden]
>:

> Hi Tinko,
>
> Many thanks for your instant response and for looking at both questions.
>
> You are correct, I missed that bit "*By that we mean they intersect, but
> one does not completely contain another*". Do you know which geometric
> function is more appropriate for this so as to get true?
> Will that be an intersection operation with a resultant multipoint with
> size greater than one?
>
> BW
> G
>
>
>
> On Mon, Jun 15, 2020 at 9:01 AM Tinko Bartels via Geometry <
> geometry_at_[hidden]> wrote:
>
>> Hi Giorgino,
>>
>> this is not a complete answer (I may look at question ii) later), but I
>> think I may have the answer for question i):
>>
>> Note, how the postgis-doc you linked specifies "By that we mean they
>> intersect, but one does not completely contain another." I think,
>> line_test_1 completely contains line_test_2 so "false" should be the
>> expected result of the overlaps-check. If you want "true" you may want to
>> look for another geometric relation.
>>
>> Kind regards
>> Tinko
>>
>> Am Mo., 15. Juni 2020 um 09:23 Uhr schrieb Giorgino R via Geometry <
>> geometry_at_[hidden]>:
>>
>>> Hi there,
>>>
>>> I have two questions for boost::geometry, any help will be much
>>> appreciated:
>>>
>>> i) I am trying to use overlap function for two linestrings (
>>> https://postgis.net/docs/ST_Overlaps.html); however, it looks like I am
>>> doing something wrong (?) .
>>>
>>>   using point_2d = bg::model::point<double, 2, bg::cs::cartesian>;
>>>   using linestring_2d = bg::model::linestring<point_2d>;
>>>
>>>   // overlaps
>>>   linestring_2d line_test_1({ point_2d(0.0, 0.0), point_2d(2.0, 0.0) });
>>>   linestring_2d line_test_2({ point_2d(0.0, 0.0), point_2d(1.0, 0.0) });
>>>   bool res = bg::overlaps(line_test1, line_test2);
>>>
>>> This results to false. Should I use a specific strategy? I checked also
>>> tests and I saw that you do test overlap for linestrings.
>>>
>>> ii) I have a structure that contains a linestring. I want to use an
>>> unordered set for storing unique objects with respect to their geometry
>>> (linestring). Therefore, I will need to write hash functions as below:
>>>
>>>
>>> struct Object_hash
>>> {
>>>   std::size_t operator()(const Object& obj) const
>>>   {
>>>     Linestring<Point> linestring = obj.get_linestring();
>>>     std::size_t hash = 0;
>>>     for (auto iter=linestring.cbegin(); iter!=linestring.cend(); ++iter)
>>>     {
>>>       boost::hash_combine(hash, iter->x1());
>>>       boost::hash_combine(hash, iter->x2());
>>>     }
>>>     return hash;
>>>   }
>>> };
>>>
>>> struct Object_compare
>>> {
>>>   bool operator()(const Object& obj1, const Object & obj2) const
>>>   {
>>>     return boost::geometry::equals(obj1.get_linestring(),
>>> obj2.get_linestring());
>>>   }
>>> };
>>>
>>> As expected, the above is valid for linestrings with the same direction
>>> of their points. If one linestring is reversed this off course will not be
>>> valid. Is there any way that I can find a better hashing function? Is there
>>> any invariant field (for two spatial equaly linestrings) that I could use
>>> to create hash key?
>>>
>>> Many thanks in adavnce,
>>> BW
>>> G
>>>
>>> _______________________________________________
>>> Geometry mailing list
>>> Geometry_at_[hidden]
>>> https://lists.boost.org/mailman/listinfo.cgi/geometry
>>>
>> _______________________________________________
>> Geometry mailing list
>> Geometry_at_[hidden]
>> https://lists.boost.org/mailman/listinfo.cgi/geometry
>>
>