确定周围特定点的边界多边形

Question

我一直在尝试弄清楚如何从另一组点（集合B）确定特定点（集A）周围的界限多边形，以便多边形仅包含集合A中的点A中的点。为简单起见，我们可以假设多边形将是凸，设置A仅包括2分，并且从给定数据中存在解决方案。

例如，给定：这些要点，我想从这样的红点围绕蓝点创建一个多边形。这可以通过以最大的角度找到下一个点，而不会切入蓝色点来完成这一点，但是我不希望结果太小。

解决此问题的任何建议或算法？

Answer 1

似乎是，如果您在所有（红色和蓝色）点上计算三角剖分，则包含蓝色顶点的三角形，形成所需区域的第一个近似值。这种近似通常会凹入，因此需要切断"耳朵"。

如果结果看起来太小，则可以添加外边界三角形的第三个顶点，如果它们不违反凸。