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

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

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

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

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

В геометрии ломаная цепочка [ ^а] представляет собой связный ряд отрезков прямых . Более формально, многоугольная цепь — это кривая , определяемая последовательностью точек , называемых ее вершинами . Сама кривая состоит из отрезков, соединяющих последовательные вершины. ${\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-мерном случае ломаные цепи.
• Составная кривая Безье — обобщение, которое заменяет каждую прямую линию многоугольной цепи гладкой кривой.
• Расстояние звена — количество сегментов кратчайшей цепи, соединяющей две точки внутри многоугольника.
• Кусочная регрессия
• Путь (теория графов) — аналогичная концепция в абстрактных графах.
• Многогранный рельеф — трехмерное обобщение монотонной многоугольной цепи.
• Спирангл — спиральная многоугольная цепочка.
• Число палочки , инвариант узла, основанный на представлении узла как замкнутой многоугольной цепи.
• Траверс , применение в геодезии

Примечания

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

Рекомендации

1. Мельхорн, Курт ; Нэхер, Стефан (1999), LEDA: платформа для комбинаторных и геометрических вычислений, Cambridge University Press, стр. 758, ISBN 9780521563291.
2. О'Рурк, Джозеф (1998), Вычислительная геометрия на C, Кембриджские трактаты по теоретической информатике, 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. Открытый геопространственный консорциум (28 мая 2011 г.), Херринг, Джон Р. (редактор), Стандарт реализации OpenGIS® для географической информации - Простой доступ к функциям - Часть 1: Общая архитектура, 1.2.1, Открытый геопространственный консорциум , получено 15 января 2016 г.
8. Гомес, Йонас; Велью, Луис; Коста Соуза, Марио (2012), Компьютерная графика: теория и практика, CRC Press, стр. 186, ISBN 9781568815800.
9. Чейни, Уорд (2001), Анализ прикладной математики, Тексты для выпускников по математике, том. 208, Спрингер, с. 13, ISBN 9780387952796.
10. Буассонна, Жан-Даниэль; Тейо, Моник (2006), Эффективная вычислительная геометрия для кривых и поверхностей, Springer, с. 34, ISBN 9783540332596.
11. Муггео, Вито М.Р. (май 2008 г.), «Сегментировано: пакет R для соответствия моделям регрессии с ломаными связями» (PDF) , R News , 8 (1): 20–25