@Network2020

Как проверить, попадает ли географическая точка в правильный шестиугольник?

Необходимо проверить, входит ли точка на карте в полигон в форме правильного шестиугольника, у которого известны центр и длина сторон. Точка, соответственно, имеет широту и долготу, центр полигона тоже. Длина сторон в метрах.
  • Вопрос задан
  • 196 просмотров
Решения вопроса 1
wataru
@wataru
Разработчик на С++, экс-олимпиадник.
Вычтите координаты центра из координат точки. Теперь шестиугольник лежит центром в (0, 0).

Составьте 6 уравнений сторон шестиугольника в виде Ax+By+C=0, так что C положительно (если нет - домножте на -1). Подставьте в эти 6 уравнений координаты точки, все они должны дать положительные значения (или нули, если точка на границе считается лежащей внутри в вашей задаче).

Почему это работает? Мы просто проверяем, что точка лежит с той же стороны от всех 6 прямых, что и центр (0, 0).

Как составить уравнения? Найдите координаты 6-ти углов. Если сторона = a, то координаты точек (a, 0), (a/2, sqrt(3)*a/2), (-a/2, sqrt(3)*a/2), (-a, 0) ...

Для уравнения одной из сторон возьмите в виде A разность по у у соседних точек, а в виде B разность по x (но с другим знаком). Потом подставьте туда координаты одной из точек и возьмите C так, чтобы был 0.

Можно все 6 уравнений составить на бумажке и закодировать в программе.

Пример для первой стороны:
A = sqrt(3)*a/2-0 = sqrt(3)*a/2
B = a - a/2 = a/2
C = -A*a - B*0 = -sqrt(3)*a*a/2.

Поскольку C отрицательно, меняем знаки:
A = -sqrt(3)*a/2
B = -a/2
C = sqrt(3)*a*a/2

Для второй прямой будет 0*x-a*y+sqrt(3)*a*a/2 = 0

И да, это работает, если предположить, что шестиугольник маленький или на плоскости. если у вас кривизна земли играет роль, то все сильно усложняется.
Ответ написан
Пригласить эксперта
Ответы на вопрос 3
Ocelot
@Ocelot
Первая грубая проверка: если расстояние от точки до центра больше стороны шестиугольника, значит точка даже в описанную окружность не попадает, ответ отрицательный. Если расстояние меньше sqrt(3)/2 стороны, значит точка попадает во вписанную окружность, ответ положительный.

Если между этими значениями, нужна точная проверка. Скорее всего, оптимально будет найти ближайшую к точке сторону полигона, зная угол вектора между точкой и центром; а затем проверить пересечение этого вектора с выбранной стороной. Не забыть про граничный случай, когда вектор проходит через вершину полигона.
Ответ написан
@habrspec
1. Пересчитать широту и долготу в градусах в координаты проекции UTM в метрах. Теперь вычисления можно производить на плоскости.
2. Реализовать алгоритм проверки попадания точки в полигон.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы