python - 删除直线中多余的点

Question

我正在研究一种算法，该算法可以在简单的黑白 map 中分析大陆的形状，并返回其周长的轮廓。

示例如下:[(1,0)、(2,0)、(2,1)、(2,2)、(3,2)...]

到目前为止，算法生成了正确的列表，但正如您所看到的，它生成了冗余点。

在该示例中，第一个点之后的 3 个点形成一条直线，从 2,0 到 2,2。 (2,1)，冗余点，应该被消除，但我不知道如何消除。

仅供引用:我正在一个纯Python应用程序中工作，我使用的唯一库是pygame。我研究过类似的问题，但没有运气。

Answer 1

3 点 (x₁,y₁), (x₂,y₂), 以及(x₃,y₃) 共线(在一条线上)如果:

(x₂-x₁)(y₃-y₂) - (y₂-y₁)(x₃-x₂) = 0

当轮廓中连续 3 个点共线时，中间的点就是多余的，可以将其删除。

您可以在向列表添加点时逐步执行此操作。如果列表中至少有 2 个点，则在添加另一个点之前，检查它是否与最后 2 个点共线。如果是，则删除最后一个点，然后再添加新的点。

完成后，检查起点和终点是否多余，如果多余则将其删除。