Вырезать прямоугольники с границы

Question

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

Вот что я хочу:

Обратите внимание, что на правой стороне границы получить сократим на несколько форм.

У меня есть граница как float[][], как в [nOfPoints] [xy]. Так, например:

[0][0] = 10; 
[0][1] = 10; 
[1][0] = 100; 
[1][1] = 10; 
[2][0] = 100; 
[2][1] = 100; 
[3][0] = 10; 
[3][1] = 100; 
[4][0] = 10; 
[4][1] = 10; 

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

помогите пожалуйста.

Answer 1

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

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

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

Комментарии:

• Вычитание выпуклый многоугольник из не-выпуклого многоугольника может привести к нескольким многоугольников. Какой многоугольник найден, зависит от начальной точки пересечения. Если отслеживать точки пересечения, которые потребляются при трассировке одного результирующего многоугольника, тогда процесс может быть повторен для непонятых пересечений, каждый раз находя больше фрагментов результата.
• В тех случаях, когда пересечения происходят в углу, все может запутаться. Один из способов - логически разбить пересечение на множество логических пересечений, каждое логическое пересечение представляет собой один юридический обход.
• Сегменты двух многоугольников могут быть параллельными, особенно в случае OP. Эти сегменты могут быть отбракованы как часть препроцесса. Если они находятся в противоположных направлениях, они представляют собой бесконечно тонкую внутреннюю часть, окруженную внешней поверхностью, если они находятся в одном и том же направлении, они представляют собой бесконечно тонкую внешность, окруженную внутренним пространством. В любом случае они могут быть отброшены.
• Предыдущий комментарий может показаться странным, поскольку после отбрасывания перекрывающихся сегментов логическое значение уже не находится между полигонами, но алгоритм требует, чтобы сущности были ориентированы правильно.Поэтому этот общий подход можно использовать для срезания многоугольников с кривыми, удерживая куски в одну сторону или другую.
• Вычитание многоугольников может привести к объектам, которые не являются простыми многоугольниками. Если вычитаемый многоугольник полностью находится внутри другого многоугольника, результатом может быть область с отверстием в ней. Если это вызывает беспокойство, вы можете подумать об использовании немного более сложной структуры, чтобы представлять регионы, которые используют несколько циклов для определения границ. Внешний контур области должен быть ориентирован против часовой стрелки, внутренние петли должны быть ориентированы по часовой стрелке.