포인트 알고리즘 사이의 가장 짧은 거리
https://stackoverflow.com/questions/1602164
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
평면의 점 세트가 주어지면이 두 지점 중 하나에 의해 형성된 가장 짧은 선 세그먼트를 찾으십시오.
어떻게 할 수 있습니까? 사소한 방법은 분명히 각 거리를 계산하는 것이지만 비교할 다른 알고리즘이 필요합니다.
해결책
http://en.wikipedia.org/wiki/closest_pair_of_points
문제는 재귀 분열 및 정복 접근법을 사용하여 O (n log n) 시간으로 해결 될 수 있습니다.
- x 좌표를 따라 점을 정렬하십시오
- 포인트 세트를 수직선 x = XMID로 두 개의 동일한 크기의 서브 세트로 분할
- 왼쪽 및 오른쪽 서브 세트에서 문제를 재귀 적으로 해결하십시오. 이것은 각각 왼쪽 및 오른쪽 최소 거리에 dlmin과 drmin을 제공합니다.
- 나누기 세로의 왼쪽에있는 한 지점이있는 지점 쌍 중에서 최소 거리 dlrmin을 찾으십시오. 두 번째 지점은 오른쪽에 있습니다.
- 마지막 답변은 DLMIN, DRMIN 및 DLRMIN의 최소입니다.
다른 팁
나는 Brute Force 기술보다 더 빠른 대안을 즉시 생각할 수 없지만 (많은 것이 있어야하지만) 선택한 알고리즘 ~하지 않다 각 점 사이의 거리를 계산하십시오. 거리를 비교 해야하는 경우를 비교하십시오 사각형 비싸고 완전히 중복 된 제곱근을 피하기 위해 거리의.
한 가지 가능성은 x 좌표로 점을 정렬하는 것입니다 (또는 y- 실제로는 중요하지 않습니다. 그런 다음이를 사용하여 다른 많은 점과의 비교를 제거 할 수 있습니다. 포인트 [i]와 포인트 [j] 사이의 거리를 살펴보면 x 거리만이 현재 가장 짧은 거리보다 크면 지점 [j+1] ... 점 [n]은 다음과 같이 제거 할 수 있습니다. 글쎄요 (가정합니다 i<j -- 만약에 j<i, 그런 다음 지점 [0] ... 포인트 [I]가 제거 된 것입니다).
포인트가 극지 좌표로 시작되면 동일한 것의 변형을 사용할 수 있습니다. 원점과의 거리별로 정렬 할 수 있으며, 원점과의 거리의 차이가 현재 가장 짧은 거리보다 크면 해당 지점을 제거 할 수 있습니다. 그리고 현재 고려하고있는 것보다 원점에서 더 멀리 떨어진 다른 모든 사람들.
당신은 선형 시간에 가장 가까운 쌍을 Delaunay 삼각 측량 그리고 반대로 Voronoi 다이어그램.
이 문제에 대한 표준 알고리즘이 있습니다. 여기에서 찾을 수 있습니다.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;
}
질문에서 세그먼트의 거리 또는 세그먼트 자체를 찾고 있는지는 확실하지 않습니다. 거리를 찾고 있다고 가정하면 (단순한 수정의 세그먼트, 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.
내가 틀리지 않으면 거리의 통근성을 감안할 때 다른 비교를 수행 할 필요가 없습니다. 파이썬에서는 무언가처럼 들릴 수 있습니다
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 점 이상의 포인트가 동일한 최소 거리를 가질 수 있고 세그먼트를 찾고 있다면 제안 된 코드를 다시 수정해야하며 출력은 거리가 최소 인 포인트 목록 (또는 몇 가지)입니다. 도움이되기를 바랍니다!
