CODEWITHSUNDEEP
mathgeometry2dpolygon
Dylbert
Dylbert

Reputation: 57

How do you find the concavity of all points in a concave polygon?

I have an array of vertices that together form a polygon which can either be a convex or concave polygon. Each vertex obviously has x and y values. Knowing the leftmost vertex (which as I understand would always be a concave point), how can I iterate through the remaining points to determine whether each is convex or concave?

Upvotes: 0

Views: 181

Answers (1)

Gene
Gene

Reputation: 47020

A leftmost point must be convex.

Call that vertex V, the previous one is U and the next one is W.

Find the vectors a = U - V and b = W - V. Now compute z = ax * by - ay * bx and note the sign of z.

(This is the z component of the cross product [a 0] X [b 0]. The sign says whether going from U to V to W is a "left turn" or "right turn" in the 2D plane.)

Then continue around the polygon. At each vertex do the same computation where V is the current vertex, U the previous one, and W the next. If the result has the same sign as the first, it's concave, else convex.

Upvotes: 2

Related Questions