How to remove points that are far from a segment?

问题:

I read how to keep points that are between two points (ie. : that are part of a segment, with some imprecision) here : How can I tell if a point is nearby a certain line?

Thus, I implemented this little algorithm in Java, and my code is (note that the variables' name should be clear for you ! :) ) :

    List<Cupple> returned = new ArrayList<>(points_to_test);

    for(Cupple c : points_to_test) {

        /*if(c == segment_first_point || c == segment_last_point) {
            continue;
        }*/

        if(Math.abs(Math.abs(
                (segment_last_point.getNumber(0) - segment_first_point.getNumber(0))
                        *
                        (segment_first_point.getNumber(1) - c.getNumber(1))
                        -
                        (segment_first_point.getNumber(0) - c.getNumber(0))
                                *
                                (segment_last_point.getNumber(1) - segment_first_point.getNumber(1))
        )
                /
                Math.sqrt(
                        Math.pow((segment_last_point.getNumber(0) - segment_first_point.getNumber(0)), 2)
                                +
                                Math.pow((segment_last_point.getNumber(1) - segment_first_point.getNumber(1)), 2)
                )

        ) > maximal_allowed_distance) {

            returned.remove(c);
        }
    }

    return returned;

To be sure you understand :

1. returned is the list with points that are on the segment, or near the segment (and the "imprecision" / maximal distance that determine if a point is out of the segment is the variable : maximal_allowed_distance)

2. points_to_test are ALL the points that are present in my graph : the both of my segment + the points that are really on the segment + the points that are almost on the segment (<= maximal_allowed_distance) + the points that are far from the segment (> maximal_allowed_distance). The idea of my little algorithm is that I remove all the latter.

3. segment_[first|last]_point are the two segment's extremities

4. c is the current point of points_to_test and I want to know if it is far from the segment or in (according to the maximal_allowed_distance)

5. getNumber(0) returns the X coordinate of the point, getNumber(1) returns the Y one.

However, it does not work. It doesn't return the good points (ie. : the points that are in the segment, taking account of maximal_allowed_distance).

Do you know if I misunderstood the answer I gave you in the first line of this question ? Do you see any mistake in my own implementation of this algorithm ?

回答1:

Note, that cited method determines distance from infinite line. If you need points near limited segment only, you would modify it.

In any case algorithm should find points far from the line. If it does not do this, check
a) whether it ever finds points to remove
b) whether it is able to remove object c that belongs to points_to_test list, from returned list

Edit
There is rather effective approach to find a distance between point and line segment using vector arithmetics

// Copyright 2001 softSurfer, 2012 Dan Sunday
// This code may be freely used, distributed and modified for any purpose
// providing that this copyright notice is included with it.
// SoftSurfer makes no warranty for this code, and cannot be held
// liable for any real or imagined damage resulting from its use.
// Users of this code must verify correctness for their application.


// Assume that classes are already given for the objects:
//     Point and Vector with
//          coordinates {float x, y, z;} (z=0  for 2D)
//          appropriate operators for:
//               Point  = Point ± Vector
//               Vector = Point - Point
//               Vector = Scalar * Vector
//     Line with defining endpoints {Point P0, P1;}
//     Segment with defining endpoints {Point P0, P1;}
//===================================================================

// dot product (3D) which allows vector operations in arguments
#define dot(u,v)   ((u).x * (v).x + (u).y * (v).y + (u).z * (v).z)
#define norm(v)     sqrt(dot(v,v))     // norm = length of  vector
#define d(u,v)      norm(u-v)          // distance = norm of difference
// dist_Point_to_Segment(): get the distance of a point to a segment
//     Input:  a Point P and a Segment S (in any dimension)
//     Return: the shortest distance from P to S
float
dist_Point_to_Segment( Point P, Segment S)
{
     Vector v = S.P1 - S.P0;
     Vector w = P - S.P0;

     double c1 = dot(w,v);
     if ( c1 <= 0 )
          return d(P, S.P0);

     double c2 = dot(v,v);
     if ( c2 <= c1 )
          return d(P, S.P1);

     double b = c1 / c2;
     Point Pb = S.P0 + b * v;
     return d(P, Pb);
}