В geometry, многоугольная цепочка - это связная серия из отрезков линии. Более формально, многоугольная цепочка P - это кривая, заданная последовательностью точек назвал его вершинами. Сама кривая состоит из отрезков прямых, соединяющих последовательные вершины.
Полигональная цепочка может также называться многоугольной кривой, многоугольным путем, ломаной, кусочно-линейной кривой, ломаной линией или, в географические информационные системы, линия или линейное кольцо .
A простая многоугольная цепочка - это цепочка, в которой только последовательные (или первая и последняя) сегменты пересекаются и только в своих конечных точках.
A замкнутая многоугольная цепочка - это цепочка, в которой первая вершина совпадает с последней, или, альтернативно, первая и последняя вершины также соединены отрезком прямой. Простая замкнутая многоугольная цепочка в плоскости является границей простого многоугольника. Часто термин «многоугольник » используется в значении «замкнутая многоугольная цепочка», но в некоторых случаях важно проводить различие между многоугольной областью и многоугольной цепью.
Многоугольная цепочка называется монотонной, если существует прямая L такая, что каждая линия, перпендикулярная L, пересекает цепочку не более одного раза. Всякая нетривиальная монотонная ломаная открыта. Для сравнения, монотонный многоугольник - это многоугольник (замкнутая цепь), который можно разделить ровно на две монотонные цепи. Графики кусочно-линейных функций образуют монотонные цепочки относительно горизонтальной прямой.
Набор из n = 17 точек имеет многоугольный путь с 4 наклонами одного знакаКаждый набор не менее points содержит многоугольный путь из не менее ребер, все склоны которого имеют одинаковый знак. Это следствие теоремы Эрдеша – Секереса.
Многоугольные цепи часто можно использовать для аппроксимации более сложных кривых. В этом контексте алгоритм Рамера – Дугласа – Пекера можно использовать для поиска многоугольной цепи с несколькими сегментами, которая служит точным приближением.
На отрисовке графика полигональные цепочки часто используются для представления ребер графов в стилях рисования, где рисование ребер в виде отрезков прямых линий может вызвать пересечения, столкновения ребер с вершинами или другие нежелательные особенности. В этом контексте часто желательно рисовать края с минимальным количеством сегментов и изгибов, чтобы уменьшить визуальный беспорядок на чертеже; проблема минимизации количества изгибов называется минимизацией изгибов.
Многоугольные цепочки также являются фундаментальным типом данных в вычислительной геометрии. Например, алгоритм определения местоположения для Ли и Препарата работает путем разложения произвольных плоских подразделений на упорядоченную последовательность монотонных цепочек в какая проблема с запросом местоположения точки может быть решена с помощью двоичного поиска ; позже этот метод был усовершенствован, чтобы дать оптимальные временные границы для задачи определения местоположения точки.
В географической информационной системе линии могут представлять любую линейную геометрию и могут быть описаны с помощью скважины -известный текст разметка как LineStringили MultiLineString. Линейные кольца (или LinearRing) - это замкнутые и простые многоугольные цепи, используемые для построения геометрии многоугольника.