我怎样才能在一个列表

我有X点的名单中删除太近点，y坐标：我怎样才能在一个列表

List_coord=[(462, 435), (491, 953), (617, 285),(657, 378)]

此列表lenght（这里是4元），可以从几百个非常大的可达35000元素。

我想在此列表中删除太靠近阈值的点。注意：积分不会处于完全相同的位置。

我对于当前的代码：

while iteration<5: 
    for pt in List_coord: 
    for PT in List_coord: 
     if (abs(pt[0]-PT[0])+abs(pt[1]-PT[1]))!=0 and abs(pt[0]-PT[0])<threshold and abs(pt[1]-PT[1])<threshold: 
     List_coord.remove(PT) 
    iteration=iteration+1

我可怕的代码:)解说：

我检查非常距离为0，那么就意味着我感到比较相同点
然后我检查x和y的距离..
迭代：我需要很少的迭代来避免丢失一个删除因为循环内部的列表本身发生变化...

此代码正在工作，但它是一个非常低的过程！

我相信还有另一种方法更容易，但我没能找到，即使一些媒体链接回答问题，是贴近我..

注：我想避免使用额外的库代码如果有可能

来源

2017-09-26 bastoon

如果您先将列表排序（以第一个坐标为关键字），该怎么办？那么你只需要比较那些第一个坐标在你的阈值内的元素。 –

我需要比较两个坐标，因为有些点可以有相同的x或非常接近的x，但不一样的y .. – bastoon

是的，当然。但是在一个排序列表中，你只需要比较很少的元素（而不是像现在这样做的整个列表）。 –

的Python会在这个;-)

你可能会想被称为四树该解决方案有点慢，但我会先提一个简单的方法，在情况下，它优选的。

通常的方法是对点进行分组，以便您可以轻松地拒绝明显彼此远离的点。

一种方法可能是将列表排序两次，一次一次x。你可以证明，如果两点太靠近，它们必须靠近一个维度或另一个维度。因此，你的内在循环可能会提前爆发。如果它看到的点与分选方向上的外点相距太远，则可以知道该列表中的所有未来点都离得太远。因此它不必再看。在X和Y中执行此操作，然后设置！

这种方法将倾向于由O（n log n）排序时间支配。但是，如果所有点都共享一个x值，那么您将最终执行与您现在正在执行的O（n^2）相同的缓慢迭代操作，因为您不会提前终止内部循环。

更可靠的解决方案是使用quadtrees。 Quadtrees旨在解决您正在查看的问题。这个想法是建立一个树，以便您可以快速排除大量的点。我会推荐这个。

如果你的点数太多，我建议你得到一个聚类库。有效的聚类是一项非常困难的任务，通常以C++或其他快速语言完成。

来源

2017-09-26 16:47:28

我怎样才能在一个列表

回答

相关问题