구면의 Geodesics (최단 거리 경로) 사이의 교차점

Question

나는이 문제에 대해 적절한 답을 찾지 못했다. 구의 시작점과 끝점으로 정의되는 구의 두 선이 주어 졌는지 여부와 그들이 교차하는 위치를 결정합니다. 이 사이트 (http://mathforum.org/library/drmath/view/62205.html)는 두 개의 큰 원의 교차점에 대한 좋은 알고리즘을 실행합니다. 주어진 점이 큰 원의 유한 부분을 따라 있는지 여부를 결정하는 데 어려움이 있습니다.

여기에 몇 가지 질문을 포함하여 stackexchange를 포함하여 여러 가지 사이트를 구현 한 것으로 밝혀졌지만 항상 두 개의 큰 서클의 교차점으로 축소 된 것처럼 보입니다.

다음과 거의 작동하는 것 같다 나는이 편지를 쓰고있어 파이썬 클래스는 다음과 같습니다

class Geodesic(Boundary): 
    def _SecondaryInitialization(self): 
    self.theta_1 = self.point1.theta 
    self.theta_2 = self.point2.theta 
    self.phi_1 = self.point1.phi 
    self.phi_2 = self.point2.phi 

    sines = math.sin(self.phi_1) * math.sin(self.phi_2) 
    cosines = math.cos(self.phi_1) * math.cos(self.phi_2) 
    self.d = math.acos(sines - cosines * math.cos(self.theta_2 - self.theta_1)) 

    self.x_1 = math.cos(self.theta_1) * math.cos(self.phi_1) 
    self.x_2 = math.cos(self.theta_2) * math.cos(self.phi_2) 
    self.y_1 = math.sin(self.theta_1) * math.cos(self.phi_1) 
    self.y_2 = math.sin(self.theta_2) * math.cos(self.phi_2) 
    self.z_1 = math.sin(self.phi_1) 
    self.z_2 = math.sin(self.phi_2) 

    self.theta_wraps = (self.theta_2 - self.theta_1 > PI) 
    self.phi_wraps = ((self.phi_1 < self.GetParametrizedCoords(0.01).phi and 
     self.phi_2 < self.GetParametrizedCoords(0.99).phi) or (
     self.phi_1 > self.GetParametrizedCoords(0.01).phi) and 
     self.phi_2 > self.GetParametrizedCoords(0.99)) 

    def Intersects(self, boundary): 
    A = self.y_1 * self.z_2 - self.z_1 * self.y_2 
    B = self.z_1 * self.x_2 - self.x_1 * self.z_2 
    C = self.x_1 * self.y_2 - self.y_1 * self.x_2 
    D = boundary.y_1 * boundary.z_2 - boundary.z_1 * boundary.y_2 
    E = boundary.z_1 * boundary.x_2 - boundary.x_1 * boundary.z_2 
    F = boundary.x_1 * boundary.y_2 - boundary.y_1 * boundary.x_2 

    try: 
     z = 1/math.sqrt(((B * F - C * E) ** 2/(A * E - B * D) ** 2) 
      + ((A * F - C * D) ** 2/(B * D - A * E) ** 2) + 1) 
    except ZeroDivisionError: 
     return self._DealWithZeroZ(A, B, C, D, E, F, boundary) 

    x = ((B * F - C * E)/(A * E - B * D)) * z 
    y = ((A * F - C * D)/(B * D - A * E)) * z 

    theta = math.atan2(y, x) 
    phi = math.atan2(z, math.sqrt(x ** 2 + y ** 2)) 

    if self._Contains(theta, phi): 
     return point.SPoint(theta, phi) 

    theta = (theta + 2* PI) % (2 * PI) - PI 
    phi = -phi 

    if self._Contains(theta, phi): 
     return spoint.SPoint(theta, phi) 

    return None 

    def _Contains(self, theta, phi): 
    contains_theta = False 
    contains_phi = False 

    if self.theta_wraps: 
     contains_theta = theta > self.theta_2 or theta < self.theta_1 
    else: 
     contains_theta = theta > self.theta_1 and theta < self.theta_2 

    phi_wrap_param = self._PhiWrapParam() 
    if phi_wrap_param <= 1.0 and phi_wrap_param >= 0.0: 
     extreme_phi = self.GetParametrizedCoords(phi_wrap_param).phi 
     if extreme_phi < self.phi_1: 
     contains_phi = (phi < max(self.phi_1, self.phi_2) and 
      phi > extreme_phi) 
     else: 
     contains_phi = (phi > min(self.phi_1, self.phi_2) and 
      phi < extreme_phi) 
    else: 
     contains_phi = (phi > min(self.phi_1, self.phi_2) and 
      phi < max(self.phi_1, self.phi_2)) 

    return contains_phi and contains_theta 

    def _PhiWrapParam(self): 
    a = math.sin(self.d) 
    b = math.cos(self.d) 
    c = math.sin(self.phi_2)/math.sin(self.phi_1) 
    param = math.atan2(c - b, a)/self.d 

    return param 

    def _DealWithZeroZ(self, A, B, C, D, E, F, boundary): 
    if (A - D) is 0: 
     y = 0 
     x = 1 
    elif (E - B) is 0: 
     y = 1 
     x = 0 
    else: 
     y = 1/math.sqrt(((E - B)/(A - D)) ** 2 + 1) 
     x = ((E - B)/(A - D)) * y 

    theta = (math.atan2(y, x) + PI) % (2 * PI) - PI 
    return point.SPoint(theta, 0) 

def GetParametrizedCoords(self, param_value): 
    A = math.sin((1 - param_value) * self.d)/math.sin(self.d) 
    B = math.sin(param_value * self.d)/math.sin(self.d) 

    x = A * math.cos(self.phi_1) * math.cos(self.theta_1) + (
    B * math.cos(self.phi_2) * math.cos(self.theta_2)) 
    y = A * math.cos(self.phi_1) * math.sin(self.theta_1) + (
     B * math.cos(self.phi_2) * math.sin(self.theta_2)) 
    z = A * math.sin(self.phi_1) + B * math.sin(self.phi_2) 

    new_phi = math.atan2(z, math.sqrt(x**2 + y**2)) 
    new_theta = math.atan2(y, x) 

    return point.SPoint(new_theta, new_phi) 

편집 : 나는 두 곡선이 교차하기로 결정하면, 그때의 지점을 가질 필요가 지정하는 것을 잊었다 교차로.

Answer 1

더 간단한 접근법은 dot product, cross product 및 triple product과 같은 기하학적 기본 연산으로 문제를 표현하는 것입니다. U의 행렬식의 부호,와트 V 및 는 U를 포함하는 승 V 및 에 의해 스팬 비행기의 측면을 알려줍니다. 이를 통해 우리는 두 지점이 비행기의 반대편에있는 지점을 감지 할 수 있습니다. 이것은 큰 원이 다른 큰 원을 교차하는지 테스트하는 것과 같습니다. 이 테스트를 두 번 수행하면 두 개의 큰 원 세그먼트가 서로 교차하는지 알 수 있습니다.

구현시 삼각 함수가 필요하지 않으며, 나누기가 필요하지 않으며, pi와의 비교가 없으며 막대 주위에 특별한 동작이 필요하지 않습니다!

class Vector: 
    def __init__(self, x, y, z): 
     self.x = x 
     self.y = y 
     self.z = z 

def dot(v1, v2): 
    return v1.x * v2.x + v1.y * v2.y + v1.z * v2.z 

def cross(v1, v2): 
    return Vector(v1.y * v2.z - v1.z * v2.y, 
        v1.z * v2.x - v1.x * v2.z, 
        v1.x * v2.y - v1.y * v2.x) 

def det(v1, v2, v3): 
    return dot(v1, cross(v2, v3)) 

class Pair: 
    def __init__(self, v1, v2): 
     self.v1 = v1 
     self.v2 = v2 

# Returns True if the great circle segment determined by s 
# straddles the great circle determined by l 
def straddles(s, l): 
    return det(s.v1, l.v1, l.v2) * det(s.v2, l.v1, l.v2) < 0 

# Returns True if the great circle segments determined by a and b 
# cross each other 
def intersects(a, b): 
    return straddles(a, b) and straddles(b, a) 

# Test. Note that we don't need to normalize the vectors. 
print(intersects(Pair(Vector(1, 0, 1), Vector(-1, 0, 1)), 
       Pair(Vector(0, 1, 1), Vector(0, -1, 1)))) 

는 각도 세타와 피의 관점에서 단위 벡터를 초기화 할 경우, 그렇게 할 수 있지만 즉시 (X는, Y, Z)을 이후의 모든 계산을 수행하기 위해 좌표 직교로 변환 바랍니다.