Определите, ли точка в треугольнике, сформированном 3 точками с данной широтой/долготой
У меня есть 3 точки (lat, lon), которые формируют треугольник. Как я могу найти, ли точка в этом треугольнике?
6 ответов
Главный вопрос заключается в том, можете ли вы использовать для этого двумерное приближение (другими словами, достаточно ли мал ваш треугольник).
Если так, то подойдет что-нибудь простое, например барицентрические координаты.
Вы можете использовать тест "точка-многоугольник".
Все просто. Проведите линию от вашей точки на восток на достаточно большом расстоянии. Подсчитайте, сколько раз эта линия пересекается с вашим плигоном. Если он четный, ваша точка зрения снаружи, если нечетная - внутри.
Это работает для любого типа многоугольника.
В большинстве языков есть функция для этого. В Java это Polygon.contains () http://docs.oracle.com/javase/7/docs/api/java/awt/Polygon.html
Просто создайте многоугольник из своего points, а затем вызовите contains () в вашей тестовой точке.
Попробуйте алгоритм преобразования лучей.
http://en.wikipedia.org/wiki/Point_in_polygon
Это довольно просто реализовать.
function SameSide(p1,p2, a,b)
cp1 = CrossProduct(b-a, p1-a)
cp2 = CrossProduct(b-a, p2-a)
if DotProduct(cp1, cp2) >= 0 then return true
else return false
function PointInTriangle(p, a,b,c)
if SameSide(p,a, b,c) and SameSide(p,b, a,c)
and SameSide(p,c, a,b) then return true
else return false
Объяснение по ссылке ниже
Я сделал что-то подобное сегодня! Также с (lat, lon), на самом деле (theta, phi), хотя я знал немного больше о меше, с которым работал. Я работаю с (theta, phi) с 0 <= theta <= PI && 0 <= phi <= 2 * PI.
Вы обнаружите, что у вас могут возникнуть проблемы, если одна из вершин находится наверху или внизу вашей сферы, поскольку в моем случае phi на самом деле не определено. В итоге вы получаете сингулярность. По сути, у вас есть квадрат, что упрощает проверку, находится ли ваша точка внутри него или нет.
Во всех остальных случаях, если вы преобразовали свою точку в (лат, долг) / (тета, фи). Просто использовать метод, описанный @Michelle Six, должно быть просто.