江苏龙网

  1. 首页 > 生活 > >

海量点集 求距离最近的3对点

其他方法：compressed region quadtree, 2D R-tree, ...Sqd You方法实现：typedef pair\u0026lt;double, double\u0026gt; Point;struct Cmp{ bool operator()(const Point \u0026amp;x, const Point \u0026amp;y) const { return x.second \u0026lt; y.second; }};double distance(const Point \u0026amp;x, const Point \u0026amp;y){ return sqrt(pow(x.first - y.first, 2) + pow(x.second - y.second, 2));}void insert(double d, double dd){ int i = 3; for (; i \u0026amp;\u0026amp; dd \u0026lt; d; i--) d = d; d = dd;}void nearest3(Point *a, Point *b, int n, double d){ if (n \u0026lt; 6) { sort(a, a+n, Cmp()); fill_n(d, 3, DBL_MAX); for (int i = 0; i \u0026lt; n; i++) for (int j = i; ++j \u0026lt; n; ) insert(d, distance(a, a)); return; } int nn = n/2; double d0, d1; Point div = a; fill_n(d0, 3, DBL_MAX); nearest3(a, b, nn, d0); fill_n(d1, 3, DBL_MAX); nearest3(a+nn, b, n-nn, d1); merge(d0, d0+3, d1, d1+3, d); merge(a, a+nn, a+nn, a+n, b, Cmp()); double dd = d; nn = copy_if(b, b+n, a, (const Point \u0026amp;x) { return fabs(x.first - div.first) \u0026lt; dd; }) - a; for (int i = 0; i \u0026lt; nn; i++) for (int j = i; ++j \u0026lt; nn \u0026amp;\u0026amp; a.second - a.second \u0026lt; dd; ) if ((a \u0026lt; div) != (a \u0026lt; div)) insert(d, distance(a, a)); copy_n(b, n, a);}计算： double d; int n = sizeof(a)/sizeof(*a); Point *b = new Point; sort(a, a+n); nearest3(a, b, n, d); delete b; // d 就是
■网友
我来说个算法吧，并没有思考到十分完善。这是个在线算法，就是可以一边往点集中加点，一边更新距离最短的点对列表。建立两棵二叉搜索树存储点集，分别以横坐标和纵坐标为比较对象。最初的时候，点集中只有3个点，它们构成距离最短的3对点。然后每加入一个点A的时候，在两棵树中寻找横、纵坐标与A相差均不超过d的点（d为当前第3大的距离），计算这些点与A的距离，并更新距离最短的点对列表。粗略分析一下复杂度。每加入一个点的时候，需要搜索两次二叉搜索树。如果树是平衡的，复杂度为O(logN)（N为当前点数）。然后需要对搜索到的候选点计算距离。我觉得对于每个点，候选点的个数应该是很少的，不过我没仔细想是不是有上界。
■网友
O(n)随机增量画网格求最近点对的那个方法还是可以用的，找完最小的那对之后试着删掉其中的一个点就能找下一对。这样只要求距离最近的常数对点的话总复杂度还是O(n)的。
【海量点集 求距离最近的3对点 】 另外这个N无穷大是什么意思...是"海量"的夸张表示么？

■网友
这是延伸一维情形下求最近点对的算法=L=把二分改为四分, 把每层递归返回一个距离改成返回三个距离, 别的自行脑补, 大致就是这样(:3_Z)


    推荐阅读


    上一篇：帆软BI、tableau、qlikview对比怎样采购价格是多少

    下一篇：在团队中， 后端开发人员的工作职责包含哪些，怎么样才算一个优秀的后端开发人员