How to determine if a list of polygon points are in clockwise order?

Question

Having a list of points, how do I find if they are in clockwise order?

For example:

point[0] = (5,0)
point[1] = (6,4)
point[2] = (4,5)
point[3] = (1,5)
point[4] = (1,0)

would say that it is anti-clockwise (or counter-clockwise, for some people).

Solution 1

Some of the suggested methods will fail in the case of a non-convex polygon, such as a crescent. Here's a simple one that will work with non-convex polygons (it'll even work with a self-intersecting polygon like a figure-eight, telling you whether it's mostly clockwise).

Sum over the edges, (x₂ − x₁)(y₂ + y₁). If the result is positive the curve is clockwise, if it's negative the curve is counter-clockwise. (The result is twice the enclosed area, with a +/- convention.)

point[0] = (5,0)   edge[0]: (6-5)(4+0) =   4
point[1] = (6,4)   edge[1]: (4-6)(5+4) = -18
point[2] = (4,5)   edge[2]: (1-4)(5+5) = -30
point[3] = (1,5)   edge[3]: (1-1)(0+5) =   0
point[4] = (1,0)   edge[4]: (5-1)(0+0) =   0
                                         ---
                                         -44  counter-clockwise

Solution 2

Find the vertex with smallest y (and largest x if there are ties). Let the vertex be A and the previous vertex in the list be B and the next vertex in the list be C. Now compute the sign of the cross product of AB and AC.

---

References:

• How do I find the orientation of a simple polygon? in Frequently Asked Questions: comp.graphics.algorithms.

• Curve orientation at Wikipedia.

Solution 3

I'm going to throw out another solution because it's straightforward and not mathematically intensive - it just uses basic algebra. Calculate the signed area of the polygon. If it's negative the points are in clockwise order, if it's positive they are counterclockwise. (This is very similar to Beta's solution.)

Calculate the signed area: A = 1/2 * (x₁*y₂ - x₂*y₁ + x₂*y₃ - x₃*y₂ + ... + x_n*y₁ - x₁*y_n)

Or in pseudo-code:

signedArea = 0
for each point in points:
    x1 = point[0]
    y1 = point[1]
    if point is last point
        x2 = firstPoint[0]
        y2 = firstPoint[1]
    else
        x2 = nextPoint[0]
        y2 = nextPoint[1]
    end if

    signedArea += (x1 * y2 - x2 * y1)
end for
return signedArea / 2

Note that if you are only checking the ordering, you don't need to bother dividing by 2.

Sources: http://mathworld.wolfram.com/PolygonArea.html

Solution 4

The cross product measures the degree of perpendicular-ness of two vectors. Imagine that each edge of your polygon is a vector in the x-y plane of a three-dimensional (3-D) xyz space. Then the cross product of two successive edges is a vector in the z-direction, (positive z-direction if the second segment is clockwise, minus z-direction if it's counter-clockwise). The magnitude of this vector is proportional to the sine of the angle between the two original edges, so it reaches a maximum when they are perpendicular, and tapers off to disappear when the edges are collinear (parallel).

So, for each vertex (point) of the polygon, calculate the cross-product magnitude of the two adjoining edges:

Using your data:
point[0] = (5, 0)
point[1] = (6, 4)
point[2] = (4, 5)
point[3] = (1, 5)
point[4] = (1, 0)

So Label the edges consecutively as
edgeA is the segment from point0 to point1 and
edgeB between point1 to point2
...
edgeE is between point4 and point0.

Then Vertex A (point0) is between
edgeE [From point4 to point0]
edgeA [From point0 to `point1'

These two edges are themselves vectors, whose x and y coordinates can be determined by subtracting the coordinates of their start and end points:

edgeE = point0 - point4 = (1, 0) - (5, 0) = (-4, 0) and
edgeA = point1 - point0 = (6, 4) - (1, 0) = (5, 4) and

And the cross product of these two adjoining edges is calculated using the determinant of the following matrix, which is constructed by putting the coordinates of the two vectors below the symbols representing the three coordinate axis (i, j, & k). The third (zero)-valued coordinate is there because the cross product concept is a 3-D construct, and so we extend these 2-D vectors into 3-D in order to apply the cross-product:

 i    j    k 
-4    0    0
 1    4    0    

Given that all cross-products produce a vector perpendicular to the plane of two vectors being multiplied, the determinant of the matrix above only has a k, (or z-axis) component.
The formula for calculating the magnitude of the k or z-axis component is
a1*b2 - a2*b1 = -4* 4 - 0* 1 = -16

The magnitude of this value (-16), is a measure of the sine of the angle between the 2 original vectors, multiplied by the product of the magnitudes of the 2 vectors.
Actually, another formula for its value is
A X B (Cross Product) = |A| * |B| * sin(AB).

So, to get back to just a measure of the angle you need to divide this value, (-16), by the product of the magnitudes of the two vectors.

|A| * |B| = 4 * Sqrt(17) = 16.4924...

So the measure of sin(AB) = -16 / 16.4924 = -.97014...

This is a measure of whether the next segment after the vertex has bent to the left or right, and by how much. There is no need to take arc-sine. All we will care about is its magnitude, and of course its sign (positive or negative)!

Do this for each of the other 4 points around the closed path, and add up the values from this calculation at each vertex..

If final sum is positive, you went clockwise, negative, counterclockwise.

Solution 5

Here is a simple C# implementation of the algorithm based on @Beta's answer.

Let's assume that we have a Vector type having X and Y properties of type double.

public bool IsClockwise(IList<Vector> vertices)
{
    double sum = 0.0;
    for (int i = 0; i < vertices.Count; i++) {
        Vector v1 = vertices[i];
        Vector v2 = vertices[(i + 1) % vertices.Count];
        sum += (v2.X - v1.X) * (v2.Y + v1.Y);
    }
    return sum > 0.0;
}

% is the modulo or remainder operator performing the modulo operation which (according to Wikipedia) finds the remainder after division of one number by another.

---

Optimized version according to @MichelRouzic's comment:

double sum = 0.0;
Vector v1 = vertices[vertices.Count - 1]; // or vertices[^1] with
                                          // C# 8.0+ and .NET Core
for (int i = 0; i < vertices.Count; i++) {
    Vector v2 = vertices[i];
    sum += (v2.X - v1.X) * (v2.Y + v1.Y);
    v1 = v2;
}
return sum > 0.0;

This saves not only the modulo operation % but also an array indexing.

View more solutions

Comments

[ToolmakerSteve]

PLEASE NOTE: The accepted answer, and many answers after it, require a lot of additions and multiplications (they are based on area calculations that end negative or positive; e.g. "shoelace formula"). Before implementing one of those, consider lhf's answer, which is simpler/quicker - based on wiki - orientation of simple polygon.

[duffymo]

I always think of it in terms of the cross product of two adjacent vectors. If I walk around the perimeter of the polygon my head points out of the plane. I cross the out of plane vector into my walking direction vector to get the third direction in my coordinate system. If that vector points so that the interior is on my left it's counterclockwise; if the interior is on my right it's clockwise.

[ReaperUnreal]

Seeing as how the cross product basically boils down to a positive scaling factor times the sine of the angle, it's probably better to just do a cross product. It'll be faster and less complicated.

[Beta]

It's calculus applied to a simple case. (I don't have the skill to post graphics.) The area under a line segment equals its average height (y2+y1)/2 times its horizontal length (x2-x1). Notice the sign convention in x. Try this with some triangles and you'll soon see how it works.

[Beta]

I'd suggest proving it first for a triangle, then showing that any polygon can be split into triangles in a way that doesn't change its "clockwiseness".

[Adam McKee]

Is there a particular name to this method?

[Beta]

Now that I think of it, the method of calculating area using a counterclockwise curve can be derived from Green's Theorem. I saw the method (without derivation) years ago-- I may have come up with idea of using it as a clockwiseness test myself, but it's a pretty obvious jump.

[Vicky Chijwani]

by "center of mass" I think you mean "centroid"?

[the Ritz]

Is there a similar elegant solution for polygons in 3D space?

[the Ritz]

Found it here: stackoverflow.com/questions/12642256/…

[Charles Bretana]

Actually, this solution is a different solution than the accepted solution. Whether they are equivalent or not is a question I am investigating, but I suspect they are not... The accepted answer calculates the area of the polygon, by taking the difference between the area under the top edge of the polygon and the area under the bottom edge of the polygon. One will be negative (the one where you are traversing from left to right), and the other will be negative. When traversing clockwise, The upper edge is traversed left to right and is larger, so the total is positive.

[Charles Bretana]

My solution measures the sum of sines of the changes in edge angles at each vertex. This will be positive when traversing clockwise and negative when traversing counter clockwise.

[agentp]

It seems with this approach you DO need to take the arcsin, unless you assume convexity (in which case you need only check one vertex)

[Michael]

It also generalizes nicely to 3-D polytopes: for each face compute the signed area in x-y plane as described in this answer, multiply by the mean value of z, and sum it up for all faces. The absolute value of the result will be the polytope's volume.

[LarsH]

A minor caveat: this answer assumes a normal Cartesian coordinate system. The reason that's worth mentioning is that some common contexts, like HTML5 canvas, use an inverted Y-axis. Then the rule has to be flipped: if the area is negative, the curve is clockwise.

[Mr.Qbs]

This method is wrong! I implemented it ad is works in 98% cases. But not always. What worked for me (in every case) is this link.

[Beta]

@Mr.Qbs: Please give us the simplest counterexample you know.

[Mr.Qbs]

I checked my implementation to show you that it's properly done and to give you counterexample. Then I saw your coment "I'd suggest proving it for a triangle" so I tried it and it works! When i have 3 points (2 edges of my big polygon) I need to calculate 3 edges to get properly result (ab, bc, ca - imaginary edge). But when I try it only for 2 "real" edges (that realy belongs to my polygon) result sometimes is bad (its hard to give example - i compute 3d objects and I can see the bad arc quickly on modified model - sometimes arc is made in bad direction).

[Beta]

@Mr.Qbs: So my method works, but if you skip a vital part, then it doesn't work. This is not news.

[Charles Bretana]

No, you do not need to take the arcsine. You do need to divide by the magnitudes of the two vector, to eliminate scaling, (where one very large pair od segments that bends one way a small angle contributes more tot the sum than many smaller segments that bend the other way by a larger angle. But the arcsine just converts one measure of an angle to another.

[Michael Macha]

Was that a typo in your signed area formula above? It ends with "xn*y1 - x1*yn"; when I believe it should be "x_n y_{n+1} - y_n x_{n-1}" (in LaTeX, at least). On the other hand, it's been ten years since I took any linear algebra classes.

[Sean the Bean]

Nope. If you check the source, you'll see that the formula does in fact reference the first point again in the last term (y1 and x1). (Sorry, I'm not very familiar with LaTeX, but I formatted the subscripts to make them more readable.)

[M Katz]

This is also explained in en.wikipedia.org/wiki/Curve_orientation. The point is that the the found point must be on the convex hull, and it's only necessary to look locally at a single point on the convex hull (and its immediate neighbors) to determine the orientation of the whole polygon.

[Olivier Jacot-Descombes]

@Mr.Qbs: You always have to link the last point to the first one. If you have N points numbered from 0 to N-1, then you must calculate: Sum( (x[(i+1) mod N] - x[i]) * (y[i] + y[(i+1) mod N]) ) for i = 0 to N-1. I.e., must must take the index Modulo N (N ≡ 0) The formula works only for closed polygons. Polygons have no imaginary edges.

[Dan M.]

Can the result be zero? And if it can, then what orientation is it? (It looks like some special cease).

[Beta]

@DanM. If the result is zero, that means that the positive and negative areas cancel out, as in a figure-eight.

[Dan M.]

Btw, It seems you only need to calculate sum of x<sub>i + 1</sub>*y<sub>i</sub> - x<sub>i</sub>*y<sub>i + 1</sub> to determine the answer.

[Beta]

@DanM.: True, but notice that my formula has only one multiplication, while yours has two.

[Matt Fiocca]

I'm trying this out with a clockwise diamond, and getting a negative (counter-clockwise) sum result, and a positive sum for counter-clockwise. CLOCKWISE DIAMOND: point[0] = 0,5 (5-0)(0+5) = 25, point[1] = 5,0 (10-5)(5+0) = 25, point[2] = 10,5 (5-10)(5+10) = -75, point[3] = 5,10 (0-5)(10+5) = -75 == -100. COUNTER DIAMOND: point[0] = 0,5 (5-0)(5+10) = 75, point[1] = 5,10 (10-5)(10+5) = 75, point[2] = 10,5 (5-10)(5+0) = -25, point[3] = 5,0 (0-5)(5+0) = -25 == +100 Is this a special case?

[Beta]

@MattFiocca: You are using the words "clockwise" and "counter-clockwise" in the opposite sense of everyone else.

[Matt Fiocca]

@Beta: just so i'm not going crazy, is everyone else using clockwise as counter-clockface? Here's a link to my diagram with calculations. s3-us-west-2.amazonaws.com/mattfiocca/polydirection.png.

[Beta]

@MattFiocca: The convention in mathematics is that the Y coordinate increases upward; your Y coordinates increase downward.

[Matt Fiocca]

@Beta: ah thanks! I knew I was missing something vital, having come from the backward world of web and apps.

[Sreeraj]

This works only with all positive co-ordinates. I tried with Polygons in X,-Z Plane (all Z values are negative in this case.). Only way I could get this logic to work in this case is by translating the polygons to X,+Z plane. i.e, by offsetting the Z values of all co-ordinates with a constant such that all values are positive. Please correct me if am wrong or if there is any simpler alternative.

[Beta]

@Sreeraj: You are mistaken, but a comment thread is not the place to discuss it. If I have time I'll make a chat room.

[David Zorychta]

This blog.element84.com/polygon-winding.html explains in simple english why this solution works.

[Cecil Curry]

Shocked and awed this hasn't received more upvotes. For simple polygons (which is most polygons in some fields), this answer yields an O(1) solution. All other answers yield O(n) solutions for n the number of polygon points. For even deeper optimizations, see the Practical Considerations subsection of Wikipedia's fantastic Curve orientation article.

[Cecil Curry]

Clarification: this solution is O(1) only if either (A) this polygon is convex (in which case any arbitrary vertex resides on the convex hull and hence suffices) or (B) you already know the vertex with the smallest Y coordinate. If this is not the case (i.e., this polygon is non-convex and you don't know anything about it), an O(n) search is required. Since no summation is required, however, this is still dramatically faster than any other solution for simple polygons.

[RunninglVlan]

Alternatively it can be calculated as sum of (point.x + nextPoint.x) * (point.y - nextPoint.y).

[marsbear]

Why all the expensive math functions? Wouldn't it be faster to only calculate the z-part of a 3D cross product by doing a1 * b2 - a2 * b1 (as the x- and y-parts will be zero anyway) and checking the sign of the result? No trigonometric functions are needed and no sqrt.

[Charles Bretana]

@marsbear, That will only work if all vectors are the same magnitude (or, equivalently, have first been normalized). If they are of different lengths, then you will get the wrong answer., because a clockwise angle between two long segments of the polygon will contribute much more to the overall sum than a counterclockwise angle between two very small segments.

[marsbear]

But shouldn't it be enough to "add up" the signs of the cross products?

[Charles Bretana]

No, all that would do is "count" the number of turns to the right minus the number of turns to the left. If you start pointing East, and take ninety one degree turns to the right, (totaling 90 degrees of right), each an inch long, you will be pointing south, and then take five 90 degree turns to the left, you will be pointing east again, and with appropriate adjustment of the length of each segment, (make the lefts longer) reconnect to the start point. The overall closed curve is clearly counterclockwise, but just counting the signs would count 90 to the right and only 5 to the left.

[nbro]

I have reformulated your answer (to make it more precise mathematically) until your sentence "The magnitude of this value is a measure of the sine of the angle between the 2 original vectors". You should edit that sentence and the remaining ones to take into account my changes. The reason I didn't edit that sentence and the remaining ones is that I am not fully understanding what you mean those.

[nbro]

Can you specify which other answers exactly this answer is based on?

[nbro]

@tibetty Can you explain why this method wouldn't work in many situations if the polygon is concave?

[MSS]

Openlayers is javascript based map management library like googlemaps and it's wrote and used in openlayers 2.

[nbro]

Can you explain a little bit what your code does, and why you're doing it?

[tibetty]

Please look at the last table in the wiki item reference in your post. It's easy for me to give a false example but hard to prove it.

[tibetty]

Please look at the last table in the wiki item reference in your post. It's easy for me to give a false example but hard to prove it.

[Sandy Gifford]

Would this work for lat/lon coordinates assuming you're not near/crossing a pole, and all polygons that cross 180 are defined with numbers greater than 180?

[Luke Hutchison]

You DO need to take the arcsin. Try it on a bunch of random non-convex polygons, and you will find the test will fail for some polygons if you don't take the arcsin.

[Charles Bretana]

No, You don't. Whatever test you are running, you are running it wrong. The value before taking the arcsine IS the sin of the original angle of rotation, converting it from a value between -1 and +1 to an actual angle between -Pi and +Pi does nothing to change the answer. And as long as you divide by the product of the magnitudes of the two vectors, the magnitudes will be normalized, and their sum will indicate the overall direction of curvature.

[Cameron Roberts]

Trying this I get exactly the opposite result, a polygon drawn in clockwise order yields a negative area, while one drawn counter clockwise yields positive. In either case, this snippet is still super useful 5yrs on, thank you.

[Ans]

@Macmee: the link given by you is broken, archive: web.archive.org/web/20171212175910/blog.element84.com/…

[Brian Carcich]

Ah, with a clever approach that cancels the extra XnYn terms over the sum, this is a cross product. Sweet!

[Eric Fortier]

I used this solution and it worked perfectly for my use. Note that if you can plan ahead and spare and extra two vectors in your array, you can get rid of the comparison (or %) by adding the first vector at the tail of the array. That way you simply loop over all the elements, except the last one (length-2 instead of length-1).

[ToolmakerSteve]

@CharlesBretana - while I have not run Luke's test, I believe he is correct. That is the nature of summing combined with a nonlinear scale [without arcsin vs. with arcsin]. Consider what marsbear suggested, that you correctly rejected. He suggested that you "just count", and you pointed out that a handful of large values could outweigh a large number of small values. Now consider arcsin of each value vs not. Isn't it still the case that failing to take arcsin gives incorrect weight to each value, therefore has same flaw (though much less so)?

[ToolmakerSteve]

@EricFortier - FWIW, rather than resize a possibly large array, an efficient alternative is for each iteration to save its point as previousPoint for next iteration. Before starting loop, set previousPoint to array's last point. Trade off is extra local variable copy but fewer array accesses. And most importantly, don't have to touch the input array.

[ToolmakerSteve]

@MichaelEricOberlin - its necessary to close the polygon, by including the line segment from last point to first point. (A correct calculation will be the same, no matter which point starts the closed polygon.)

[ToolmakerSteve]

@tibetty is correct. You can't simply take any three points along the polygon; you might be in either a convex or concave region of that polygon. Reading wiki carefully, one must take three points along the convex hull that encloses the polygon. From "practical considerations": "One does not need to construct the convex hull of a polygon to find a suitable vertex. A common choice is the vertex of the polygon with the smallest X-coordinate. If there are several of them, the one with the smallest Y-coordinate is picked. It is guaranteed to be [a] vertex of the convex hull of the polygon."

[ToolmakerSteve]

Hence lhf's earlier answer, which is similar, and references the same wiki article, but specifies such a point. [Apparently it doesn't matter whether one takes smallest or largest, x or y, as long as one avoids being in the middle; effectively one is working from one edge of the bounding box around the polygon, to guarantee in a concave region.]

[ToolmakerSteve]

Maybe this works if the polygon is entirely convex. It definitely is not reliable if there are any concave regions - its easy to pick a point that is on the "wrong" side of one of the edges of the cave, then connect it to that edge. Will get wrong answer.

[ToolmakerSteve]

Probably works if polygon is entirely convex. But better to instead use an answer that will work for non-convex polygons.

[ToolmakerSteve]

True, but you misunderstand the concept of a polygon's winding order (clockwise or counter-clockwise). In an entirely convex polygon, the angle at all points will be clockwise or all will be counter-clockwise [as in your first sentence]. In a polygon with concave region(s), the "caves" will be in the opposite direction, but the polygon as a whole still has a well-defined interior, and is considered clockwise or counter-clockwise accordingly. See en.wikipedia.org/wiki/…

[ToolmakerSteve]

IMHO, it would be safer to stick to the fundamental math shown in lhf's answer - thank you for mentioning him. The challenge in reducing it to quadrants is that its a fair amount of work to prove that your formula is correct in all cases. Did you correctly calculate "more west"? In a concave polygon where both [1] and [3] are "west and south" of [2]? Did you correctly handle different lengths of [1] and [3] in that situation? I have no idea, whereas if I directly compute that angle (or its determinant), I'm using well-known formulas.

[VectorVortec]

@ToolmakerSteve the if statements always work if the 3 points are convex. The if statements will return, then you'll get the right answer. The if statements will not return, if the shape is concave and extreme. That's when you have to do the math. Most images have one quadrant, so that part is easy. More than 99% of my subroutine calls are handled by the if statements.

[ToolmakerSteve]

That doesn't address my concern. What is that formula? Is it the orientation determinant as given in the wiki link from lhf's answer? If so, then say so. Explain that what you are doing is doing quick checks that handle most cases, to avoid the standard math. If that is so, then your answer now makes sense to me. (Minor nit: would be easier to read if you used .x and .y of a struct, instead of [0] and [1]. I didn't know what your code was saying, first time I glanced at it.)

[ToolmakerSteve]

An implementation of this answer: c# code to find corner vertex and calculate determinant of angle at that vertex.

[ToolmakerSteve]

Since I did not have confidence in your approach, I implemented lhf's approach; formula from his link. Slow part is finding appropriate vertex - O(N) search. Once found, the determinant is an O(1) operation, using 6 multiplies with 5 adds. That last part is what you've optimized; but you've done so by adding additional if-tests. I can't personally justify taking a non-standard approach - would need to verify each step is correct - But thank you for an interesting analysis of quadrants!

[Venkata Goli]

It works even if the polygon is concave. The point needs to be inside that concave polygon. However I am not sure about complex polygon (did not test.)

[ToolmakerSteve]

"It works even if the polygon is concave." - Counterexample: poly (0,0), (1,1), (0,2), (2,2), (2,0). Line segment (1,1), (0, 2). If you pick an interior point within (1,1), (0,2), (1,2) to form triangle -> (1,1), (0,2), (0.5,1.5)), you get opposite winding than if you pick an interior point within (0,0), (1,1), (1,0) > (1,1), (0,2),(0.5,0.5). Those are both interior to the original polygon, yet have opposite windings. Therefore, one of them gives the wrong answer.

[ToolmakerSteve]

In general, if a polygon has any concave region, pick a segment in the concave region. Because it is concave, you can find two "interior" points that are on opposite sides of that line. Because they are on opposite sides of that line, the triangles formed have opposite windings. End of proof.

[Warwick Allison]

This appears to be for down-is-positive Y coordinates. Flip CW/CCW for standard coordinates.

[Eric Fortier]

@ToolmakerSteve - Good point. Unless you know the size beforehand and can create the array with the extra element, your solution is fast and prevents resizing.

[allez l'OM]

@CameronRoberts The norm (see IETF in particular for geoJson) is to follow the 'right-hand rule'. I guess that Google is complaining with. In that case outer ring must be counterclockwise (yielding positive area), and inner rings (holes) are winding clockwise (negative area to be removed from main area).

[allez l'OM]

@nbro this code implements the lhf answer. It is easy to keep the non OpenLayer part in a pure javascript function by having vertices directly as parameter. It works well, and could be adapted to the case of multiPolygon.

[Chanwoo Park]

@LarsH unless it's Y coordinate is inverted resulting in a negative Y value, wouldn't positive sum of edges still means the polygon is clockwise?

[LarsH]

@ChanwooPark: Good question. I can see why that might appear to be the case, since y1 + y2 wouldn't change sign just from inverting the direction of the y axis. But I don't think so. Try it for a simple triangle. (I don't have time to try it now.)

[LarsH]

Ok I tried it with the example given in the answer. If you flip the y-axis to go from 5 to 0 instead of 0 to 5, you end up with 45 instead of -44. So no, a positive sum doesn't mean the polygon is clockwise, when the y-axis is flipped.

[LarsH]

@ChanwooPark Think of how the algorithm works: if edges that go leftward (x2 < x1) have higher y-values overall than edges that go rightward (x2 > x1), the negative terms will outweigh the positive, and in a Cartesian coordinate system this means the polygon goes counterclockwise.

[LarsH]

Whereas in an inverted y-coordinate system, edges that would have had higher y-values than the others now have lower y-values. So for a counterclockwise polygon, the leftward edges now have lower y-values, and the positive terms of the rightward edges will outweigh them, producing a positive result.

[Chanwoo Park]

@LarsH Thx for the answer it helped me alot

[LarsH]

@ChanwooPark Thx for the question. I hadn't really understood the algorithm until you provoked me to think it thru.

[LarsH]

@CecilCurry I think your 2nd comment explains why this hasn't received more upvotes. It yields wrong answers in certain scenarios, without any mention of those limitations.

[stenfeio]

Can this be generalized to 3 dimensions, x, y, z?

[Beta]

@stenfeio: Yes, but you must think carefully about what "clockwise" means in 3D. If you don't see how, you can post ta Question; it's too much to add to this one.

[stenfeio]

@Beta, posted here: stackoverflow.com/questions/66226478/…

[Michel Rouzic]

You can avoid the costly % and avoid branching too by setting v1 = vertices[vertices.Count-1] before the loop starts, use v2 = vertices[i]; then after the addition to the sum do v1 = v2.

[WDUK]

@MichelRouzic how is (i+1) % (count-1) a branch isn't that just a math operation for the next index? Why would this involve branching ?

[Michel Rouzic]

It took me some time to remember what I meant by this, it's not branching, I meant that if anyone tried to do something like (i+1) % (count-1) without % they'd go for something like i+1 < count ? i+1 : 0 like this answer for instance, when there's a way that avoids both modulo and branching.