Eigen: way to check if point is on a segment?

Question

I need to know if a point lies on a segment in 2d.

I already solved that issue using Boost and intersects between a point and a segment.

Question

is it possible to use the Eigen library only?

Why:

I am currently in the middle of an algorithm that uses Eigen, and I don't want to copy my points again and again in a loop to a Boost geometry construct to check for this. This is what I currently do and it works. But it adds a dependency.

This is a contrived code:

using Line2 = Eigen::Hyperplane <double, 2>;
using Vec2 = Eigen::Vector2d;
Vec2 a( 0, 0 );
Vec2 b( 1, 1 );

Vec2 d(70, 100); 

Line2 ab = Line2::Through( a, b );

auto res = ab.normal();

auto projection_point = ab.projection(d); <- that projection point is not on the segment ab
//.. here I test with Boost and loop again if necessary

if there is no alternative I will keep doing it the way I do, but I am sure someone knows better out there.

I don't want to write the function myself (otherwise, I prefer to keep using Boost). I just want to rely on Eigen.

Thanks

Yes, but I have to write it, and I don't want that. I want to minimize my "fingerprint" on that codebase. I could have copy/pasted https://lucidar.me/en/mathematics/check-if-a-point-belongs-on-a-line-segment/ as an example, but I don't want to maintain/explain it after I'm done with that work — Kroma, Aug 03 '22 at 06:56
Well Eigen is not a geometry library. You can formulate the problem in terms of an [overconstrained linear system](https://eigen.tuxfamily.org/dox/group__LeastSquares.html) but it is hardly any simpler or less code than a straightforward solution. — n. m. could be an AI, Aug 03 '22 at 07:35
For checking if a point is "on" a Hyperplane, you can check if the absolute distance is below a threshold: https://eigen.tuxfamily.org/dox/classEigen_1_1Hyperplane.html#a6d7e330896982be88d4e6cf8e9365687 -- for checking if `X` is on a segment between points `A` and `B`, check if `(A-X).norm() + (X-B).norm() < (A-B).norm() + tolerance` — chtz, Aug 03 '22 at 09:49

Homer512 · Answer 1 · 2022-08-03T10:13:20.613

I suggest checking the distance of the point and its projection onto the line against an epsilon. Plus a check against the distance from origin, plus a check (via a dot product) that the point lies in the correct direction from the origin.

Eigen has a parameterized line type for this. It isn't a line segment but an origin plus direction vector. So the maximum distance from the origin has to be computed and stored separately.

using PLine2d = Eigen::ParameterizedLine<double, 2>;
Eigen::Vector2d a = ..., b = ..., d = ...;
PLine2d line = Pline2d::Through(a, b);
double sqrlength = (b - a).squaredNorm();
Eigen::Vector2d projection = line.projection(d);
Eigen::Vector2d fromOrigin = projection - line.origin();
bool isOnLineSegment = projection.isApprox(d) && 
                       fromOrigin.squaredNorm() <= sqrlength &&
                       fromOrigin.dot(line.direction()) >= 0.f;

I haven't counted operations but there is a good chance that the code you linked is shorter and faster when implemented in Eigen. Cross and dot products are readily available, after all.

Replace squaredNorm() with stableNorm() if desired. In 2D hypotNorm() would also work well.

A potential issue is isApprox() which, as the documentations states, fails close to zero. Therefore depending on your data, an extended check may be necessary such as

(projection.isApprox(d) || (d.isZero() && projection.isZero()))

All have tuneable epsilon parameters.

Yes, even with the modification, it still gives me a wrong answer — Kroma, Aug 03 '22 at 09:47
@Kroma You're right, the answer was wrong. We also have to check that the projected point is not before the starting point on the line — Homer512, Aug 03 '22 at 10:14
There are several ways to check this "between" condition, I think the simplest one is dot(a-c,b-c)<=0 but I might be wrong. There is a [list](https://stackoverflow.com/questions/328107/how-can-you-determine-a-point-is-between-two-other-points-on-a-line-segment) of methods by the way. — n. m. could be an AI, Aug 03 '22 at 16:16

Eigen: way to check if point is on a segment?

Question

Why:

1 Answers1