В геометрии , A ломаный является связной серией линейных сегментов . Более формально полигональная цепь P - это кривая, заданная последовательностью точек, называемых ее вершинами . Сама кривая состоит из отрезков прямых, соединяющих последовательные вершины.
Имя [ редактировать ]
Многоугольная цепь может также называться многоугольной кривой , [1] многоугольным путем , [2] ломаной линией , [3] кусочно-линейной кривой , [3] ломаной линией [4] или, в географических информационных системах , линией или линейным кольцом . [5]
Варианты [ править ]
Простой ломаный является тот , в котором только последовательные (или первые и последние) сегменты пересекаются и только на их концах.
Замкнутая ломаная является тот , в котором первая вершина совпадает с последней, или, в качестве альтернативы, первая и последняя вершины также соединены с помощью линейного сегмента. [6] Простая замкнутая многоугольная цепь на плоскости является границей простого многоугольника . Часто термин « многоугольник » используется в значении «замкнутая многоугольная цепь», но в некоторых случаях важно провести различие между многоугольной областью и многоугольной цепью.
Полигональная цепь называется монотонной , если существует такая прямая L , что каждая прямая, перпендикулярная L, пересекает цепь не более одного раза. Всякая нетривиальная монотонная ломаная открыта. Для сравнения, монотонный многоугольник - это многоугольник (замкнутая цепь), который можно разделить ровно на две монотонные цепи. [7] Графики кусочно-линейных функций образуют монотонные цепочки относительно горизонтальной прямой.
Свойства [ править ]
Каждый набор не менее чем точек содержит многоугольный путь, состоящий не менее чем из ребер, все склоны которого имеют один и тот же знак. Это следствие теоремы Эрдеша – Секереса .
Приложения [ править ]
Многоугольные цепи часто можно использовать для аппроксимации более сложных кривых. В этом контексте алгоритм Рамера – Дугласа – Пекера может использоваться для поиска многоугольной цепи с несколькими сегментами, которая служит точным приближением. [8] [9]
При рисовании графов многоугольные цепи часто используются для представления ребер графов, в стилях рисования, где рисование ребер в виде отрезков прямых линий может вызвать пересечения, столкновения ребер с вершинами или другие нежелательные особенности. В этом контексте часто желательно рисовать края с минимальным количеством сегментов и изгибов, чтобы уменьшить визуальный беспорядок на чертеже; проблема минимизации количества изгибов называется минимизацией изгибов . [10]
Многоугольные цепочки также являются фундаментальным типом данных в вычислительной геометрии . Например, алгоритм определения местоположения точки Ли и Препараты действует путем декомпозиции произвольных плоских подразделений на упорядоченную последовательность монотонных цепочек, в которой проблема запроса местоположения точки может быть решена с помощью двоичного поиска ; Позже этот метод был усовершенствован, чтобы дать оптимальные временные рамки для задачи определения местоположения точки. [11]
В географической информационной системе строки могут представлять любую линейную геометрию и могут быть описаны с использованием хорошо известной текстовой разметки как LineString или MultiLineString . [5] Линейные кольца (или LinearRing ) - это замкнутые и простые многоугольные цепи, используемые для построения геометрии многоугольника.
См. Также [ править ]
- Цепь (алгебраическая топология) , формальная комбинация симплексов, которая в одномерном случае включает многоугольные цепи
- Составная кривая Безье - обобщение, в котором каждая прямая многоугольной цепи заменяется гладкой кривой.
- Расстояние связи , количество сегментов самой короткой цепи, которая связывает две точки в многоугольнике.
- Кусочная регрессия
- Путь (теория графов) , аналогичное понятие в абстрактных графах
- Многогранный рельеф , трехмерное обобщение монотонной многоугольной цепи
- Число палочек, инвариант узлов, основанный на представлении узла в виде замкнутой многоугольной цепи
- Траверс , применение в геодезии
Ссылки [ править ]
- ^ Гомес, Йонас; Велью, Луис; Коста Соуза, Марио (2012), Компьютерная графика: теория и практика , CRC Press, стр. 186, ISBN 9781568815800.
- ^ Чейни, Уорд (2001), Анализ прикладной математики , Тексты для выпускников по математике, 208 , Springer, стр. 13, ISBN 9780387952796.
- ^ a b Буассонна, Жан-Даниэль; Тейо, Моник (2006), Эффективная вычислительная геометрия для кривых и поверхностей , Springer, стр. 34, ISBN 9783540332596.
- ^ Muggeo, Vito MR (май 2008 г.), «сегментированный: пакет R для соответствия регрессионным моделям с ломаной линией» (PDF) , R News , 8 (1): 20–25
- ^ a b Открытый геопространственный консорциум ( 28 мая 2011 г. ), Херринг, Джон Р. (ред.), Стандарт реализации OpenGIS® для географической информации - Простой доступ к функциям - Часть 1: Общая архитектура , 1.2.1, Открытый геопространственный консорциум , получено 15.01.2016
- ^ Мельхорн, Курт ; Нахер, Стефан (1999), LEDA: платформа для комбинаторных и геометрических вычислений , Cambridge University Press, стр. 758, ISBN 9780521563291.
- ^ О'Рурк, Джозеф (1998), Вычислительная геометрия в C , Кембриджские тракты по теоретической информатике, Cambridge University Press, стр. 45, ISBN 9780521649766.
- ^ Ramer, Урс (1972), "итерационная процедура для полигональной аппроксимации плоских кривых", компьютерная графика и обработка изображений , 1 (3): 244-256, DOI : 10.1016 / S0146-664X (72) 80017-0.
- ^ Дуглас, Дэвид; Peucker, Thomas (1973), «Алгоритмы уменьшения количества точек, необходимых для представления оцифрованной линии или ее карикатуры», The Canadian Cartographer , 10 (2): 112–122, doi : 10.3138 / FM57-6770-U75U -7727.
- ^ Tamassia, Роберто (1987), "О вложении графа в сетке с минимальным количеством изгибов", SIAM журнала по вычислениям , 16 (3): 421-444, DOI : 10.1137 / 0216030.
- ^ Эдельсбруннер, Герберт ; Гибас, Леонидас Дж .; Стольй, Хорх (1986), "Оптимальное положение точки в монотонном подразделении", SIAM журнал по вычислениям , 15 (2): 317-340, DOI : 10,1137 / 0215023.
