java - 如何查找 arrayList 中哪些 2D 点共线

Question

我有一个存储 2D 点的 arrayList。将这些点连接在一起时，它们就代表了一条路线。我想找到哪些点在同一条线上(共线)，这样我就可以知道哪些点发生转弯/拐角。一个例子是:

ArrayList<Point> positions = new ArrayList<Point>();
positions.add(Point(0,0));
positions.add(Point(0,1));
positions.add(Point(0,2));
positions.add(Point(1,2));
positions.add(Point(2,2));
positions.add(Point(3,3));

示例图片:

我希望能够知道在此示例中，点 C、D、E 和 G > 是“转弯”发生的地方，而点 A,B,C, C,D, D,E, E, F,G 和 G,H 共线。

我的想法是首先采样三个点并检查斜率。如果斜率不匹配，我就知道第三个点与前两个点不共线。如果它们确实存在，我就知道它们是共线的，并且我会检查更多点，直到斜率不匹配为止。然后我知道第一行结束，第二行开始，以及转弯发生在哪里。我重复这个过程。但是我不知道如何实现这一点。我真的很感激任何帮助。

编辑:我只有整数坐标，并且两个连续点的切比雪夫距离始终为 1。感谢@Marco13。

Answer 1

当涉及垂直线时，您不应该不计算斜率。

根据图像和描述，我假设您只有整数坐标，并且两个连续点始终具有 Chebyshev distance 1.(如果情况并非如此，您应该编辑您的答案并包含更多信息)。

那么，一个点(x_i, y_i)就是一个转折点，当

• x_i-1 - x_i != x_i+1 - x_i 和
• y_i-1 - y_i != y_i+1 - y_i

我个人建议计算列表中这些点的索引，因为这有几个优点:

• 当同一点出现多次时，您不会遇到麻烦
• 有了索引，您就可以轻松地在列表中查找点
• 您可以使用连续的转折点索引来计算共线点的子列表

这是作为示例实现的:

import java.awt.Point;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class TurningPoints
{
    public static void main(String[] args)
    {
        List<Point> points = new ArrayList<Point>();
        points.add(createPoint("A", 1, 0));
        points.add(createPoint("B", 1, 1));
        points.add(createPoint("C", 1, 2));
        points.add(createPoint("D", 2, 2));
        points.add(createPoint("E", 3, 1));
        points.add(createPoint("F", 4, 1));
        points.add(createPoint("G", 5, 1));
        points.add(createPoint("H", 5, 2));

        List<Integer> indices = computeTurningPointIndices(points);
        System.out.println("Turning points are at " + indices);

        List<Point> turningPoints = indices.stream().map(i -> points.get(i))
            .collect(Collectors.toList());
        System.out.println("They are " + turningPoints);

        System.out.println("Collinear:");
        indices.add(0, 0);
        indices.add(points.size() - 1);
        for (int i = 0; i < indices.size() - 1; i++)
        {
            int i0 = indices.get(i);
            int i1 = indices.get(i + 1);
            List<Point> collinear = points.subList(i0, i1 + 1);

            System.out.println("    " + collinear);
        }
    }

    private static List<Integer> computeTurningPointIndices(List<Point> points)
    {
        List<Integer> indices = new ArrayList<Integer>();
        for (int i = 1; i < points.size() - 1; i++)
        {
            Point prev = points.get(i - 1);
            Point curr = points.get(i);
            Point next = points.get(i + 1);
            int dxPrev = prev.x - curr.x;
            int dyPrev = prev.y - curr.y;
            int dxNext = next.x - curr.x;
            int dyNext = next.y - curr.y;
            if (dxPrev != dxNext && dyPrev != dyNext)
            {
                indices.add(i);
            }
        }
        return indices;
    }

    private static Point createPoint(String name, int x, int y)
    {
        // Only for this example. You should usually not do this!
        return new Point(x, y)
        {
            @Override
            public String toString()
            {
                return name + "(" + x + "," + y + ")";
            }
        };
    }

}

输出为

Turning points are at [2, 3, 4, 6]
They are [C(1,2), D(2,2), E(3,1), G(5,1)]
Collinear:
    [A(1,0), B(1,1), C(1,2)]
    [C(1,2), D(2,2)]
    [D(2,2), E(3,1)]
    [E(3,1), F(4,1), G(5,1)]
    [G(5,1), H(5,2)]