Как найти, какие 2D точки в массиве ListList коллинеарны

Question

У меня есть arrayList, в котором хранятся 2D точки.При соединении этих точек вместе они представляют маршрут.Я хочу найти, какие точки находятся на одной линии (коллинеарны), чтобы я мог знать, в каких точках происходят повороты / углы.Примером может быть:

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

Вы должны , а не вычислять наклон, когда присутствуют вертикальные линии.

Из изображения и описания я предполагаю, что у вас есть только целочисленные координаты и две последовательные точкивсегда иметь расстояние Чебышева , равное 1. (Если это не так, вам следует отредактировать свой ответ и включить дополнительную информацию).

Затем точка (x _{i *)1010 *, y i ) является поворотным моментом, когда}

• x _i-1 - x _i ! = X _{i + 1} - x _i и
• y _i-1 - y _i ! =y _{i + 1} - y _i

Я лично рекомендовал бы вычислить индексы этих точек в списке,потому что у этого есть несколько преимуществ:

• Вы не столкнетесь с проблемами, когда одна и та же точка появится несколько раз
• Вы можете легко найти точки в списке, когда у вас есть индекс
• Вы можете использовать последовательный указатель поворотаces для вычисления подсписков точек, которые коллинеарны

Это реализовано здесь в качестве примера:

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)]

Answer 2

Рассчитывая изменения наклона для каждой соседней пары в спискеВы можете получить точки, где происходят «повороты».Java может заботиться о вертикальных линиях, вычисляя наклон как « Infinity »,так что не беспокойтесь об этом.

public static void main(String[] args) {
    ArrayList<Point> positions = new ArrayList<Point>();
    positions.add(new Point(1,0));
    positions.add(new Point(1,1));
    positions.add(new Point(1,2));
    positions.add(new Point(2,2));
    positions.add(new Point(3,1));
    positions.add(new Point(4,1));
    positions.add(new Point(5,1));
    positions.add(new Point(5,2));

    ArrayList<Point> turns = new ArrayList<Point>();
    for (int i = 0; i < positions.size(); i++) {
        turns.add(null);
    }

    int counter = 0;
    if (positions.size() > 2) {
        Point base = positions.get(0);
        Point next = positions.get(1);
        int x = (next.x - base.x);
        double slope = 1.0 * (next.y - base.y) / (next.x - base.x);

        for (int i = 2; i < positions.size(); i++) {
            Point newpoint = positions.get(i);

            double newslope = 1.0 * (newpoint.y - next.y) / (newpoint.x - next.x);
            if (newslope != slope) {
                counter++;
                turns.set(i - 1, positions.get(i - 1));
                slope = newslope;
            }

            next = newpoint;
        }
    }

    System.out.println("Collinear points:");
    for (int i = 0; i < positions.size(); i++) {
        System.out.print("(" + positions.get(i).x + ", " + positions.get(i).y + ") ");
        if (turns.get(i) != null) {
            System.out.println();
            System.out.print("(" + positions.get(i).x + ", " + positions.get(i).y + ") ");
        }
    }

    System.out.println();
    System.out.println();

    if (counter > 0) {
        System.out.println("Turns at these points: ");
        for (Point p : turns) {
            if (p != null)
                System.out.print("(" + p.x + ", " + p.y + ") ");
        }
    } else {
        System.out.println("There are no turns!");
    }
}

напечатает:

Collinear points:
(1, 0) (1, 1) (1, 2) 
(1, 2) (2, 2) 
(2, 2) (3, 1) 
(3, 1) (4, 1) (5, 1) 
(5, 1) (5, 2) 

Turns at these points: 
(1, 2) (2, 2) (3, 1) (5, 1)