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

Question

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

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

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

（我目前正在使用 PyGame）

Answer 1

您将要弄清楚交叉点发生在哪里并在那里创建新节点。

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

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

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

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