Для точки в неправильном многоугольнике, каков наиболее эффективный способ выбрать край, ближайший к точке?

Question

Учитывая неправильный многоугольник и точку в этом многоугольнике, как мне определить, какое ребро в многоугольнике ближе всего к точке?

Мне, вероятно, придется выполнить этот расчет для большого набора точек в пределах многоугольника (например, 50-200 точек).

Answer 1

1. Вычисление ближайшей точки на линии, касательной к каждому краю многоугольника.
2. Вычисление ближайшей точки на каждом отрезке линии (ребре многоугольника) к рассматриваемой точке.
3. Рассчитайте расстояние от ближайшей точки на каждом отрезке линии до рассматриваемой точки.
4. Найдите минимальное расстояние.Ответом является соответствующий многоугольник с минимальным расстоянием.

Каждый шаг этого алгоритма - это линейное время (O (n)).

Вот основные формулы для каждого изшаги:

Рассчитать ближайшую точку на линии, которая касается каждого ребра многоугольника.

• Пусть одна конечная точка ребра многоугольника будетp1 = {x1, y1}.
• Пусть другая конечная точка ребра многоугольника будет p2 = {x2, y2}.
• Пусть точка анализируемого полигона будет p3 = {x3,y3}.
• Пусть u будет процентом расстояния между p1 и p2, которое необходимо для нахождения точки на линии, образованной p1 и p2, такой, что p1+u(p2-p1) = точка на линии, ближайшая к p3 (отрезок линии между этой точкой и p3 также оказывается перпендикулярным линии, проходящей через p1 и p2).
• u = ((x3 - x1)(x2 - x1)+(y3 - y1)(y2 - y1)) / ((x2 - x1)^2 + (y2 - y1)^2)
• Пусть точка, ближайшая к p3 на линии, образованной p1 иp2 известен как pu = {xu, yu}
• xu = x1 + u (x2 - x1)
• yu = y1 + u (y2- y1)
• И, как мы уже говорили ранее pu = {xu, yu}
• Повторите эти вычисления для каждого ребра многоугольника (т.е. подставьте в новые p1s и p2s)

Рассчитайте ближайшую точку на каждой линииотрезок (край многоугольника) до рассматриваемой точки.

Точка pu является только самой близкой точкой на отрезке, когда 0 <= u <= 1.В противном случае подходящей конечной точкой отрезка является ближайшая точка к рассматриваемой точке.Таким образом, для каждого pu, p1, p2, and u, вычисленного на предыдущем шаге, выполните следующее:

• Let pc = {xc, yc} будет обозначаться как ближайшая точка на отрезке линии ребра многоугольника к рассматриваемой точке.
• IF u<0 THEN pc = p1
• ELSE IF u>1 THEN pc = p2
• ELSE pc = pu

Рассчитать расстояние от ближайшей точки на каждом отрезке линии до точки

• Расстояние между p3 и pc = `sqrt ((x3 - xc) ^ 2 + (y3 - yc) ^ 2)
• Повторите этот расчет для всех компьютеров

Найдите минимальное расстояние.Ответом является соответствующий многоугольник с минимальным расстоянием.

• Перебирайте все расстояния, пока не найдете наименьшее.Соответствующее ребро многоугольника является ответом.

Вот диаграмма, которая поможет вам понять, что представляют собой точки и терминология в этом посте:

....

Answer 2

Правильный ответ зависит от общей картины проблемы: что происходит, когда вы принимаете во внимание несколько запросов? Я предполагаю, что каждый запрос будет иметь дело с другой точкой. Но как насчет многоугольника? Ожидаете ли вы получить несколько запросов для одного и того же полигона? Или каждый раз полигон отличается?

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

Однако, если вы ожидаете какой-то предсказуемости и стабильности на стороне многоугольника задачи (достаточно много точечных запросов к одному и тому же многоугольнику или к фиксированному набору многоугольников), то ситуация кардинально меняется. Наилучшим подходом в этом случае было бы предварительно построить диаграмму Вороного на основе ребер внутри многоугольника (ов). Затем вы можете решить проблему определения местоположения точки (для которой существуют известные эффективные алгоритмы), чтобы определить, в какую область Вороного попадает точка запроса. Это сразу скажет вам, какой край является ближайшим.

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

P.S. Я вижу, что вы заявляете в своем вопросе, что вы собираетесь запустить его для большого набора точек для одного многоугольника. Это сразу делает решение на основе диаграмм Вороного верным. Дополнительные нюансы алгоритма могут зависеть от того, известен ли этот большой набор точек заранее или он поступает по точкам непредсказуемым образом.

Answer 3

См. Этот пост на SO для вдохновения расстояние от точки в пределах многоугольника до края многоугольника или это Наименьшее расстояние между точкой и отрезком линии