Как я могу перебирать вершины многоугольника и сравнивать две вершины друг с другом?

Question

У меня есть XML - список xy-координат (вершин), которые определяют край многоугольника. Я прочитал этот файл и сохранил вершины в ArrayList. Теперь я хотел бы перебрать готовый список ArrayList и сравнить две вершины друг с другом, чтобы решить, является ли ребро, соединяющее обе вершины, северным, западным, южным или восточным краем простого многоугольника.

Это код, который я могу использовать, чтобы проверить, является ли край, составляющий две точки, северным, западным, восточным или южным краем.

enum EdgeType {TOP, BOTTOM, LEFT, RIGHT, EMPTY}

public EdgeType orthoEdgeTypeCCW(double x0, double y0, double x1, double y1)
{
if(x0 == x1) // vertical
{           
    return (y0 < y1) ? EdgeType.RIGHT : 
           (y0 > y1) ? EdgeType.LEFT : 
                       EdgeType.EMPTY;
}
else if(y0 == y1) // horizontal
{
    return (x0 < x1) ? EdgeType.BOTTOM : 
           (x0 > x1) ? EdgeType.TOP : 
                       EdgeType.EMPTY;
}
else
{
    throw new IllegalArgumentException("Edge not orthogonal");
}
}

У меня есть две проблемы, решения которых я не могу найти:

Первый Я хотел бы проверить, отсортированы ли вершины по часовой стрелке или против часовой стрелки. Соответственно, мне пришлось бы изменить код для типов ребер.

Второй Я не знаю, как я могу перебирать ArrayList вершин, чтобы сравнить две вершины в каждый шаг. Например, на первом шаге v1 с v2, на втором v2 с v3, на третьем v3 с v4 и так далее .. Могу ли я, возможно, адресовать вершины в ArrayList с их индексами?

Answer 1

Для простого ортогонального многоугольника без самопересечений вы можете определить его ориентацию (CW | CCW), найдя нижнюю левую угловую точку и определив, равно ли значение y следующей точки (CCW) или больше (CW ).

enum Orientation {CW, CCW}

public Orientation orientation(List<Point2D> points)
{
    int minIdx = 0;
    for(int i=1; i<points.size(); i++)
        if(pointOrder(points.get(i), points.get(minIdx)) <= 0) minIdx = i;

    int nextIdx = (minIdx+1) % points.size();       
    if(points.get(nextIdx).getY() == points.get(minIdx).getY()) 
        return Orientation.CCW;
    else
        return Orientation.CW;
}

public int pointOrder(Point2D p1, Point2D p2)
{
    if(p1.getY() < p2.getY()) return -1;
    else if(p1.getY() > p2.getY()) return 1;
    else if(p1.getX() < p2.getX()) return -1;
    else if(p1.getX() > p2.getX()) return 1;
    else return 0;
}

Когда у вас есть ориентация, вы можете перебирать края, чтобы определить их тип.

for(int i=0, j=points.size()-1; i<points.size(); j=i++)
{
    EdgeType edgeType = orthoEdgeTypeCCW(points.get(j), points.get(i));
    System.out.format("%s -> %s : %s%n", points.get(j), points.get(i), edgeType);
}

С

public EdgeType orthoEdgeTypeCCW(Point2D p1, Point2D p2)
{
    if(p1.getX() == p2.getX()) // vertical
    {           
        return (p1.getY() < p2.getY()) ? EdgeType.RIGHT : 
               (p1.getY() > p2.getY()) ? EdgeType.LEFT : 
                                         EdgeType.EMPTY;
    }
    else if(p1.getY() == p2.getY()) // horizontal
    {
        return (p1.getX() < p2.getX()) ? EdgeType.BOTTOM : 
               (p1.getX() > p2.getX()) ? EdgeType.TOP : 
                                         EdgeType.EMPTY;
    }
    else
    {
        throw new IllegalArgumentException("Edge not orthogonal");
    }
}

Очевидно, тип для CW полигонов перевернут.

Answer 2

Относительно вашего первого вопроса. Есть несколько способов найти ориентацию многоугольника. См. Обсуждение SO здесь.

Что касается сравнения точек в многоугольнике, вы можете сделать что-то вроде следующего:

List<Point2D.Float> points = new ArrayList<>(); //your initial set of points
for (int i = 0; i < points.size(); i++) {
    Point2D.Float current = points.get(i);
    Point2D.Float next = points.get((i + 1) % points.size());
    //do your comparison between the two points here
}

Это будет сравнивать каждую точку со следующей, включая сравнение последней точки с первой, чтобы «закрыть l oop». Если в этом нет необходимости, вы можете сделать небольшое изменение, чтобы остановиться, как только будет достигнута последняя точка:

List<Point2D.Float> points = new ArrayList<>(); //your initial set of points
for (int i = 0; i < points.size() - 1; i++) {
    Point2D.Float current = points.get(i);
    Point2D.Float next = points.get((i + 1));
}