Delete all the points that are far from a segment

Question

I wrote an algorithm inspired by some answers on StackOverflow : it detects points that are quite far from an infinite line. This algorithm is shown below.

However, I don't work with infinite lines in my project, but with segments. And the problem, according to me, is that if a point has the same ordinate than a segment's extremity, it will not be considered as "far from the segment".

How could I modify this algorithm to make it working with a segment, and not an infinite line please ?

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.

---

Important edit : implementation of the muzzlor's solution

public static List<Point> getOnlyOnSegmentPoints(Point segment_first_point, Point segment_last_point, List<Point> points_to_test, double maximal_allowed_distance) {
    System.out.println("=== Segment : " + segment_first_point + " - " + segment_last_point);
    double segment_first_point_x = segment_first_point.getNumber(0);
    double segment_first_point_y = segment_first_point.getNumber(1);
    double segment_last_point_x = segment_last_point.getNumber(0);
    double segment_last_point_y = segment_last_point.getNumber(1);
    double test_x, test_y;
    double k_numerator, k_denominator;

    Point p;
    List<String> coords_p = new ArrayList<>();

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

    for(Point point_to_test : points_to_test) {

        if(point_to_test == segment_first_point || point_to_test == segment_last_point) {
            continue;
        }

        test_x = point_to_test.getNumber(0);
        test_y = point_to_test.getNumber(1);

        // k = ((x - a).(b - a))/((b - a).(b - a))
        k_numerator = (test_x - segment_first_point_x) * (segment_last_point_x - segment_first_point_x)
                + (test_y - segment_first_point_y) * (segment_last_point_y - segment_first_point_y);

        k_denominator = (segment_last_point_x - segment_first_point_x) * (segment_last_point_x - segment_first_point_x)
                + (segment_last_point_y - segment_first_point_y) * (segment_last_point_y - segment_first_point_y);

        // p = ((x - a).(b - a))/((b - a).(b - a)) (b - a) + a
        coords_p.add(
                ""
                        + (

                        ((test_x - segment_first_point_x) * (segment_last_point_x - segment_first_point_x)) // "((x - a).(b - a))"
                                /
                                (0.00001+ // "((b - a).(b - a))"
                                        (segment_last_point_x - segment_first_point_x) * (segment_last_point_x - segment_first_point_x)

                                )

                                *
                                (segment_last_point_x - segment_first_point_x) // "* (b - a)"

                        +

                        segment_first_point_x) // " + a"
        );
        coords_p.add(
                ""
                        + (

                        ((test_y - segment_first_point_y) * (segment_last_point_y - segment_first_point_y)) // "((x - a).(b - a))"
                                /
                                (0.00001+ // "((b - a).(b - a))"
                                        (segment_last_point_y - segment_first_point_y) * (segment_last_point_y - segment_first_point_y)

                                )

                                *

                                (segment_last_point_y - segment_first_point_y) // "* (b - a)"

                        +

                        segment_first_point_y) // " + a"

        );
        p = new Point(coords_p);

        if(k_numerator/k_denominator < 0 && EuclidianFilters.distanceBetweenTwoPoints(point_to_test, segment_first_point) > maximal_allowed_distance) {
            returned.remove(point_to_test);
            System.out.println("------> Point removed x-a : " + point_to_test);

        } else if(k_numerator/k_denominator >= 0 && k_numerator/k_denominator <= 1 && EuclidianFilters.distanceBetweenTwoPoints(point_to_test, p) > maximal_allowed_distance) {
            returned.remove(point_to_test);
            System.out.println("------> Point removed x-p : " + point_to_test);

        } else if(k_numerator/k_denominator > 1 &&  EuclidianFilters.distanceBetweenTwoPoints(point_to_test, segment_last_point) > maximal_allowed_distance) {
            returned.remove(point_to_test);
            System.out.println("------> Point removed x-b : " + point_to_test);
        }

    }

    return returned;
}

Screenshot illustrating the execution

As you can see, for the Segment : (1 ; 2 ; 0 ) - (1 ; 0 ; 0 ), the point (1 ; 1 ; 0) is considered as too far from it. However, it must be considered as part of this segment.

Answer 1

Any point on the line can be represented as by the equation:

v = a + k (b - a)

Take the projection of your point onto that line and determine the value of k. You can then set up some basic logic based on the values of k (k < 0, k in [0, 1] and k > 1) plus some geometry to calculate the distance from the line segment.

Edit: Going to expand more on this because I realise it was a little terse

I'm going to represent vector variables by single letters because I don't want to have to expand this out, . will represent dot product.

You have a point x, you want to look at its projection p onto that line, and then represent it by the formula above:

p = ((x - a).(b - a))/((b - a).(b - a)) (b - a) + a

From this formula, we can see that the value of k is going to be the coefficient here:

k = ((x - a).(b - a))/((b - a).(b - a))

Now if k < 0, you're going to want to take ||x - a||, if k in [0, 1], then you're going to want to take ||x - p|| as your distance and if k > 1, you want ||x - b||

Edit 2:

Just to clarify, while I used single letters for my vector variables, I also used a single letter for k but it should be thought of as a scalar. Note that it's just made from dot products and so only ever takes on a scalar value. As an example, if we want to break down p into components (p_x, p_y)

 p_x = k * (b_x - a_x) + a_x
 p_y = k * (b_y - a_y) + a_y

Answer 2

1) Calculate the point p that is on the infinite line (a,b) for the point t that you are testing.

2) Calculate how far p is from the point t you are testing, if it is too far, discard it.

3) If the x-coordinates of (a,b) are not equal, then check if the x-coordinate of p is in the range of the x-coordinates of a and b. If so, keep the point. If not, do a distance check from t to a and b, if neither is within the maximum allowed distance then discard it.

4) If the x-coordinates of (a,b) were equal, do the same as step 3 except comparing the y-coordinates.