Concave and Convex Polygon - Turn arbitrary polygo

问题:

How can I identify and remove those four RED points drawn in image

Those four points make that polygon a concave polygon that’s why I want to remove it.

My goal is to convert concave polygon to convex by removing this kind of point by identifying and removing those points.

Is there any way to identify and remove these kind of points?

回答1:

Use a convex hull algorithm (such as the Graham scan), and remove all points that are not part of the resulting convex hull.

In your example, the convex hull will consist of P1, P2, P3, P5, P7, P8, P9, P11, P12, P13, P14, P15, P16, P18, which are precisely all points except the red ones.

---

Note that simply removing those points whose inner angle is greater than 180 will not necessarily result in a convex polygon. Take this polygon for example:

回答2:

aioobe has it right—you sound as though you are looking to compute the convex hull of your polygon, in which case you want one of the convex hull algorithms like Graham scan or Chan's algorithm.

However, if you just want to know whether an angle is convex or concave there's a quick way to compute this that avoids trigonometry.

If A, B, and C are consecutive vertices going clockwise around the polygon, then the vertex at B is convex if

(B − A)^⟂ · (C − B) < 0

Here V^⟂ is a vector that's V rotated by 90° anti-clockwise, which can be computed like so: (x, y)^⟂ = (−y, x).

回答3:

You can detect concave points by looking at the interior angle — if it's greater than a half circle then the point is concave. Indeed they're usually called reflex points because the interior angle is reflex.

A quick way to check is the dot product. For example, look at the three points P14, P15, P16. P16 is behind the line that the segment between P14 to P15 lies on (ie, the dot product of the vector from P15 to P16 with the normal to that line is negative), so P15 is a convex point.

P18 is in front of the line that the segment from P16 to P16 lies on (ie, the dot product of the vector from P17 to P18 with the normal of that line is positive), so P17 is a reflex point.

In 2d, the normal of the line is as simple as flipping the x and y coordinates and negating one.

However, what I think you might want is the convex hull — consider whether there might be convex points that nonetheless create a concave hull. The most obvious example is if I left P17 where it is but moved P18 and P16 even further into the shape, behind it. If so then you want to check out convex hull algorithms.

回答4:

I am guessing you have the coordinates for the points (P1, P2, etc.). You can get the angle generated between each three points and remove it if it is less than 180. For figuring out the angle, check How to calculate an angle from three points?