Слабо простой многоугольник
В геометрии слабо простой многоугольник — это обобщение простого многоугольника , позволяющее сторонам многоугольника соприкасаться друг с другом ограниченным количеством способов. Разные авторы определяли слабо простые многоугольники по-разному:
- Одно из определений состоит в том, что, когда односвязное открытое множество на плоскости ограничено конечным числом отрезков, его граница образует слабо простой многоугольник. [1] Согласно этому определению, на изображении ABCDEFGHJKLM представляет собой слабо простой многоугольник, синим цветом обозначающий область, для которой он является границей. Этот тип слабо простого многоугольника может возникнуть в компьютерной графике и САПР как компьютерное представление многоугольных областей с отверстиями : для каждого отверстия создается «разрез», чтобы соединить его с внешней границей. На изображении выше ABCM представляет собой внешнюю границу плоской области с отверстием FGHJ. Разрез ED соединяет отверстие с внешней стороной и дважды проходится в результате чего получается слабо простое многоугольное представление.
- В альтернативном и более общем определении слабо простых многоугольников они являются пределами последовательностей простых многоугольников. Все полигоны в последовательности должны иметь один и тот же комбинаторный тип, со сходимостью на расстоянии Фреше . [2] Это формализует представление о том, что такой многоугольник позволяет сегментам соприкасаться, но не пересекаться. Это обобщает понятие многоугольной границы топологического диска: эта граница является пределом последовательности многоугольников, смещенных от нее внутри диска. Однако этот тип слабо простого многоугольника не обязательно образует границу региона, поскольку его «внутренняя часть» может быть пустой. Например, если обратиться к тому же изображению, то многоугольная цепочка ABCBA согласно этому определению является слабо простым многоугольником: ее можно рассматривать как предел «сжатия» многоугольника ABCFGHA.
Ссылки [ править ]
- ^ Думитреску, Адриан; Тот, Чаба Д. (2007). «Легкие ортогональные сети с постоянным геометрическим расширением». У Томаса, Вольфганга; Вейль, Паскаль (ред.). STACS 2007: 24-й ежегодный симпозиум по теоретическим аспектам информатики, Ахен, Германия, 22–24 февраля 2007 г., Труды (иллюстрированное издание). Спрингер. п. 177. ИСБН 978-3540709176 .
- ^ Чанг, Сянь-Чжи; Эриксон, Джефф; Сюй, Чао (2015). «Обнаружение слабо простых многоугольников». В Индике, Петр (ред.). Материалы двадцать шестого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, SODA 2015, Сан-Диего, Калифорния, США, 4–6 января 2015 г. {СИАМ}. стр. 1655–1670. arXiv : 1407.3340 . дои : 10.1137/1.9781611973730.110 .