删除远离线段的所有点

Question

我受 Whosebug 上一些答案的启发编写了一个算法：它检测距离无限直线很远的点。该算法如下所示。

但是，我在项目中使用的不是无限线，而是线段。根据我的说法，问题是如果一个点的纵坐标与线段的末端相同，则不会被视为 "far from the segment".

请问我如何修改此算法以使其适用于线段，而不是无限线？

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;

为了确保你理解 :

returned 是线段上或线段附近点的列表（以及确定点是否在线段之外的 "imprecision" / 最大距离段是变量：maximal_allowed_distance)
points_to_test 是我图表中存在的所有点：我的线段+真正在线段上的点+几乎在线段上的点（ <= maximal_allowed_distance) + 远离线段的点 (> maximal_allowed_distance)。 我的小算法的思路是把后面的都去掉
segment_[first|last]_point是两段的四肢
c是points_to_test的当前点，我想知道它是远离段还是在（根据maximal_allowed_distance）
getNumber(0) returns点的X坐标，getNumber(1) returns Y坐标。

重要编辑：muzzlor 解决方案的实施

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;
}

说明执行情况的屏幕截图

如您所见，对于 Segment : (1 ; 2 ; 0 ) - (1 ; 0 ; 0 )，点 (1 ; 1 ; 0) 被认为离它太远。但是，它必须被视为该细分市场的一部分。

Answer 1

直线上的任何一点都可以表示为等式：

v = a + k (b - a)

将您的点投影到该线上并确定 k 的值。然后，您可以根据 k 的值（k < 0、k in [0, 1] 和 k > 1）设置一些基本逻辑加上一些几何来计算距离从线段。

编辑：将对此进行更多扩展，因为我意识到它有点简洁

我将用单个字母表示向量变量，因为我不想扩展它，。将代表点积。

你有一个点x，你想看它在那条直线上的投影p，然后用上面的公式表示它：

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

从这个公式可以看出，k的值就是这里的系数：

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

现在，如果 k < 0，您将要参加 ||x - a||，如果 k 在 [0, 1]，那么您将要参加 ||x - p|| 作为你的距离，如果 k > 1，你想要 ||x - b||

编辑 2：

澄清一下，虽然我对矢量变量使用了单个字母，但我也对 k 使用了单个字母，但它应该被视为标量。请注意，它只是由点积构成，因此只具有标量值。例如，如果我们想将 p 分解为组件 (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) 为您正在测试的点 t 计算无限直线 (a,b) 上的点 p。

2) 计算p离你测试的点t有多远，如果太远，丢弃它。

3) 如果(a,b)的x坐标不相等，则检查p的x坐标是否在a的x坐标范围内和 b。如果是这样，请保持这一点。如果不是，则从 t 到 a 和 b 进行距离检查，如果两者都不在最大允许距离内，则将其丢弃。

4) 如果(a,b)的x坐标相等，除比较y坐标外同步骤3。

删除远离线段的所有点

Delete all the points that are far from a segment

java

algorithm

points

coordinates

重要编辑：muzzlor 解决方案的实施

说明执行情况的屏幕截图