我在图片中有多个点。垂直方向最近的两个点之间的距离(在A
和B
、或B
和C
、或D
等之间E
)是distance_y
。两个最近点之间的水平距离(在A
和之间D
等)为distance_x
。
假设:
distance_y < distance_x < 2*distance_y
distance_x
A <-------------> D <-------------> G
|
distance_y |
|
B <-------------> E <-------------> H
-
C <-------------> F <-------------> I
我将任意两点之间的距离公式化如下:
Distance(point P1, point P2) = m * distance_x + n * distance_y
例如,对于点A
and B
,m = 0
和n = 1;
问题是:从一个点开始P
,我怎样才能通过最近的邻居首先遍历所有剩余的点(即按远离点的距离降序排列P
)?
我不想计算从其他点到的整个距离P
,然后按距离的降序对这些点进行排序,P
因为这很耗时。我想寻找可以快速评估邻居位置而不计算其他点位置的算法。
例如,从点开始D
,以下几点将是
E (m= 0, n = 1),
A (m= 1, n = 0),
G (m= 1, n = 0),
F (m =0, n = 2),
B (m= 1, n = 1),
H (m= 1, n = 1),
C (m= 1, n = 2),
I (m= 1, n = 2).
如何确定搜索最近邻居的顺序m
和搜索顺序?n