Расстояние для перемещения двух полигонов, чтобы они касались краев

Лучше всего описано на изображении ниже.

Многоугольник

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

Я попытался просмотреть все линии в одном многоугольнике и все точки в другом, спроецировать точку на линию и получить разницу между точкой y и точкой проекции y, а затем найти минимальное расстояние. Однако у этого была проблема, заключающаяся в том, что если полигоны перекрываются, а самая дальняя линия в одном полигоне и самая дальняя точка в другом имеют минимальное расстояние, это даст результат, который приведет к перекрытию полигонов.

Редактировать: проецируя точку на линию, я имею в виду найти значение y для точки на линии, которая имеет то же значение x, что и исходная точка. Пропустите этот шаг, если значение x находится за пределами линии.


geometry computational-geometry polygons
person Jacob Parker    schedule 16.10.2015    source источник
comment
Я предлагаю добавить теги geometry и computational-geometry, чтобы привлечь больше читателей (сам не могу, правки должны быть больше 10 символов, гррр!)   -  person kebs    schedule 16.10.2015
comment
Так ? Вы получили два ответа и ни одного комментария или плюса от вас? Вы действительно заинтересованы? Вы нашли другое решение? Если да, пожалуйста, внесите свой вклад, вы также можете дать ответ на свой вопрос.   -  person kebs    schedule 18.10.2015

Ответы (2)


arrow_upward
2
arrow_downward

Я не уверен, что правильно понял ваше предложение (что такое «проецировать точку на прямую»?).

В любом случае, я бы попробовал это (псевдокод):

for pA: points of polygon A:
   for sB: segments of polygon B
      compute distance along y-axis d(pA,sB) and store in table
Find minimum distance in table: d1
Proceed as above by reversing A and B: d2
final d = min(d1,d2)

Но, к сожалению, это, вероятно, не очень хорошо, если ваши многоугольники вогнуты, что, похоже, так и есть.

person kebs    schedule 16.10.2015

arrow_upward
2
arrow_downward

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

На заданной вертикали вычислите разницу между самой высокой конечной точкой многоугольника и самой низкой точкой другого. Ответ — наименьшее различие между всеми вертикалями (которое может быть отрицательным числом).

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

Для двух полигонов размером N и M сортировка будет стоить O(N+M)Log(N+M)); тогда сканирование будет стоить примерно O((N+M)K), где K — среднее количество пересечений вертикали с полигоном, обычно небольшое число от 2 до 4.

person Yves Daoust    schedule 16.10.2015