Расстояние от точки до многоугольника

Я пытаюсь определить расстояние от точки до многоугольника в 2D-пространстве. Точка может быть внутри или снаружи многоугольника; Многоугольник может быть выпуклым или вогнутым.

Если точка находится внутри многоугольника или вне многоугольника с расстоянием, меньшим, чем заданная пользователем константаdпроцедура должна вернутьсяTrue; False иначе.

Я нашел похожий вопрос:Расстояние от точки до многогранника или многоугольника, Однако в моем случае пространство является двумерным, и многоугольник может быть вогнутым, поэтому он несколько отличается от этого.

Я предполагаю, что должен быть метод, более простой, чем смещение многоугольникаd и определение его внутри или снаружи многоугольника.

Любой алгоритм, код или подсказки для меня в Google будут оценены.

 clwen11 июн. 2012 г., 18:28
@trumpetlicks ищет минимальное расстояние. К сожалению, вы не уверены в том, что вы подразумеваете под "частью линии, соединяющей 2 точки". Любая точка на границе многоугольника считается.
 Girish Rao11 июн. 2012 г., 18:23
Я нашел это для тебя. Возвращает фактическое расстояние от точки до многоугольника (положительное, если точка находится за пределами многоугольника, и отрицательное в противном случае). Это код Matlab, но он может быть полезен с алгоритмической точки зрения:mathworks.com/matlabcentral/fileexchange/…
 trumpetlicks11 июн. 2012 г., 18:25
Имеет ли значение какая точка на многоугольнике, может ли она быть на части линии, соединяющей 2 точки? Вы ищете минимальное расстояние или просто ЛЮБОЕ расстояние?
 Kendall Frey11 июн. 2012 г., 18:18
Должен ли код вызова знать расстояние или просто оно находится на определенном расстоянии?
 clwen11 июн. 2012 г., 18:24
@KendallFrey, будь то в пределах определенного расстояния. Однако можно ли определить, находится ли оно на определенном расстоянии, не зная точно, какое это расстояние?

Ответы на вопрос(4)

The distance can be calculated using Wikipedia entry, even with an untested snipped of code. The inside/outside border can be solved with this Stack Post and links

и некоторые замечания:

you should check only the nearest points, as Martin Beckett´s answer point outs, since another segment can "proyected" very near, but in reality don´t be close as need.
 clwen11 июн. 2012 г., 20:24
Для внутренней / внешней границы я сравниваю не только прямоугольники, но и общие многоугольники. Я нашел комментарий в ссылке, которую вы дали, хотя помогает. Спасибо!


Должно ли это быть всегда абсолютно правильно в крайних случаях или будетgood enough большую часть времени будет в порядке?

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

Для больших сложных форм вы также можете хранить приблизительно несколько ограничивающих прямоугольников (прямоугольных или шестиугольников) и находить ближайшую сторону перед проверкой более подробной информации.

Вам также может понадобиться код для обработки особого случая точно в строке.

 24 нояб. 2016 г., 22:00
Я программирую игры, этот алгоритм кажется неправильным для любого приложения, в котором ребра многоугольника не гарантированно имеют одинаковую длину.
 11 июн. 2012 г., 18:49
@ Хэтчет, да, вот почему я сказал, что ты должен рассмотреть вопрос об использовании. Процедура обнаружения столкновений в игре отличается от навигации, а фрактальная береговая линия отличается от приложения CFD.
 11 июн. 2012 г., 18:46
Рассмотрим крайний пример многоугольника с двумя вершинами, очень удаленными от целевой точки, но с линией между ними, проходящей очень близко к целевой точке. Третья вершина треугольника находится на небольшом расстоянии от этой линии. Ярлык, который проверяет только линии, связанные с этой ближайшей вершиной, даст неправильный ответ.

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

Решение Вопроса

Corrected as per @jcaron's comment

Лучше всего сделать итерацию по всем линиям и найти минимальное расстояние от точки до отрезка.

Чтобы найти расстояние от точки до отрезка, вы сначала находите расстояние от точки до линии, выбирая произвольные точки.P1 а такжеP2 на линии (это может быть целесообразно использовать ваши конечные точки). Затем возьмите вектор изP1 к вашей точкеP0 и найти(P2-P1) . (P0 - P1) где. это скалярное произведение. Разделите это значение на||P2-P1||^2 и получить значениеr.

Теперь, если вы выбралиP1 а такжеP2 в качестве ваших очков, вы можете просто проверить, еслиr между 0 и 1. Еслиr  больше 1, тоP2 самая близкая точка, поэтому ваше расстояние||P0-P2||, Еслиr меньше 0, тоP1 самая близкая точка, поэтому ваше расстояние||P0-P1||.

Если0<r<1тогда ваше расстояниеsqrt(||P0-P1||^2 - r * ||P2-P1||^2)

Псевдокод выглядит следующим образом:

for p1, p2 in vertices:

  var r = dotProduct(vector(p2 - p1), vector(x - p1))
  //x is the point you're looking for

  r /= magnitude(vector(p2 - p1))

  if r < 0:
    var dist = magnitude(vector(x - p1))
  else if r > 1:
    dist = magnitude(vector(p2 - x))
  else:
    dist = sqrt(magnitude(vector(x - p1)) ^ 2 - r * magnitude(vector(p2-p1)) ^ 2)

  minDist = min(dist,minDist)
 02 сент. 2013 г., 13:36
есть ли какой-нибудь алгоритм для этого?
 01 сент. 2017 г., 21:12
Во-первых, вы также должны проверить, если точкаin полигон Если это так, верните ноль, в противном случае следуйте расчету @HansZ
 03 сент. 2013 г., 17:20
@Muneem Я обновил свой ответ для легкого для понимания псевдокода в конце.
 11 июн. 2012 г., 18:44
Я тоже так думаю. Этот SO-ответ говорит о поиске кратчайшего расстояния между точкой и отрезком:stackoverflow.com/questions/849211/… .
 04 дек. 2014 г., 16:45
Я считаю, что в описании и коде есть пара ошибок: r следует разделить на квадрат P1P2, а не PP1. Не проверили математику, но это согласуется с ответом, связанным с комментарием @hatchet, и это работает намного лучше!

Ваш ответ на вопрос