python - 在 PyGame 中获取图形轮廓作为多边形

Question

我有一种感觉，这是不可能的(或者至少非常复杂)，但我目前有一个生成的图表，看起来像这样(请原谅我糟糕的绘画技巧):

现在，我希望能够创建轮廓的多边形，我有所有节点的坐标，但没有交点。到目前为止，我能管理的最好的方法是礼品包装算法，它比其他任何算法都更能提供多边形的粗略轮廓。

有人对我如何解决这个问题有任何想法吗？

(我目前正在使用 PyGame)

Answer 1

您需要找出交叉点发生的位置并在那里创建新节点。

然后您想要找到位于外多边形上的边。我建议从无穷远处运行随机光线，直到它到达边缘。

然后想象你自己沿着那条边缘行走，左手放在边界上，右手放在外面。开始步行。

当你碰到一个节点时，你会转弯，这样你就不会越过任何边缘。也就是说，您开始按逆时针顺序遍历下一条边。 (一个简单的实现是使用 atan2() 按方向对它们进行排序。)

这都是基础的高中代数和三角学，但如果这是您第一次编写这种性质的东西，可能会有点粗糙。不过，你会学到很多东西。