凹面和凸面多边形-将任意多边形变成凸面多边形 [英] Concave and Convex Polygon - Turn arbitrary polygon into a convex polygon

问题描述

如何识别并删除图像中绘制的这四个红色点

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?

推荐答案

使用凸包算法(例如 Graham扫描)，然后删除所得凸包中不部分的所有点.

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

在您的示例中，凸包将由P1，P2，P3，P5，P7，P8，P9，P11，P12，P13，P14，P15，P16，P18组成，除了红色的点

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.

请注意，仅删除内角大于180的那些点并不一定会导致凸多边形.以这个多边形为例:

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:

这篇关于凹面和凸面多边形-将任意多边形变成凸面多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！