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

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

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

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

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

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

Ответ 1

Исправлено в соответствии с комментарием @jcaron

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

Чтобы найти расстояние от точки до отрезка, сначала вы должны найти расстояние от точки до линии, выбрав произвольные точки 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)

Ответ 2

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

Ответ 3

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

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

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

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

Ответ 4

Я могу помочь вам с этими указателями:

Расстояние можно рассчитать, используя запись в Википедии даже с непроверенным текстом.
Внутренняя/внешняя граница может быть решена с помощью Stack Post и ссылок

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

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

Ответ 5

Я не знаю о разнице в производительности по сравнению с остальными ответами, но в библиотеках boost C++ есть общая реализация, называемая distance. Он содержит информацию о сложности в каждом случае, а в вашем проблемном случае он является линейным.

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

Ответ 6

вы можете сделать вашу программу немного быстрее, используя тригонометрию и предложение sin