구형 좌표의 지점에 가장 가까운 그리드 사각형

StackOverflow https://stackoverflow.com/questions/1463606

문제

구의 표면을 그리드 포인트로 분해 한 알고리즘을 프로그래밍하고 있습니다 (단순화를 위해 그리드 라인이 자오선과 평행하고 수직 인 경우). 포인트 A가 주어지면, 나는 그리드 "사각형"을 효율적으로 가져 와서 가장 낮은 구형 좌표 거리 AB로 정사각형의 지점 B를 결정할 수 있기를 원합니다. 퇴화 된 경우 "사각형"은 실제로 "삼각형"입니다.

나는 실제로 그것을 검색하는 어떤 사각형을 묶는 데만 사용하고 있으므로, 나는 또한 하한 조금만 나가면. 이러한 이유로 알고리즘이 매우 빠르려면 정확도를 잃어 버리고 몇 차례 더 검색하는 것이 좋습니다.

도움이 되었습니까?

해결책 4

수학 오버플로를 참조하십시오. https://mathoverflow.net/questions/854/closest-grid-square-to-apoint-in-spherical-coordinates 정확한 솔루션

다른 팁

구의 지점의 경우 전체 3D 공간에서 가장 가까운 점도 구의 표면을 따라 측정 할 때 가장 가까워집니다. 실제 거리는 다를 수 있지만 가장 가까운 지점 직후에 큰 원 호에 대해 걱정하는 대신 3D 거리를 최소화하는 것이 가장 쉽습니다.

구의 두 가지 (latitidude, longitude) 지점 사이의 실제 큰 원 거리는 이 링크.

명확성을 위해 몇 가지 요점.

구체적 으로이 사각형이 정사각형이되기를 원하지 않는 한 (따라서 자오선과 관련 하여이 평행하고 수직 인 레이아웃에 정확하게 맞지 않음), 이들은 정확히 사각형이 아닙니다. 이것은 정사각형의 크기가 큰 경우 특히 보입니다.

이 질문은 [완벽한] 구체에 대해 이야기합니다. 우리가 평평한 기둥으로 지구 (또는 다른 행성)를 고려하고 있다면 문제는 다소 다릅니다.

다음은 청구서에 맞는 "알고리즘"입니다. 최적이라고 의심하지만 좋은 기반을 제공 할 수 있습니다. 편집하다: 이는 공식의 복잡성을 크게 줄일 것이기 때문에 해당 큰 원이 아닌 지점 사이의 평범한 3D 거리 (즉, 코드가 아닌 코드의 거리)가 아닌 점 사이의 평범한 3D 거리를 사용하겠다는 TOM10의 제안을 참조하십시오.

Problem layout:  (A, B and Sq as defined in the OP's question)
 A  : a given point the the surface of the sphere
 Sq : a given "square" from the grid 
 B  : solution to problem : point located within Sq which has the shortest 
      distance to A.
 C  : point at the center of Sq

Tentative algorithm:
Using the formulas associated with [Great Circle][1], we can:
 - find the equation of the  circle that includes A and C
 - find the distance between A and C. See the [formula here][2] (kindly lifted
    from Tom10's reply).
 - find the intersect of the Great Circle arc between these points, with the
   arcs  of parallel or meridian defining the Sq.
   There should be only one such point, unless this finds a "corner" of Sq, 
   or -a rarer case- if the two points are on the same diameter (see 
   'antipodes' below).
Then comes the more algorithmic part of this procedure (so far formulas...):
 - find, by dichotomy, the point on Sq's arc/seqment which is the closest from
   point A.  We're at B! QED.

Optimization:  
 It is probably possible make a good "guess" as to the location
 of B, based on the relative position of A and C, hence cutting the number of
 iterations for the binary search.
 Also, if the distance A and C is past a certain threshold the intersection
 of the cicles' arcs is probably a good enough estimate of B.  Only when A
 and C are relatively close will B be found a bit further on the median or
 parallel arc in these cases, projection errors between A and C (or B) are
 smaller and it may be ok to work with orthogonal coordinates and their 
 simpler formulas.

Another approach is to calculate the distance between A and each of the 4 
corners of the square and to work the dichotomic search from two of these
points (not quite sure which; could be on the meridian or parallel...)

( * ) *Antipodes case*:  When points A and C happen to be diametrically 
opposite to one another, all great circle lines between A and C have the same
 length, that of 1/2 the circonference of the sphere, which is the maximum any
 two points on the surface of a sphere may be.  In this case, the point B will
 be the "square"'s corner that is the furthest from C.

이게 도움이 되길 바란다...

게으른 하한 방법은 정사각형의 중심까지의 거리를 찾은 다음 반 대각선 거리를 빼고 삼각형 불평등을 사용하여 결합하는 것입니다. 이것들은 실제 사각형이 아니기 때문에 실제로 두 개의 대각선 거리가있을 것입니다. 우리는 더 큰 것을 사용할 것입니다. 나는 그것이 합리적으로 정확할 것이라고 생각합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top