Полигональная цепь

Связанная серия отрезков прямой

Простая многоугольная цепь

Самопересекающаяся полигональная цепь

Замкнутая многоугольная цепь

В геометрии полигональная цепь ^[a] — это связанная серия отрезков прямых . Более формально, полигональная цепь ⁠ ⁠ ${\displaystyle P}$ — это кривая, заданная последовательностью точек , называемых ее вершинами . Сама кривая состоит из отрезков прямых, соединяющих последовательные вершины. ${\displaystyle (A_{1},A_{2},\dots ,A_{n})}$

Вариации

Простой

Простая многоугольная цепь — это цепь, в которой пересекаются только последовательные сегменты и только в своих конечных точках.

Закрыто

Замкнутая полигональная цепь — это цепь, в которой первая вершина совпадает с последней, или, в качестве альтернативы, первая и последняя вершины также соединены отрезком прямой. ^[1] Простая замкнутая полигональная цепь на плоскости является границей простого полигона . Часто термин « полигон » используется в значении «замкнутая полигональная цепь», но в некоторых случаях важно провести различие между полигональной областью и полигональной цепью. Пространственная замкнутая полигональная цепь также известна как перекошенный «полигон» .

Монотонный

Набор из n =17 точек имеет многоугольную траекторию с 4 наклонами одного знака.

Полигональная цепь называется монотонной, если существует прямая линия L такая, что каждая линия, перпендикулярная L, пересекает цепь не более одного раза. Каждая нетривиальная монотонная полигональная цепь является открытой. Для сравнения, монотонный полигон — это полигон (замкнутая цепь), который можно разбить ровно на две монотонные цепи. ^[2] Графики кусочно-линейных функций образуют монотонные цепи относительно горизонтальной линии.

Параметризация

Каждый сегмент полигональной цепи обычно параметризуется линейно, используя линейную интерполяцию между последовательными вершинами. Для всей цепи в практических приложениях распространены две параметризации: каждому сегменту цепи может быть назначен единичный интервал параметра, соответствующий индексу первой вершины; поочередно каждому сегменту цепи может быть назначен интервал параметра, соответствующий длине сегмента, так что параметр равномерно соответствует длине дуги вдоль всей цепи.

Из точечных множеств

Каждый набор из по крайней мере точек содержит полигональный путь из по крайней мере ребер, в котором все наклоны имеют одинаковый знак. Это следствие теоремы Эрдёша–Секереша . ${\displaystyle n}$ ${\displaystyle \lfloor {\sqrt {n-1}}\rfloor }$

Приложения

Полигональные цепи часто могут использоваться для аппроксимации более сложных кривых. В этом контексте алгоритм Рамера–Дугласа–Пейкера может использоваться для поиска полигональной цепи с небольшим количеством сегментов, которая служит точной аппроксимацией. ^{[3] [4]}

В рисовании графов полигональные цепи часто используются для представления рёбер графов, в стилях рисования, где рисование рёбер в виде отрезков прямых линий может привести к пересечениям, столкновениям рёбер и вершин или другим нежелательным особенностям. В этом контексте часто желательно рисовать рёбра с как можно меньшим количеством отрезков и изгибов, чтобы уменьшить визуальный беспорядок на рисунке; ​​проблема минимизации количества изгибов называется минимизацией изгибов . ^[5]

Красная кривая Безье определяется контрольными точками P ₀ , ...,  P ₄ . Серая полигональная цепь, соединяющая контрольные точки, называется контрольным полигоном.

В компьютерном геометрическом проектировании гладкие кривые часто определяются списком контрольных точек , например, при определении сегментов кривой Безье . При соединении вместе контрольные точки образуют многоугольную цепь, называемую контрольным многоугольником .

Полигональные цепи также являются фундаментальным типом данных в вычислительной геометрии . Например, алгоритм определения местоположения точек Ли и Препараты работает путем разложения произвольных плоских подразделений в упорядоченную последовательность монотонных цепей, в которой задача запроса определения местоположения точек может быть решена с помощью бинарного поиска ; этот метод был позже усовершенствован, чтобы дать оптимальные временные границы для задачи определения местоположения точек. ^[6]

В географической информационной системе линии могут представлять любую линейную геометрию и могут быть описаны с использованием известной текстовой разметки как LineStringили MultiLineString. ^[7] Линейные кольца (или LinearRing) представляют собой замкнутые и простые многоугольные цепи, используемые для построения многоугольной геометрии.

Смотрите также

• Цепь (алгебраическая топология) , формальная комбинация симплексов, которая в одномерном случае включает полигональные цепи.
• Составная кривая Безье — обобщение, заменяющее каждую прямую линию многоугольной цепи гладкой кривой.
• Расстояние связи — число сегментов кратчайшей цепи, соединяющей две точки внутри многоугольника.
• Кусочная регрессия
• Путь (теория графов) , аналогичное понятие в абстрактных графах
• Многогранный рельеф , трехмерное обобщение монотонной многоугольной цепи.
• Спираль , спиральная многоугольная цепь.
• Число палочек , инвариант узла, основанный на представлении узла в виде замкнутой многоугольной цепи
• Теодолитный ход , применение в геодезии

Примечания

1. Полигональная цепь может также называться полигональной кривой , ^[8] полигональным путем , ^[9] полилинией , ^[10] кусочно-линейной кривой , ^[10] ломаной линией ^[11] или, в географических информационных системах , линией или линейным кольцом . ^[7]

Ссылки

1. Мельхорн, Курт ; Наэр, Стефан (1999), LEDA: Платформа для комбинаторных и геометрических вычислений, Cambridge University Press, стр. 758, ISBN 9780521563291.
2. О'Рурк, Джозеф (1998), Вычислительная геометрия на языке C, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, стр. 45, ISBN 9780521649766.
3. Рамер, Урс (1972), «Итеративная процедура для полигональной аппроксимации плоских кривых», Компьютерная графика и обработка изображений , 1 (3): 244–256, doi :10.1016/S0146-664X(72)80017-0.
4. Дуглас, Дэвид; Пойкер, Томас (1973), «Алгоритмы для сокращения количества точек, необходимых для представления оцифрованной линии или ее карикатуры», The Canadian Cartographer , 10 (2): 112–122, doi :10.3138/FM57-6770-U75U-7727.
5. Тамассиа, Роберто (1987), «О встраивании графа в сетку с минимальным числом изгибов», SIAM Journal on Computing , 16 (3): 421–444, doi :10.1137/0216030.
6. Эдельсбруннер, Герберт ; Гибас, Леонидас Дж.; Столфи , Хорхе (1986), «Оптимальное расположение точки в монотонном подразделении», SIAM Journal on Computing , 15 (2): 317–340, doi :10.1137/0215023.
7. Open Geospatial Consortium (2011-05-28), Херринг, Джон Р. (ред.), Стандарт внедрения OpenGIS® для географической информации — Простой доступ к объектам — Часть 1: Общая архитектура, 1.2.1, Open Geospatial Consortium , получено 2016-01-15
8. Гомес, Йонас; Велью, Луис; Коста Соуза, Марио (2012), Компьютерная графика: теория и практика, CRC Press, стр. 186, ISBN 9781568815800.
9. Чейни, Уорд (2001), Анализ для прикладной математики, Graduate Texts in Mathematics, т. 208, Springer, стр. 13, ISBN 9780387952796.
10. Буассонна, Жан-Даниэль; Тейо, Моник (2006), Эффективная вычислительная геометрия для кривых и поверхностей, Springer, стр. 34, ISBN 9783540332596.
11. Муггео, Вито MR (май 2008 г.), «сегментированный: пакет R для подгонки регрессионных моделей с ломаными связями» (PDF) , R News , 8 (1): 20–25