3

给定一个坐标列表，我想知道如何知道另外两个点中间有多少点。

A(1 ; 3)
B(2 ; 2)
C(3 ; 1)
D(3 ; 2)
E(3 ; 3)

这是一个表示：

_______
|A| |E|  
_______
| |B|D|  
_______
| | |C|  
_______

这里 B 和 D 是中点，所以答案是“2”。

我发现了一个非常低效的O(n³)算法。

count := 0
For each point x1  
  For each point x2   
    For each point x3  
      If x3 is the midpoint of [x1;x2] 
        count := count + 1
Print count

您对更有效的算法有任何想法吗？

4

1 回答 1

3

使用kd 树，您可以将其改进为O(n^2 logn)：

将每个点存储在树中，并且对于每一对（其中有O(n^2)），搜索它们中间是否存在一个点（易于计算中间在哪里）。每一次寻求都会O(logn)导致O(n^2 * log(n))解决方案。

如果您只谈论整数，您可能会通过将点放在哈希表中（成对）来增加平均复杂度O(n^2)，并检查是否存在具有所需坐标的元素。

（注意，两种解决方案基本相同，唯一的变化是集合的实现，一种使用树，另一种使用哈希表）。

伪代码：

set <- new set
for each point p:
   set.add(p)
for each point p1:
   for each point p2 != p1:
       candidate <- findMiddle(p1,p2)
       if set.contains(candidate):
           yield (p1,candidate,p2)
于 2013-01-10T19:19:32.707 回答