您可以通过绕过所有边缘并检查下一个边缘始终沿相同方向(左/右手)移动来测试形状为凸包的形状.这是一种快速而廉价的算法.这里有一个实现:en.wikipedia.org/wiki/Graham_scan
如果您没有凸包,请执行包裹算法以获得包含所有点的凸包(再次非常快).en.wikipedia.org/wiki/Gift_wrapping_algorithm
现在,寻找你的形状上的点,但不在凸包上.对于这些点的每次运行,从这些点创建一个新形状(加上凸包的两侧).
递归现在是你的朋友:对刚刚制作的每个子形状执行完全相同的处理.
我已经使用这种技术测试一个包含在任意形状内的点:即该点必须在凸包内(易于测试),但不是任何子形状,或它们的子形状,或它们的子-shapes ....