How can I iterate over the vertices of a polygon and compare two vertices with each other?

Question

I have an XML - list of xy-coordinates (vertices) that define the edge of a polygon. I read this file and save the vertices in an ArrayList. Now I would like to iterate over the finished ArrayList and compare two vertices with each other to decide whether the edge connecting both vertices is a north, west, south, or east edge of the simple polygon.

This is the code I can use to test whether the edge that makes up two points is a north, west, east, or south edge.

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

I have two concerns for which I don't find a solution:

First I would like to test whether the vertices are sorted clockwise or counterclockwise. Accordingly, I would have to change the code for the edge types.

Second I don't know how I can iterate over the ArrayList of vertices in order to compare two of the vertices at each step. For example in the first step v1 with v2, in the second v2 with v3, in the third v3 with v4 and so on.. Can I perhaps address the vertices in the ArrayList with their indices?

right, left, bottom, top edges - this doesn't sound like a polygon, this sounds like a rectangle. What about edges that don't fit cleanly into these designations? Also, are you aware of java.awt.Polygon (and Polygon2D)? — ControlAltDel, May 05 '20 at 13:02
It is a orthogonal Polygon, so all edges are parallel to the x- or y-axis. java.awt.Polygon I cannot use since the x and y coordinates are float values — C-lara, May 05 '20 at 13:16

score 1 · Answer 1 · answered May 05 '20 at 13:18

Regarding your first question, there are a number of ways to find the orientation of a polygon. See the discussion on SO here.

As for comparing the points in a polygon, you can do something like the below:

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
}

This will compare each point with the next, including comparing the last point with the first to 'close the loop'. If this isn't needed, you can do a small change to stop as soon as the last point is reached:

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

Thank you! And then I can access the x and y value of the point for "current" and "next"? — C-lara, May 05 '20 at 13:30
yep, should be something like current.getX(), next.getY(), etc. — Jurgen Camilleri, May 05 '20 at 14:03

RaffleBuffle · Accepted Answer · 2020-05-05T16:02:24.870

For a simple orthogonal polygon with no self-intersections you can determine its orientation (CW|CCW) by finding the lower left corner point and determining if the y value of the next point is equal to (CCW) or greater (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;
}

Once you have the orientation you can iterate through the edges to determine their type.

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

With

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

Obviously the type for CW polygons is reversed.

How can I iterate over the vertices of a polygon and compare two vertices with each other?

2 Answers2