在Python中有效操纵笛卡尔坐标列表 [英] Efficient manipulation of a list of cartesian coordinates in Python

问题描述

我正在编写一个程序，该程序处理与各种规则形状的顶点网络有关的大量数据.我有一个工作生成器，它根据用户输入参数的范围生成与所述形状的顶点相对应的笛卡尔坐标的列表.然后将数据传递到筛选器，筛选器将清除重复的条目，对数据进行排序和其他各种功能，然后将清除的数据从这些数据馈送到画布模块，该模块循环并绘制顶点.

I'm writing a program which handles large quantities of data related to the networks of vertices of various regular shapes. I have a working generator which produces a list of cartesian coordinates corresponding to the vertices of said shapes based on a range of user input parameters. The data is then passed to filters which clear up duplicate entries, sort the data and various other functions, from where the cleaned data is fed to a canvas module which loops through and draws the vertices.

我需要实现一个新的过滤器，该过滤器可以有效地遍历坐标，将每对与其他对(即(x1,y1)-> (x2,y2)与(x1,y1)-> (xn,yn)，(x2,y2)-> <所有条目的c5>到(x2,y2)-> (xn,yn)等，例如，如果(x1,y1)和(x5,y5)之间的关系适合[(x5-x1)^2+(y5-y1)^2]=vertex_spacing^2，则然后将两组坐标与它们各自的列表配对条目号并附加到新列表中，其中一个条目的形式为:[(x1,y1), (x5,y5), 0, 4].最有效的方法是什么?

I need to implement a new filter that efficiently loops through the coordinates, comparing each pair against every other pair, i.e. (x1,y1)->(x2,y2) to (x1,y1)->(xn,yn), (x2,y2)->(x3,y3) to (x2,y2)->(xn,yn) etc. for all entries and, for example, if the relationship between (x1,y1) and (x5,y5) fits [(x5-x1)^2+(y5-y1)^2]=vertex_spacing^2, then the two sets of coordinates are then paired with their respective list entry numbers and appended to a new list where one entry would be of the form: [(x1,y1), (x5,y5), 0, 4] for example. What is the most efficient method for achieving this?

在这里和各种指南中，我已经研究了很多处理列表的方法.我曾尝试嵌套"for"和"if"循环，但是发现这种方法虽然可以工作，但会导致运行时间过长，并试图将问题分解为多个较小的for循环.

I've looked at quite a few methods for handling lists on here and on various guides. I've attempted nested 'for' and 'if' loops, but find while this method can work it leads to excessively long run times, as well as attempting to breaking the problem down into numerous smaller for loops.

此操作的最终目的是将生成的坐标用于前端接口元素，并在需要时进行保存和导入. [(x1,y1), (x5,y5), 0, 4]中列表位置0和4的功能是使界面能够将坐标分组以便以后在画布对象中使用.该方法应该能够处理潜在的数千个坐标.

The ultimate aim of this is to use the resulting coordinates for front-end interface elements, and to be saved and imported as necessary. The function of the list positions 0 and 4 in [(x1,y1), (x5,y5), 0, 4] is to enable the interface to group coordinates for later use in canvas objects. The method should be able to process potentially thousands of coordinates.

在此先感谢您的帮助，我当然愿意改善我提供的措词/信息和/或添加示例代码(如果尚不清楚我在以什么方式询问的内容)-我还是很新的为此！ :)

Thank you in advance for any help, I am of course willing to improve the phrasing/information I've supplied and/or add example code if it is unclear what I am asking in any way- I'm still quite new to this! :)

推荐答案

您基本上要检查的是:

对于每个顶点v，找到所有顶点u，以使u位于半径vertex_spacing围绕v的圆上.

for each vertex v, find all vertices u such that u is on the circle of radius vertex_spacing around v.

如果您的点的分布使得并非所有点都靠得很近，我想到了两种加快搜索速度的方法:

If the distribution of your points is such that not all points are close together, I think of two approaches to speed up the search:

1. 加快此过程的最简单方法是按x坐标对点进行排序.这样，您可以跳过许多比较.作为一个简单的示例，假设x坐标为[1, 2, 10, 15, 18, 20, 21]和vertex_spacing = 5.您只需要将第一个顶点与第二个顶点进行比较，因为所有其他顶点显然都在第一个顶点周围的圆之外.

1. The simplest way to speed up this process would be to sort the points by x-coordinate. That way, you can possible skip many comparisons. As a simple example, assume that the x-coordinates are [1, 2, 10, 15, 18, 20, 21] and vertex_spacing = 5. You only need to compare the first vertex with the second one, because all the other vertices are obviously outside the circle around the first vertex.

请注意，如果所有点都靠在一起，则此方法无用.换句话说，如果为vertex_spacing = 25，则不能跳过任何比较.

Note that this approach is useless if all points are close together. In other words, if vertex_spacing = 25, you cannot skip any comparison.

沿着同一行，您可以使用二维 k-d树.这等效于排序方法，但在二维上.给定顶点(x, y)和vertex_spacing = v，您将必须检查范围([x-v, x+v], [y-v, y+v])中的所有点.使用与之前相同的示例，假设第一个点的坐标为(1, 0)，第二个点的坐标为(2, 10)，则无需将第一个顶点与任何坐标进行比较.

Along the same lines, you could use a 2-dimensional k-d tree. This is equivalent to the sorting approach, but in two dimensions. Given a vertex (x, y) and vertex_spacing = v, you would have to check all points in the range ([x-v, x+v], [y-v, y+v]). Using the same example as before, assume the first point had coordinates (1, 0) and the second one (2, 10), there would be no need to compare the first vertex to anything.

这两种方法都是启发式的，在最坏情况下的运行时间上没有任何改进(非常相反:您还具有排序/构建kd树的开销)，但是如果顶点通常至少为vertex_space此外，这可以大大加快您的搜索速度.

Both approaches are heuristics and do not give any improvements on the worst-case running time (quite contrary: you also have the overhead of the sorting / building the k-d tree), but if the vertices are typically at least vertex_space apart, this could speed up your search a lot.

这篇关于在Python中有效操纵笛卡尔坐标列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！