1

I'm currently using boost 1.67 and I'm finding that if I use boost::geometry::within() to check if a point is within a segment, I'm not getting answers I'd expect. For example, I can construct a couple of segments that intersect, and use boost::geometry::intersection() to acquire the point of intersection. I would expect that point to be within each of the edges. That's not always what I'm seeing, however. Here's some code demonstrating my problem:

#include <iostream>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>

int main() {
    using point_t = boost::geometry::model::d2::point_xy<double>;
    using segment_t = boost::geometry::model::segment<point_t>;
    segment_t e1{point_t{100, 350}, point_t{-100, 400}};
    segment_t e2{point_t{0, 0}, point_t{90, 600}};
    std::vector<point_t> iv;
    boost::geometry::intersection(e1, e2, iv);
    assert(iv.size() == 1);
    const auto& v = iv[0];
    bool is_within = boost::geometry::within(v, e1);
    std::cout << "is within? " << is_within << std::endl;
    is_within = boost::geometry::within(v, e2);
    std::cout << "is within? " << is_within << std::endl;

    return 0;
}

In this case within() returns false for both edges.

user888379
  • 1,343
  • 12
  • 30
  • What value does the intersection point `v` have? – Xirema Oct 02 '18 at 16:55
  • First `within` returns false if point lies on segment (it is default strategy, you can change this strategy). You can use `covered_by` instead of `within`, in this case algorithm checks the border by default - but it doesn't help you. These calculations are made using float - math arithmetic , you need to use some approximation to test if point lies on segment. Try to call `boost::geometry::distance(v,e1)` and you will get value which is not 0.0, it is very small floating-point value but it is different from `0` I suppose while testing if point is on segment this dst is 0. So your test fails. – rafix07 Oct 02 '18 at 17:05
  • @Xirema the intersection point is (54.216867469879517, 361.4457831325301), for what it's worth. – user888379 Oct 02 '18 at 17:51
  • @rafix07 I don't think that's quite true. I can set up a trivial case where the segment runs from (-100, 0) to (100, 0) and give a test point of (0, 0). In that case `within()` returns true. – user888379 Oct 02 '18 at 17:57
  • yes, but does it cover all cases ? I don't think so. You need to have one universal method to check if point lies on segment and don't rely on input data. – rafix07 Oct 02 '18 at 18:00

2 Answers2

2

I'm going to post this as an answer in hopes that it may be useful to others in the future. If you need to check that a given point lies on a segment, don't use within() (or covered_by(), for that matter). In the comments to the original question, @rafix07 suggested a more useful approach to solving this problem: use boost::geometry::distance(point, segment). You can set an appropriate tolerance for your situation, and if the measured distance falls inside it, declare victory and move on.

user888379
  • 1,343
  • 12
  • 30
1

This question is almost a duplicate of Is Floating Point Math Broken?, though distinct enough that I don't think it should be flagged as such.

You have two problems in total:

  • boost::geometry::within will return false for points that are exactly on the border of a geometry object, which will be the case for all points in a line. You need to change the strategy to permit within to return true for points that are on the border.
  • Calculating the intersection of two points will, usually, result in some degree of error during the floating point math. You can't guarantee that the point determined to be the intersection of two lines is literally on either line. You need to allow a certain degree of tolerance in the distance up to a delta value (defined by you, I wouldn't go larger than one ten-thousandth) to permit being treated as "intersecting" the line.
Xirema
  • 19,889
  • 4
  • 32
  • 68
  • I'm a little dismayed that the default behavior of `within()` is basically useless when called with a point and a segment. – user888379 Oct 02 '18 at 18:12
  • @user888379 It's clearly intended to be used with intersecting geometries with actual area. Like building a triangle and a rectangle and taking the intersection of those two objects, then checking if a given point is "within" the intersection. Like Rafix suggested, use `covered_by` if you need a function whose default behavior is to handle this case. – Xirema Oct 02 '18 at 18:14
  • Okay, but perhaps it would be better for `within()` to simply not support the point-segment combination. – user888379 Oct 02 '18 at 18:27
  • @user888379 The boost.geometry library is highly generic, they'd have to add a special clause to disallow that particular use, and it's not obvious that no valid use of that combination exists. – Xirema Oct 02 '18 at 18:29
  • Fair enough. Thanks for your indulgence of my complaints :). – user888379 Oct 02 '18 at 18:33