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@gmail.com> 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@gmail.com>:
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@lists.boost.org> 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@lists.boost.org>:
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@lists.boost.org
https://lists.boost.org/mailman/listinfo.cgi/geometry
_______________________________________________
Geometry mailing list
Geometry@lists.boost.org
https://lists.boost.org/mailman/listinfo.cgi/geometry