하나의 점 X가 Java에서 가장 가까운 arraylist의 인접 점 쌍을 찾는 가장 좋은 방법은 무엇입니까?

Question

arraylist (예 : A, B, C, D)에 2D 점이 있습니다. 함께 엮은 선 문자열을 나타내는 임의의 수의 점을 포함 할 수 있습니다.

점 B와 C 사이에있는 점 X가 있다고 가정합니다. 함수의 출력이 점 "B"와 "C"가있는 arraylist인지 어떻게 확인할 수 있습니까 (또는 간단히 pointA 또는 pointB가 할당 됨). 주어진 점 "B"와 "C") 다음 두 건으로 :

Point pointA = null; 
Point pointB = null; 

int minDistance = Integer.MAX_VALUE; 
for(int i = 0; i < pointlist.size(); i++) { 
    int distance = pointlist.get(i).getDistanceToPoint(xPoint); 
    if(distance < minDistance) { 

     if(pointB != null) { 
      pointB = pointA; 
     } 
     minDistance = distance; 
     pointA = pointlist.get(i); 
    } else { 
    pointB = pointA; 
    pointA = pointlist.get(i); 
    } 
} 

: 다음과 같이 pointX을 가정한다

1- Point X is closer to B than C, but still falls between B and C 
2- Point X is closer to C than B, but still falls between C and B 
3- Point X is closer to C than G (maybe because the line segments from the array list is oddly shaped like a U or something), but the function should return either the points C and D or C and B, depending on whichever is the closest to pointX. 

내 현재 코드는 다음 작업을 수행하는 함수에 전달 위의 사례는 # 1 사례를 충족하지만 사례 # 2는 충족하지 않습니다. pointA가 "B"이고 pointB가 "C"와 같도록하는 가장 좋은 방법은 무엇입니까? 이렇게하는 더 좋은 방법이 있다면, 나는 그것에 열려 있습니다.

바로 pointX에 가장 가까운 두 점입니까? 점의 arraylist가 U 모양을 만들었거나 두 점이 가장 가까워 지도록 만든 모양이 있지만 함수가 반환 된 경우 반드시 인접하지는 않는 것은 가장 가까운 점과 두 번째로 가까운 점이 아닙니다. 그 두 점은 틀렸다. 대신 가장 가까운 첫 번째 점을 반환 한 다음 해당 점에 인접한 두 번째 점을 반환해야합니다. UNLESS 사용자가 포인트 "4"또는 특정 인덱스에서 시작하도록 지정할 수 있으므로 6 번째 포인트가 가장 가까운 두 번째 포인트 인 경우 결과는 5 번째 또는 7 번째와 함께 6 번째 포인트를 반환합니다 , 어느 선분에 속하는가에 따라 다릅니다.

Answer 1

코멘트 스레드에서 14 번을 추천하면 사실 문제는 연결된 선분 집합에서 어떤 점 X에 가장 가까운 선분을 찾는 것입니다. 세트는 정점 좌표로만 저장되지만, 기본적으로는 관계가 없습니다.

나는 다음과 같은 이유로 Segment을 사용할 예정입니다. Java 및 문제를 해결하려면 문제를 해결하기 위해 데이터 구조를 사용하십시오. 선을 찾고 싶습니까? 라인 클래스를 사용하십시오. 그래서 :의 그것에서 2 점 대신 ArrayList를의 선 세그먼트 (segment)의 표현에 전용 클래스를 사용하자 :

class Segment { 
    Point p1, p2; 
    public Segment(Point a, Point b) { p1=a; p2=b; } 
} 

ArrayList<Segment> segments = new ArrayList<Segment>(); 
for(int i=0, last=points.size()-1; i<last; i++) { 
    segments.add(new Segment(points.get(i), points.get(i+1)); 
} 

완료. 그래서, 가장 가까운 세그먼트 :

Segment findClosestSegment(ArrayList<Segment> segments, Point target) { 
    double dist, minDist = Double.MAX_VALUE; 
    Segment minDistSegment; 
    for(Segment s: segments) { 
    dist = s.distanceTo(target); 
    if(dist < minDist) { 
     minDist = dist; 
     minDistSegment = s; 
    } 
    } 
    return minDistSegment; 
} 

이제 우리는 단지 프로젝션 내에있는 확인하고 다음을위한 선형 대수의 약간의 (a) getting the projection distance for the point to the line segment을 구현 필요 Segment.distanceTo(Point), 그리고 (b)를 구현해야 세그먼트의 시작/끝점.

실제적으로 당신을위한 그 코드를 가지고있는 사이트가 많아서 여기에 그것을 포함하지 않을 것입니다. (지금까지 생각할 수있는 모든 언어로 there are SO questions for that code) 사실 말 그대로 포인트의 친밀감을 결정하는 유일한 통계입니다. 특정 라인 세그먼트.