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

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

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

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

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

Вариации

Простой

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

Закрыто

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

монотонный

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

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

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

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

Из наборов точек

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

Приложения

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

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

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

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

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

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

См. также

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