平面上の一連の点が与えられた場合、これらの点のうちの任意の 2 点によって形成される最短の線分を見つけます。
どうやってやるの？自明な方法は明らかに各距離を計算することですが、比較するには別のアルゴリズムが必要です。
37948 次
7 に答える
35
http://en.wikipedia.org/wiki/Closest_pair_of_points
この問題は、次のように、再帰的な分割統治法を使用して O(n log n) 時間で解決できます。
- x 座標に沿ってポイントを並べ替える
- 垂直線 x = xmid によって点のセットを 2 つの等しいサイズのサブセットに分割します。
- 左サブセットと右サブセットで問題を再帰的に解きます。これにより、左側と右側の最小距離 dLmin と dRmin がそれぞれ得られます。
- 1 つの点が分割垂直線の左側にあり、2 番目の点が右側にある点のペアの間で最小距離 dLRmin を見つけます。
- 最終的な答えは、dLmin、dRmin、および dLRmin の最小値です。
于 2009-10-21T17:29:02.670 に答える
28
ブルート フォース テクニックよりも迅速な代替手段をすぐには思いつきませんが (たくさんあるはずですが)、どのアルゴリズムを選択しても、各ポイント間の距離は計算されません。距離を比較する必要がある場合は、距離の2 乗を比較するだけで、費用がかかり完全に冗長な平方根を回避できます。
于 2009-10-21T17:11:38.400 に答える
6
1つの可能性は、ポイントをX座標で並べ替えることです（またはY-は実際にはどちらでもかまいませんが、一貫しているだけです）。次に、それを使用して、他の多くのポイントとの比較を排除できます。ポイント[i]とポイント[j]の間の距離を見ているときに、X距離だけが現在の最短距離よりも大きい場合、ポイント[j +1]...ポイント[N]は次のように削除できます。よく（仮定i<j-の場合j<i、削除されるのはpoint [0] ... point [i]です）。
ポイントが極座標として始まる場合は、同じもののバリエーションを使用できます。原点からの距離で並べ替えます。原点からの距離の差が現在の最短距離よりも大きい場合は、そのポイントを削除できます。そして、現在検討しているものよりも原点から遠い（または近い）他のすべてのもの。
于 2009-10-21T17:24:26.507 に答える
5
Delaunay 三角形分割から線形時間で最も近いペアを抽出し、逆にボロノイ図から抽出できます。
于 2009-10-24T21:32:11.023 に答える
3
この問題には標準のアルゴリズムがあります。ここで見つけることができます: http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairPS.html
そして、これがこのアルゴリズムの私の実装です。申し訳ありませんが、コメントはありません。
static long distSq(Point a, Point b) {
return ((long) (a.x - b.x) * (long) (a.x - b.x) + (long) (a.y - b.y) * (long) (a.y - b.y));
}
static long ccw(Point p1, Point p2, Point p3) {
return (long) (p2.x - p1.x) * (long) (p3.y - p1.y) - (long) (p2.y - p1.y) * (long) (p3.x - p1.x);
}
static List<Point> convexHull(List<Point> P) {
if (P.size() < 3) {
//WTF
return null;
}
int k = 0;
for (int i = 0; i < P.size(); i++) {
if (P.get(i).y < P.get(k).y || (P.get(i).y == P.get(k).y && P.get(i).x < P.get(k).x)) {
k = i;
}
}
Collections.swap(P, k, P.size() - 1);
final Point o = P.get(P.size() - 1);
P.remove(P.size() - 1);
Collections.sort(P, new Comparator() {
public int compare(Object o1, Object o2) {
Point a = (Point) o1;
Point b = (Point) o2;
long t1 = (long) (a.y - o.y) * (long) (b.x - o.x) - (long) (a.x - o.x) * (long) (b.y - o.y);
if (t1 == 0) {
long tt = distSq(o, a);
tt -= distSq(o, b);
if (tt > 0) {
return 1;
} else if (tt < 0) {
return -1;
}
return 0;
}
if (t1 < 0) {
return -1;
}
return 1;
}
});
List<Point> hull = new ArrayList<Point>();
hull.add(o);
hull.add(P.get(0));
for (int i = 1; i < P.size(); i++) {
while (hull.size() >= 2 &&
ccw(hull.get(hull.size() - 2), hull.get(hull.size() - 1), P.get(i)) <= 0) {
hull.remove(hull.size() - 1);
}
hull.add(P.get(i));
}
return hull;
}
static long nearestPoints(List<Point> P, int l, int r) {
if (r - l == P.size()) {
Collections.sort(P, new Comparator() {
public int compare(Object o1, Object o2) {
int t = ((Point) o1).x - ((Point) o2).x;
if (t == 0) {
return ((Point) o1).y - ((Point) o2).y;
}
return t;
}
});
}
if (r - l <= 100) {
long ret = distSq(P.get(l), P.get(l + 1));
for (int i = l; i < r; i++) {
for (int j = i + 1; j < r; j++) {
ret = Math.min(ret, distSq(P.get(i), P.get(j)));
}
}
return ret;
}
int c = (l + r) / 2;
long lD = nearestPoints(P, l, c);
long lR = nearestPoints(P, c + 1, r);
long ret = Math.min(lD, lR);
Set<Point> set = new TreeSet<Point>(new Comparator<Point>() {
public int compare(Point o1, Point o2) {
int t = o1.y - o2.y;
if (t == 0) {
return o1.x - o2.x;
}
return t;
}
});
for (int i = l; i < r; i++) {
set.add(P.get(i));
}
int x = P.get(c).x;
double theta = Math.sqrt(ret);
Point[] Q = set.toArray(new Point[0]);
Point[] T = new Point[Q.length];
int pos = 0;
for (int i = 0; i < Q.length; i++) {
if (Q[i].x - x + 1 > theta) {
continue;
}
T[pos++] = Q[i];
}
for (int i = 0; i < pos; i++) {
for (int j = 1; j < 7 && i + j < pos; j++) {
ret = Math.min(ret, distSq(T[i], T[j + i]));
}
}
return ret;
}
于 2009-10-21T17:30:53.650 に答える
1
あなたの質問から、セグメントの距離を探しているのか、それともセグメント自体を探しているのかは明確ではありません。距離を探していると仮定すると (距離が最小の 2 点がわかれば、単純な修正でセグメントが変わります)、1 から 5 までの番号が付けられた 5 つの点が与えられると、次のようにする必要があります。
compare 1 with 2,3,4,5, then
compare 2, with 3,4,5, then
compare 3 with 4,5, then
compare 4 with 5.
私が間違っていなければ、距離の可換性を考えると、他の比較を実行する必要はありません。Pythonでは、何かのように聞こえるかもしれません
import numpy as np
def find_min_distance_of_a_cloud(cloud):
"""
Given a cloud of points in the n-dim space, provides the minimal distance.
:param cloud: list of nX1-d vectors, as ndarray.
:return:
"""
dist_min = None
for i, p_i in enumerate(cloud[:-1]):
new_dist_min = np.min([np.linalg.norm(p_i - p_j) for p_j in cloud[(i + 1):]])
if dist_min is None or dist_min > new_dist_min:
dist_min = new_dist_min
return dist_min
これは、次のコードのようなものでテストできます。
from nose.tools import assert_equal
def test_find_min_distance_of_a_cloud_1pt():
cloud = [np.array((1, 1, 1)), np.array((0, 0, 0))]
min_out = find_min_distance_of_a_cloud(cloud)
assert_equal(min_out, np.sqrt(3))
def test_find_min_distance_of_a_cloud_5pt():
cloud = [np.array((0, 0, 0)),
np.array((1, 1, 0)),
np.array((2, 1, 4)),
np.array((3, 4, 4)),
np.array((5, 3, 4))]
min_out = find_min_distance_of_a_cloud(cloud)
assert_equal(min_out, np.sqrt(2))
2 つ以上のポイントが同じ最小距離を持つことができ、セグメントを探している場合は、提案されたコードを再度変更する必要があり、出力は距離が最小のポイント (またはポイントのカップル) のリストになります。それが役に立てば幸い！
于 2016-07-11T11:01:24.163 に答える