0

So I have a set of points making up a simple polygon

points = [(x0, y0), (x1, y1), ..., (xn, yn)]

The polygon may be concave or convex, both cases must be handled.

Next I create two arcs for each line by treating the arc between point A-B as different from the arc between point B-A. Next I create paths from these points by always choosing the closest counter-clockwise arc. So one path goes clockwise and one counter-clockwise: [(x0, y0), (x1, y1), ... , (xn, yn)] and [(xn, yn), (xn-1, yn-1), ... , (x0, y0)]

By traversing these arcs how do I know if the arcs are creating an internal face or an external face?

For example, in the two polygons below the same orange line is used on two different polygons. In the first polygon the top orange arc is in the internal face (pointing inwards) while in the other polygon the top orange arc is in the external face (pointing outwards).

enter image description here

My question arose from the answer by @HEKTO in this post: How to find all the polygonal shapes of given the vertices?.

Magnuti
  • 63
  • 9
  • But... here you have the only contour, it is external face, there are no internal ones – MBo May 20 '22 at 17:28
  • for concave polygons you can use [hit test](https://stackoverflow.com/a/24465094/2521214) ... for convex the winding rule is enough – Spektre May 21 '22 at 06:46

1 Answers1

0

Use Green's theorem. Iterate over the points and compute the integral, then check the sign. Like this:

decimal sum = 0.0;
for(int current = 0; current < points.length; current++)
{
    int next = current + 1;
    if (next == points.length)
        next = 0;
    sum += (points[this].y + point[next].y) * (point[next].x - point[this].x);
}

Check the sign of sum to find out whether the winding is clockwise or counter-clockwise. Which is which will depend on which direction the Y axis increases in.

Note that if you were trying to compute the area of the polygon you would multiply the Y part of the equation by 0.5, but since you're only interested in the sign of the result you don't need to.

samgak
  • 23,944
  • 4
  • 60
  • 82