标签: closest-points

我有一个二维数组:

MyArray = array([6588252.24, 1933573.3, 212.79, 0, 0],
                [6588253.79, 1933602.89, 212.66, 0, 0],
                 etc...)

前两个元素MyArray[0],并MyArray[1]是X和Ÿ点的坐标.

对于数组中的每个元素,我想找到以半径X单位返回其单个最近邻居的最快方法.我们假设这是在2D空间.

让我们说这个例子X = 6.

我通过将每个元素与每个其他元素进行比较来解决问题,但是当列表长度为22k点时,​​这需要15分钟左右.我们希望最终在大约3000万点的名单上运行.

我已经阅读了关于Kd树并了解基本概念,但却无法理解如何编写脚本.

是否有一种已知的,有效的算法,用于在云中找到最接近的三个点组？

这类似于最接近的一对点问题,但我正在寻找三点而不是两点.

编辑
"最接近"的定义将影响算法的复杂性.正如杰克指出的那样,找到最小面积三角形是3sum-hard,并且在任何情况下都不适合我的应用.

我希望有一个更有效的算法来找到最小的perimiter(即| AB | + | AC | + | BC |)三角形或类似的东西(例如最小| AB |²+ | ​​AC |²+ | ​​BC |².我知道没有理由为什么这应该是3sum-hard,因为其他地方存在3个共线点不会影响结果.

注意:我的点有八个维度,因此任何限制为较少维度的算法都不合适.

我有两个包含时间序列(unix时间戳)的numpy数组.
我想找到一对时间戳(每个数组1个),它们的差异在一个阈值内.

为了实现这一点,我需要将两个时间序列数据对齐成两个数组,这样每个索引都有最接近的对.(如果数组中的两个时间戳同样接近另一个数组中的另一个时间戳,我不介意选择任何一个,因为对的数量比实际值更重要.)

因此,对齐的数据集将具有两个相同大小的数组,另外一个较小的数组将填充空数据.

我在考虑使用timeseries包和align功能.
但我不确定如何使用对齐我的数据这是一个时间序列.

示例考虑两个时间序列数组:

ts1=np.array([ 1311242821.0, 1311242882.0, 1311244025.0, 1311244145.0, 1311251330.0, 
               1311282555.0, 1311282614.0])
ts2=np.array([ 1311226761.0, 1311227001.0, 1311257033.0, 1311257094.0, 1311281265.0])

输出样本:

现在ts2[2] (1311257033.0),它最接近的一对应该是ts1[4] (1311251330.0)因为差异在于5703.0,threshold它是最小的,并且它是最小的.现在,ts2[2]和ts1[4] 已经配对,他们应该被排除在外的其他计算.

应该找到这样的Pairs,因此Output数组可能比实际数组长

abs(ts1 [0] -ts2 [0])= 16060
abs(ts1 [0] -ts2 [1])= 15820 //对
abs(ts1 [0] -ts2 [2])= 14212
abs(ts1 [0 ] -ts2 [3])= 14273
abs(ts1 [0] -ts2 …

我试图用分而治之的方法在Python中实现最接近的配对问题,一切似乎工作得很好,除了在某些输入情况下,有一个错误的答案.我的代码如下:

def closestSplitPair(Px,Py,d):
    X = Px[len(Px)-1][0]
    Sy = [item for item in Py if item[0]>=X-d and item[0]<=X+d]
    best,p3,q3 = d,None,None
    for i in xrange(0,len(Sy)-2):
        for j in xrange(1,min(7,len(Sy)-1-i)):
            if dist(Sy[i],Sy[i+j]) < best:
                best = (Sy[i],Sy[i+j])
                p3,q3 = Sy[i],Sy[i+j]
    return (p3,q3,best)

我通过递归函数调用上面的函数,如下所示:

def closestPair(Px,Py): """Px and Py are input arrays sorted according to
their x and y coordinates respectively"""
    if len(Px) <= 3:
        return min_dist(Px)
    else:
        mid = len(Px)/2
        Qx = Px[:mid] ### x-sorted left side of P
        Qy = Py[:mid] …

给定二维空间中的点列表,您希望在Haskell中执行一个函数来找到两个最近点之间的距离.示例:输入:项目[(1,5),(3,4),(2,8),( - 1,2),( - 8.6),(7.0),(1.5),(5.5),(4.8 ),(7.4)]输出:2.0

假设列表中两个最远点之间的距离最多为10000.

这是我的代码:

import Data.List
import System.Random

sort_ :: Ord a => [a] -> [a]
sort_ []    =  []
sort_ [x]  =  [x]
sort_ xs   =  merge (sort_ left) (sort_ right)
  where
    (left, right) = splitAt (length xs `div` 2) xs
    merge [] xs = xs
    merge xs [] = xs
    merge (x:xs) (y:ys)=
    if x <= y then 
        x : merge xs (y:ys)
    else  y : merge (x:xs) ys     

project :: [(Float,Float)] -> Float …

我能找到一个点之间的距离MyPoint和多边形MyPolygon与

double dist = boost::geometry::distance(MyPoint, MyPolygon)

显然,MyPolygon必须在某处计算实际的最近点.有没有一种简单的方法来获得最接近的点？我在Boost文档中找不到任何内容,我确信其他人也有这个问题.

谢谢

我试图实现这个算法的更简单版本,但它比二次算法更好.我的想法主要是只用x坐标对点进行排序,并尝试从那里解决它.一旦我按x坐标对点阵列进行排序,我想迭代数组,基本上跳过距离大于我前两点的点.

例如,我的currentminDist = x;

如果我正在观察的两对点的距离> x(仅通过其x coord dist),我忽略该点并在数组中移过它.

我有这个想法,但我有点坚持如何实际实现这一点(特别是条件部分).我有一个函数,它根据x坐标返回两点之间的距离.

我很困惑如何实际为我的循环写我的条件因为我想忽略一个点,如果距离恰好太远并仍然填写我的数组,其中将包含每个i的最近点的答案(我是当前点我在看).

任何提示或方向将不胜感激.我对编码算法知之甚少,所以非常令人沮丧.

这是我的代码的一部分:

for (i = 0; i < numofmypoints; i++)
        {
            for (int j = i + 1; (j < numpofmypoints) && ((inputpoints[j].x - inputpoints[i].x) < currbest); j++ )
            {
                currdist = Auxilary.distbyX(inputpoints[i],inputpoints[j]);

                if (currdist < bestdist) 
                {
                 closest[i] = j;
                 bestdist = currdist;

                }
            }
        }

distbyX是我的函数,只返回两点之间的距离.

谢谢!

我知道这可能是重复的,但它似乎是"最近点对"算法的变体.

给定单位平方中的一组N个点(x,y)和距离d,找到所有点对,使得它们之间的距离最多为d.

对于大N,蛮力方法不是一种选择.除了"扫描线"和"分而治之"的方法,还有一个更简单的解决方案吗？这对点是无向图的边缘,我需要遍历它并说它是否连接(我已经使用DFS做过,但是当N = 100万时它永远不会完成!).

欢迎任何伪代码,评论或想法,谢谢!

编辑:我在Sedgewick上发现了这本书(我正在查看代码):

当N足够大时,程序3.18使用链接列表的二维数组来将程序3.7的运行时间提高约1/d2.它将单位正方形划分为大小相等的网格.然后,对于每个方格,它构建一个落入该方格的所有点的链表.二维阵列提供了立即访问靠近给定点的点集的能力; 链表提供了灵活性,可以存储它们可能落下的点,而不必提前知道每个网格方格中有多少点.

我有两组 2D 点，它们在平面上被一条线分开。我想有效地找到一对点，​​由每组中的一个点组成，它们之间的距离最小。Radu Litiu 有一篇非常方便的论文，Closest Pair for Two Independent Sets of Points，但它使用 L1（曼哈顿）距离度量而不是欧几里得距离。

有谁知道适用于欧几里德距离的类似算法？

我几乎可以看到标准分而治之最接近对算法的扩展——用垂直于原始分割线的中线将两个集合分开，在两侧递归，然后寻找由一个点组成的更接近对中位数的每一边。如果到递归步骤的最小距离是 d，那么中位数一侧的点的伴星必须位于尺寸为 2d*d 的盒子内。但与原始算法不同，我看不到任何方法来限制该框内的点数，因此整个算法就变成了 O(m*n)。

有任何想法吗？

我想将一个数组中的点与另一个数组中的点进行比较并找到最接近的一对。到目前为止，我遇到的都是单个数组。我不想比较同一数组中的点。暴力算法可以工作，但速度太慢。是否有使用分而治之方法的算法或实现？

编辑1：点被定义为地球表面上的一对（纬度，经度）。

我正在努力解决分裂和征服算法如何适用于大于2的维度,特别是如何在两个子问题之间找到最接近的点对.

我知道我只需要考虑轴上d两者之间距离的距离x.

我知道在3d情况下,我需要将每个点与仅15个其他点进行比较.

我不明白的是如何选择那15分.在第二种情况下,只需按值对值进行排序,y然后按顺序进行排序.但是,在3d情况下,需要将每个点y 与 z轴和轴上最接近它的15个点进行比较.我似乎无法找到一种方法来确定那些15点是什么样的,没有最坏的情况O(n^2)......

我在这里错过了什么？

我有n个不等大小的排序列表(我事先不知道将会有多少列表).我需要找到每个列表中一个元素之间的最小平均距离.

例如,对于三个列表,给定n = 3:

a = [14, 22, 36, 48]
b = [14, 23, 30, 72]
c = [1, 18, 24]

输出应为(22,23,24),因为:

mean(abs(22-23), abs(23-24), abs(22-24)) = 1.33333

这是上例中所有点中最小的一个.

我尝试在Python中实现它如下

def aligner(aoa):
'''
read arrays of arrays of peaks and return closest peaks
'''
#one of arrays is empty
if not [y for x in aoa for y in x]:
    return None
# there is the same nr in all array no need to do anything
candidate = set.intersection(*map(set, aoa))
if …

现在我正在整个图上执行Dijkstra算法,并通过距离原点节点的总距离形成节点的最小堆.然后我从堆中删除前n个元素.

这让我感到非常低效.假设我需要找到10个最近的节点,我的图表有超过100000个节点.然后在整个图表上执行Dijkstra似乎是浪费时间.但问题是我不确定我能找到前10个最近的节点而不计算图中每个节点的最短路径.

有没有更好的办法？