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

From: Giorgino R (giorginor21_at_[hidden])
Date: 2020-06-16 04:45:02

Hi Tinko,

Your suggestion with respect to my first question looks to solve my
problem. I used the `boost::geometry::relate` along with the 1D mask :) .

Now, as far as the hashing issue is concerned, I think that even if I sort
out the compare method by reversing the linestring (temporary), the hashing
function will still result in different hashing value ( even though they
will have equal coordinates of each point the hashing order will result in
different value).

You also mentioned about using Points with double type coordinates. This is
a good point, I have come across some issues with some operations (e.g.
boost::geometry::difference); especially for linestrings. When I set
strategy with float precision (
boost::geometry::strategy::intersection::cartesian_segments<float>()) I get
what I expect. However, I am not fully aware if it will be correct/safe to
set my points to float precision. Do you have any reference on setting
tolerance in boost::geometry? My understanding is that boost::geometry is
using epsilon<T> for tolerance.

Many thanks and best regards,
G

On Mon, Jun 15, 2020 at 12:49 PM Tinko Bartels <tinkobartels_at_[hidden]>
wrote:

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