Решение геометрической задачи

Question

Решение геометрической задачи

Рейтинг: -2Ответов: 1Опубликовано: 29.07.2023

У меня имеется задача: Имеются 2 прямых дороги, заданные точками начала и конца AB и CD соответвтенно. Точка представляет собой географическую координату (широта и долгота). Нужно попасть из точки A в точку D. Перемещаться можно только по дорогам. Необходимо реализовать функцию route_exist, которая возвращает истину в случае существования такого маршрута.

Эту задачу необходимо реализовать на python

Я очень не силен в геометрии и даже не могу понять как просто устно реализовать данную задачу Может кто помочь?

Смог задать только классы

@dataclass
class Point:
    latitude: float # Широта
    longitude: float # Долгота


@dataclass
class Road:
    start_point: Point
    end_point: Point


def route_exist(road_1: Road, road_2: Road) -> bool:
     pass

python геометрия

Источник: Stack Overflow на русском

Answer 1

▲ 1Принят

Любая пара точек, если они различные и не диаметрально противоположные, задаёт на сфере большой круг, который определяется плоскостью, построенной на центре сферы и этих двух точках. Плоскость задаётся нормальным вектором n: n = c×d, где c и d - точки задающие плоскость (трехмерные вектора единичной длины), × - векторное произведение.

Дуга между точками a и b пересечёт большой круг, если скалярные произведения a_n = n · a и b_n = n · b имеют разные знаки.

Пусть оказалось что a_n < 0 < b_n (если это не так, поменяем их местами чтобы стало так). Тогда можно вычислить точку на плоскости большого круга между a и b. Эта точка равна b_na - a_nb. Если эту точку (вектор) нормализовать, получим точку пересечения дуги от a до b с большим кругом заданным с и d.

Вычислим i_ab - пересечение дуги ab с большим кругом cd.

Вычислим i_cd - пересечение дуги cd с большим кругом ab.

Возможны следующие ситуации:

i_ab не существует, так как дуга ab не пересекает большой круг cd. Тогда дуги ab и cd не пересекаются.

Пример: a = 10°, 10°, b = 20°, 10° - кусок меридиана в северном полушарии. с = 0°, 0°, d = 0°, 20° - кусок экватора.
i_cd не существует, так как дуга cd не пересекает большой круг ab. Тогда дуги ab и cd не пересекаются.

Пример: a = 10°, 10°, b = -10°, 10° - кусок меридиана в районе экватора. с = 0°, 20°, d = 0°, 30° - кусок экватора.
i_ab и i_cd существуют обе и диаметрально противоположны. Дуги ab и cd не пересекаются, хотя каждая из них пересекает большой круг другой дуги. Бывает.

Пример: a = 10°, 0°, b = -10°, 0° - кусок нулевого меридиана в районе экватора. с = 0°, 170°, d = 0°, -170° - кусок экватора с противоположной стороны.
i_ab и i_cd существуют и совпадают. Пересечение найдено. Ура!

Пример: a = 10°, 10°, b = -10°, 10° - кусок меридиана. с = 0°, 0°, d = 0°, 20° - кусок экватора.

Код реализует описанный алгоритм. Все случаи где решение может выродится (совпадающие точки, противолежащие точки) нормально обрабатываются. Единственная ситуация, которая не обработана - когда обе дуги лежат на одном большом круге. Программа в этом случае возвращает что пересечения нет, даже если дуги перекрываются.

import math


# скалярное произведение
def dot(a, b):
    return a[0] * b[0] + a[1] * b[1] + a[2] * b[2]


# векторное произведение
def cross(a, b):
    return                         \
        a[1] * b[2] - a[2] * b[1], \
        a[2] * b[0] - a[0] * b[2], \
        a[0] * b[1] - a[1] * b[0]


# (широта, долгота) -> (x, y, z)
def to_3d(lat_long_deg):
    lat, long = map(math.radians, lat_long_deg)
    lat_c = math.cos(lat)
    return lat_c * math.cos(long), lat_c * math.sin(long), math.sin(lat)


def are_intersected(arc1, arc2):

    # это не настоящее пересечение круга и дуги
    # вектор, который возвращается:
    #   сонаправлен с точкой пересечения, если пересечение есть
    #   равен нулю, если пересечения нет
    # этого достаточно для финального теста
    def intersection(circle, arc):
        n = cross(*circle)
        a, b = arc
        a_n = dot(n, a)
        b_n = dot(n, b)
        if a_n > b_n:
            a, b = b, a
            a_n, b_n = b_n, a_n
        if a_n <= 0 <= b_n:
            return                       \
                b_n * a[0] - a_n * b[0], \
                b_n * a[1] - a_n * b[1], \
                b_n * a[2] - a_n * b[2]
        # fake intersection
        return 0, 0, 0

    arc1_3d = tuple(map(to_3d, arc1))
    arc2_3d = tuple(map(to_3d, arc2))

    # если оба вектора не нули
    # и если они сонаправлены,
    # то их скалярное произведение будет больше нуля.
    # в этом случае дуги пересекаются
    return dot(
        intersection(arc1_3d, arc2_3d),
        intersection(arc2_3d, arc1_3d)
    ) > 0


print(are_intersected(
    ((10, 10), (20, 20)),
    ((20, 10), (10, 20))
))

Решение геометрической задачи

Ответы