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

Question

[Network2020]

Необходимо проверить, входит ли точка на карте в полигон в форме правильного шестиугольника, у которого известны центр и длина сторон. Точка, соответственно, имеет широту и долготу, центр полигона тоже. Длина сторон в метрах.

Comments

[Денис Загаевский]

правильных шестиугольников, у которых известен центр и длина сторон бесконечно много.

[Network2020]

Денис Загаевский, не понял. Например?

[Network2020]

Денис Загаевский, вроде все такие

[Денис Загаевский]

Network2020, возьми тот единственный шестиугольник, который, по твоему мнению, подходит. Теперь вращай его вокруг центра на произвольный угол. Таких углов бесконечно много, соответственно, шестиугольников тоже бесконечно много. В рамках твоей задачи всё это - разные шестиугольники, потому что в них попадают разные точки.

[Rsa97]

Network2020, Возьмите правильный шестиугольник и просто вращайте его вокруг центра. Получите бесконечное количество правильных шестиугольников, каждый со своим углом поворота.

[Network2020]

Денис Загаевский, он именно в том положении, что и на картинке, это как-то меняет суть?)

Answer 1

[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

И да, это работает, если предположить, что шестиугольник маленький или на плоскости. если у вас кривизна земли играет роль, то все сильно усложняется.

Comments

[Network2020]

Расстояние каждой стороны - 200 метров. Это повлияет, интересно, на результат? Кривизна конечно есть, но на таких маленьких расстояниях не сильно заметна

[Network2020]

Как не пытаюсь, некоторые моменты никак не понимаю.
У меня, например, такие координаты X, Y для каждой стороны шестиугольника
Сторона a [ aX, aY ], [ bX, bY ] - это первая верхняя сторона шестиугольника, а дальше по часовой стрелке
Сторона b [ bX, bY ], [ cX, cY ]
Сторона c [ cX, cY ], [ dX, dY ]
Сторона d [ dX, dY ], [ eX, eY ]
Сторона e [ eX, eY ], [ jX, jY ]

Можно, пожалуйста, подставить их в твои формулы...?( Был бы очень признателен

[Network2020]

Это точки шестиугольника, начиная с первой точки первой стороны
[ aX, aY ]
[ bX, bY ]
[ cX, cY ]
[ dX, dY ]
[ eX, eY ]
[ jX, jY ]

[Wataru]

Network2020, Возьмем первую сторону (ax, ay), (bx, by).

A = ay-by
B = bx-ax (обратите внимание на разные знаки!)
С = -ax*A-ay*B

Если вершины заданы против часовой стрелки, то С будет уже положительное. Кстати, для всех 6-ти прямых C будет одинаковым, потому что они на одинаковом расстоянии от центра.

Напоминаю, координаты вершин у вас такие, что (0, 0) - это центр шестиугольника.

[Network2020]

Илья Николаевский, а sqrt не нужен? Просто в формуле выше они есть

[Wataru]

Network2020, вам нужен синус/косинус 60 градусов, чтобы получить координаты точек. Дальше синус не нужен. Просто 2 разные формулы. Та считает площадь треугольников из точки на стороны. Эта формула проверяет, что точка лежит по правильную сторону от всех сторон.

Та фромула с синусом чуть сложнее и работает даже для не выпуклых многоугольников. Моя формула попроще и работает только для выпуклых.

[Network2020]

Илья Николаевский, короче, т.к. я немного тупой, спрошу еще раз)) хотя ты достаточно объяснил
Мне надо по каждому из сторон найти значение A,B,C по этой формуле
A = ay-by
B = bx-ax (обратите внимание на разные знаки!)
С = -ax*A-ay*B

Потом вставить найденные значения в эту формулу Ax+By+C=0 и вместо x,y поставить координаты точки, которую проверяем и проверить каждое полученное значение. Я все правильно понял?)

[Wataru]

Network2020, да

[Network2020]

Илья Николаевский, отлично, спасибо огромное!

[Network2020]

Илья Николаевский, к сожалению, решение возвращает хаотичные данные((
Написал на js алгоритм строго по вашему сценарию, но возвращаемые значения неверные

let arr_pos = [
[[ aX, aY ], [ bX, bY ]],
[[ bX, bY ], [ cX, cY ]],
[[ cX, cY ], [ dX, dY ]],
[[ dX, dY ], [ eX, eY ]],
[[ eX, eY ], [ jX, jY ]]
];

arr_pos.forEach((item,i,arr) => {

let lat_p1 = item[0][0];
let long_p1 = item[0][1];
let lat_p2 = item[1][0];
let long_p2 = item[1][1];

let A = long_p1 - long_p2;

let B = lat_p2 - lat_p1;

let C = (lat_p1 * (-1) * A) - (long_p1 * B);

C = (C < 0) ? (C * (-1)) : C ;

let isPol = (A * geo_lat) + (B * geo_long) + C;

console.log('isPol', isPol);

})

[Wataru]

Network2020,

1) Если C отрицательное, то надо домножать на -1 все коэффициенты в уравнении.
2) Условие isPol > 0. Значения будут зависеть от положения точки и могут быть любыми.
3) Нужно 6 сторон. Замкните круг добавив [[jX, jY], [aX, aY]] (кстати, почему не fX, fY?
4) Важно, координаты geo_lat, geo_long должны быть уже уменьшены на центр шестиугольника, как и все 6 вершин.

Answer 2

[AVKor]

Здесь.

Comments

[Network2020]

Можно, пожалуйста, формулу оттуда на понятном языке? Я просто немного тупой)))

[AVKor]

Network2020, Там описаны разные методы. Выбирайте по вкусу.

Answer 3

[Ocelot]

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

Если между этими значениями, нужна точная проверка. Скорее всего, оптимально будет найти ближайшую к точке сторону полигона, зная угол вектора между точкой и центром; а затем проверить пересечение этого вектора с выбранной стороной. Не забыть про граничный случай, когда вектор проходит через вершину полигона.

Answer 4

[habrspec]

1. Пересчитать широту и долготу в градусах в координаты проекции UTM в метрах. Теперь вычисления можно производить на плоскости.
2. Реализовать алгоритм проверки попадания точки в полигон.