Случайное размещение многоугольника внутри многоугольника

Question

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

Я изучал это на пару дней и не сделал заметного прогресса. Любые выводы будут оценены.

Answer 1

^{Отказ от ответственности:Если вы пытаетесь упаковать несколько полигонов внутри большего многоугольника, то я думаю, this problem is NP hard так что маловероятно, что эффективный и точный алгоритм может быть разработан, чтобы решить эту проблему. Многоугольник может непрерывно трансформироваться и вращаться в плоскости, что означает, что места размещения могут быть бесконечными, и это делает пространство решения задачи также бесконечным. Если вы просто пытаетесь найти, может ли меньший многоугольник помещаться внутри большего, мне не хватает эффективного ответа, но, как вы спросили: «Любые выводы будут оценены» - вот один из них.}

---

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

На изображении ниже показана ограничительная коробка и минимальный ограничивающий прямоугольник. Мы используем это для получения Fast Fail Filter (очень простая идея ... определена в следующем параграфе). Коробка (a), показанная ниже, быстрее вычисляется, тогда как поле (b) является более точным для фильтрации. Нарисуйте эту коробку, которая дает лучшую отдачу от инвестиций для вашего дела. Хотя на рисунке ниже они оба ограничивают эллипс вместо полигона, но вы получаете идею.

http://portal.ku.edu.tr/~cbasdogan/Tutorials/imageU21.JPG

^{(изображения взяты из: http://portal.ku.edu.tr/~cbasdogan/Tutorials/imageU21.JPG)}

Затруднение: Если какой-либо линии B пересекается с любой линии S, или если все линии S находятся вне В , B не может принимать S.

Фильтр с быстрым отказом: Получите ограничивающие прямоугольники B и S. Если вы не можете поместить ограничивающий прямоугольник S внутри ограничивающего прямоугольника B, то вы не можете поместить многоугольник S внутри многоугольника B. Таким образом, вы не сможете быстрее, если нет вероятность того, что B будет заключать S. Следующее изображение иллюстрирует три случая.

^{(изображения взяты из: http://www.cs.berkeley.edu/~ug/slide/pipeline/assignments/as4/figures/boundcull.gif)}

---

Препроцессирование: Определить уравнение линий, которые образуют B. хранить их в HashMap<<Point, Point>, Line> для шага это будет сделано позже.Вы можете однозначно определить линию по наклону m и перехватить c, а конечные точки вашей линии будут ключом () HashMap.

---

Алгоритм:

Для каждого S, который прошел вышеупомянутый фильтр:

1. Read точки S и определения линий, которые образуют S
2. Для каждой линии от S, см., если он пересекается с любой строкой B ^† (они хранятся в HashMap alr eady)
3. Если нет пересечения, S находится внутри B, и все, что вам нужно сделать, это просто нарисовать линии, не беспокоясь о пересечении.

В худшем случае, сложность этого алгоритма будет O (бс) для рисования каждого полигона.

---

^†_{Этот шаг записывается перебором держать Algo легко понять. В противном случае здесь возможно критическая оптимизация, которая даст результат быстрее. Вы можете фильтровать строки B. Вам не нужно рассматривать линию B для пересечения с S, если конечные точки линии B находятся слева от самой левой точки S или справа от самой правой точки S или выше S или ниже S. Это может сэкономить много расчетов.}

Answer 2

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

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

1. уплотнить меньшего многоугольника, добавляя вершины между существующими вершинами. На изображении ниже показано уплотнение линии.
2. Теперь для уплотненного многоугольника проверьте, все ли его точки лежат внутри внешнего многоугольника. Этот тест можно выполнить, вычерчивая линии с точки, выходящей на бесконечность с обеих сторон, и затем подсчитывая, сколько раз эта линия пересекалась с большим полигоном.
3. Если все точки находятся внутри, то полигон находится внутри.

---

_{First Image source.}

^{Second Image source.}