最近对分算法 [英] Closest pair of points algorithm
问题描述
我想实现这个算法的简化版本，但它的工作原理要比二次算法更好。我的想法主要是由只有X点坐标进行排序，并试图从那里解决。有一次，我整理点我用X阵列坐标，我想遍历数组，并基本上跳过点，其距离大于前两点我带的。
I am trying to implement a simpler version of this algorithm but which works better than the quadratic algorithm. My idea basically is to sort the points by only x coordinate and try to solve it from there. Once I sort my array of points by x coordinate, I want to iterate over the array and basically skip over points whose distance is greater than the first two points I took at.
例如，我currentminDist = X;
For example, my currentminDist = x;
如果这两个点对我在看有距离> X（只有其x坐标DIST），我忽视了一点，并搬过去就到数组中。
If the two pair of points I am looking at have distance > x (only by its x coord dist), I ignore the point and move past it in the array.
我有这个想法了，但那种我被困在如何真正实现这个（特别是条件部分）。我有一个函数，返回我基于其x坐标的两个点之间的距离。
I have the idea down, but I am kind of stuck on how to actually implement this (especially the condition part). I have a function that returns me the distance between two points based on their x coordinate.
我很困惑如何真正写我的条件，我的循环，因为我想忽略的一点，如果距离恰好是太远，还是填写我的数组其中将包含答案最接近的点，每个I（I而当前点我在看）。
I am confused on how to actually write my conditions for my loop since I want to ignore a point if the distance happens to be too far and still fill out my array which will contain the answers for closest points for each i (i being current point I am looking at).
任何提示或指示将大大AP preciated。我不是很懂行的编码算法，以便其相当令人沮丧。
Any tips or directions would be greatly appreciated. I am not very knowledgeable in coding algorithms so its quite frustrating.
下面是我的code部分：
Here is part of my code:
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是我的函数，仅仅返回两个点之间的距离。
distbyX is my function that just returns the distance between two points.
谢谢！
推荐答案
使用KD树 快速算法
该算法创建一个kd树，然后查找最接近的一对每个点。创建kd树是O（n日志 2 n），并找到一个点最近的邻居是O（LOGN）。信用必须去维基百科，其中一文中介绍了如何创建KD树，也如何使用它们来找到最接近的邻居。
Fast Algorithm using a KD-Tree
This algorithm creates a kd-tree and then finds the closest pair for each point. Creating the kd-tree is O(n log2n), and finding the closest neighbour of a point is O(logn). Credit must go to Wikipedia, which in one article explains how to create kd-trees and also how to use them to find the closest neighbour.
import java.util.*;
public class Program
{
public static void main(String[] args)
{
List<Point> points = generatePoints();
Point[] closest = new Point[points.size()];
KDTree tree = new KDTree(points, 0); // WILL MODIFY 'points'
for (int i = 0; i < points.size(); i++)
{
closest[i] = tree.findClosest(points.get(i));
}
for (int i = 0; i < points.size(); i++)
{
System.out.println(points.get(i) + " is closest to " + closest[i]);
}
}
private static List<Point> generatePoints()
{
ArrayList<Point> points = new ArrayList<Point>();
Random r = new Random();
for (int i = 0; i < 1000; i++)
{
points.add(new Point(r.nextInt() % 1000, r.nextInt() % 1000));
}
return points;
}
}
class Point
{
public static final Point INFINITY
= new Point(Double.POSITIVE_INFINITY,
Double.POSITIVE_INFINITY);
public double[] coord; // coord[0] = x, coord[1] = y
public Point(double x, double y)
{
coord = new double[] { x, y };
}
public double getX() { return coord[0]; }
public double getY() { return coord[1]; }
public double distance(Point p)
{
double dX = getX() - p.getX();
double dY = getY() - p.getY();
return Math.sqrt(dX * dX + dY * dY);
}
public boolean equals(Point p)
{
return (getX() == p.getX()) && (getY() == p.getY());
}
public String toString()
{
return "(" + getX() + ", " + getY() + ")";
}
public static class PointComp implements Comparator<Point>
{
int d; // the dimension to compare in (0 => x, 1 => y)
public PointComp(int dimension)
{
d = dimension;
}
public int compare(Point a, Point b)
{
return (int) (a.coord[d] - b.coord[d]);
}
}
}
class KDTree
{
// 2D k-d tree
private KDTree childA, childB;
private Point point; // defines the boundary
private int d; // dimension: 0 => left/right split, 1 => up/down split
public KDTree(List<Point> points, int depth)
{
childA = null;
childB = null;
d = depth % 2;
// find median by sorting in dimension 'd' (either x or y)
Comparator<Point> comp = new Point.PointComp(d);
Collections.sort(points, comp);
int median = (points.size() - 1) / 2;
point = points.get(median);
// Create childA and childB recursively.
// WARNING: subList() does not create a true copy,
// so the original will get modified.
if (median > 0)
{
childA = new KDTree(
points.subList(0, median),
depth + 1);
}
if (median + 1 < points.size())
{
childB = new KDTree(
points.subList(median + 1, points.size()),
depth + 1);
}
}
public Point findClosest(Point target)
{
Point closest = point.equals(target) ? Point.INFINITY : point;
double bestDist = closest.distance(target);
double spacing = target.coord[d] - point.coord[d];
KDTree rightSide = (spacing < 0) ? childA : childB;
KDTree otherSide = (spacing < 0) ? childB : childA;
/*
* The 'rightSide' is the side on which 'target' lies
* and the 'otherSide' is the other one. It is possible
* that 'otherSide' will not have to be searched.
*/
if (rightSide != null)
{
Point candidate = rightSide.findClosest(target);
if (candidate.distance(target) < bestDist)
{
closest = candidate;
bestDist = closest.distance(target);
}
}
if (otherSide != null && (Math.abs(spacing) < bestDist))
{
Point candidate = otherSide.findClosest(target);
if (candidate.distance(target) < bestDist)
{
closest = candidate;
bestDist = closest.distance(target);
}
}
return closest;
}
}
修正至code的问题
如果你真的不担心复杂性，用你的code，唯一的问题是，你期待，但不是倒退。只是重复内部循环，使Ĵ从去（I - 1）到 0 ：
Fix to the code in the question
If you really don't worry about the complexity, the only problem with your code is that you look forward but not backwards. Just duplicate the inner loop and make j go from (i - 1) to 0:
Point[] points = sort(input());
int[] closest = new int[points.length];
for (int i = 0; i < points.length; i++)
{
double bestdist = Double.POSITIVE_INFINITY;
for (int j = i + 1; (j < points.length) && ((points[j].x - points[i].x) < bestdist); j++ )
{
double currdist = dist(points[i], points[j]);
if (currdist < bestdist)
{
closest[i] = j;
bestdist = currdist;
}
}
for (int j = i - 1; (j >= 0) && ((points[i].x - points[j].x) < bestdist); j-- )
{
double currdist = dist(points[i], points[j]);
if (currdist < bestdist)
{
closest[i] = j;
bestdist = currdist;
}
}
}
这篇关于最近对分算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
