Простые многоугольники: определение и свойства

Введение

Форма, ограниченная непересекающимися отрезками линий.

В геометрии простой многоугольник — это многоугольник, который не самопересекается и не имеет отверстий. Иными словами, это кусочно-линейная кривая Жордана, состоящая из конечного числа отрезков. Эти многоугольники включают в себя в качестве частных случаев выпуклые многоугольники, звёздчатые многоугольники и монотонные многоугольники. Сумма внешних углов простого многоугольника составляет 360 градусов. Любой простой многоугольник с *n* сторонами может быть разбит на треугольники с помощью *n-3* его диагоналей, и согласно теореме о галерее искусств его внутренность видна из некоторых *n-3* его вершин. Простые многоугольники часто используются в качестве входных данных для задач вычислительной геометрии, включая проверку принадлежности точки многоугольнику, вычисление площади, построение выпуклой оболочки простого многоугольника, триангуляцию и поиск кратчайших евклидовых путей. Другие геометрические построения, связанные с простыми многоугольниками, включают отображение Шварца — Кристоффеля, используемое для нахождения конформных отображений, связанных с простыми многоугольниками, полигонализацию множеств точек, формулы конструктивной твердотельной геометрии для многоугольников и графы видимости многоугольников.

Определения

Простой многоугольник — это замкнутая кривая на евклидовой плоскости, состоящая из отрезков прямой, соединенных концами, образуя ломаную линию. Два отрезка прямой встречаются в каждой конечной точке, и других точек пересечения между отрезками нет. Никакое собственное подмножество отрезков не обладает теми же свойствами. Определение «простой» иногда опускается, подразумевая, что термин «многоугольник» относится к простому многоугольнику. Отрезки, образующие многоугольник, называются его сторонами или ребрами. Конечная точка отрезка называется вершиной (множественное число: вершины) или углом. Термины «ребра» и «вершины» более формальны, но могут быть неоднозначными в контексте, где также рассматриваются ребра и вершины графа; для избежания этой неоднозначности можно использовать более разговорные термины «стороны» и «углы». Количество ребер всегда равно количеству вершин. Некоторые источники допускают, чтобы два отрезка прямой образовывали развернутый угол (180°), в то время как другие этого не допускают, требуя, чтобы коллинеарные отрезки замкнутой ломаной линии объединялись в один более длинный отрезок. Две вершины называются соседними, если они являются конечными точками одной из сторон многоугольника. Простые многоугольники иногда называют многоугольниками Джордана, поскольку они являются кривыми Джордана; теорема Джордана о кривых может быть использована для доказательства того, что такой многоугольник разделяет плоскость на две области. Фактически, исходное доказательство этой теоремы Камиль Джордан начинал со специального случая простых многоугольников (указанного без доказательства). Область внутри многоугольника (его внутренность) образует ограниченное множество, топологически эквивалентное открытому диску по теореме Джордана — Шенфлиса, с конечной, но ненулевой площадью. Сам многоугольник топологически эквивалентен кругу, а область снаружи (внешность) — неограниченному связному открытому множеству с бесконечной площадью. Хотя формальное определение простого многоугольника обычно дается как система отрезков прямой, также возможно (и часто встречается в неформальном использовании) определить простой многоугольник как замкнутое множество на плоскости, являющееся объединением этих отрезков с внутренностью многоугольника. Диагональ простого многоугольника — это любой отрезок прямой, соединяющий две вершины многоугольника и полностью лежащий внутри многоугольника.

A simple polygon is a closed curve in the Euclidean plane consisting of straight line segments, meeting end to end to form a polygonal chain. Two line segments meet at every endpoint, and there are no other points of intersection between the line segments. No proper subset of the line segments has the same properties. The qualifier simple is sometimes omitted, with the word polygon assumed to mean a simple polygon. The line segments that form a polygon are called its edges or sides. An endpoint of a segment is called a vertex (plural: vertices) or a corner. Edges and vertices are more formal, but may be ambiguous in contexts that also involve the edges and vertices of a graph; the more colloquial terms sides and corners can be used to avoid this ambiguity. The number of edges always equals the number of vertices. Some sources allow two line segments to form a straight angle (180°), while others disallow this, instead requiring collinear segments of a closed polygonal chain to be merged into a single longer side. Two vertices are neighbors if they are the two endpoints of one of the sides of the polygon. Simple polygons are sometimes called Jordan polygons, because they are Jordan curves; the Jordan curve theorem can be used to prove that such a polygon divides the plane into two regions. Indeed, Camille Jordan's original proof of this theorem took the special case of simple polygons (stated without proof) as its starting point. The region inside the polygon (its interior) forms a bounded set topologically equivalent to an open disk by the Jordan–Schönflies theorem, with a finite but nonzero area. The polygon itself is topologically equivalent to a circle, and the region outside (the exterior) is an unbounded connected open set, with infinite area. Although the formal definition of a simple polygon is typically as a system of line segments, it is also possible (and common in informal usage) to define a simple polygon as a closed set in the plane, the union of these line segments with the interior of the polygon. A diagonal of a simple polygon is any line segment that has two polygon vertices as its endpoints, and that otherwise is entirely interior to the polygon.

Свойства

Внутренний угол простого многоугольника, в одной из его вершин, – это угол, образованный внутренней частью многоугольника в этой вершине. Вершина называется выпуклой, если ее внутренний угол меньше (прямого угла, 180°) и вогнутой, если внутренний угол больше. Если внутренний угол равен, то внешний угол в той же вершине определяется как его смежный угол, угол поворота от одной направленной стороны к следующей. Внешний угол положителен в выпуклой вершине и отрицателен в вогнутой вершине. Для любого простого многоугольника сумма внешних углов равна (одному полному обороту, 360°). Следовательно, сумма внутренних углов для простого многоугольника с n сторонами равна.

The internal angle of a simple polygon, at one of its vertices, is the angle spanned by the interior of the polygon at that vertex. A vertex is convex if its internal angle is less than (a straight angle, 180°) and concave if the internal angle is greater than If the internal angle is , the external angle at the same vertex is defined to be its supplement , the turning angle from one directed side to the next. The external angle is positive at a convex vertex or negative at a concave vertex. For every simple polygon, the sum of the external angles is (one full turn, 360°). Thus the sum of the internal angles, for a simple polygon with sides is
Every simple polygon can be partitioned into non overlapping triangles by a subset of its diagonals. When the polygon has sides, this produces triangles, separated by diagonals. The resulting partition is called a polygon triangulation. The shape of a triangulated simple polygon can be uniquely determined by the internal angles of the polygon and by the cross ratios of the quadrilaterals formed by pairs of triangles that share a diagonal. According to the two ears theorem, every simple polygon that is not a triangle has at least two ears, vertices whose two neighbors are the endpoints of a diagonal. A related theorem states that every simple polygon that is not a convex polygon has a mouth, a vertex whose two neighbors are the endpoints of a line segment that is otherwise entirely exterior to the polygon. The polygons that have exactly two ears and one mouth are called anthropomorphic polygons. According to the art gallery theorem, in a simple polygon with vertices, it is always possible to find a subset of at most of the vertices with the property that every point in the polygon is visible from one of the selected vertices. This means that, for each point in the polygon, there exists a line segment connecting to a selected vertex, passing only through interior points of the polygon. One way to prove this is to use graph coloring on a triangulation of the polygon: it is always possible to color the vertices with three colors, so that each side or diagonal in the triangulation has two endpoints of different colors. Each point of the polygon is visible to a vertex of each color, for instance one of the three vertices of the triangle containing that point in the chosen triangulation. One of the colors is used by at most of the vertices, proving the theorem.

Любой простой многоугольник можно разбить на непересекающиеся треугольники с помощью подмножества его диагоналей. Если многоугольник имеет n сторон, то получается n-2 треугольника, разделенных n-3 диагоналями. Полученное разбиение называется триангуляцией многоугольника. Форма триангулированного простого многоугольника однозначно определяется внутренними углами многоугольника и перекрестными отношениями четырехугольников, образованных парами треугольников, имеющих общую диагональ. Согласно теореме о двух ушах, любой простой многоугольник, который не является треугольником, имеет по крайней мере два уха – вершины, две соседние с которыми являются концами диагонали. Связанная теорема утверждает, что любой простой многоугольник, который не является выпуклым, имеет рот – вершину, две соседние с которой являются концами отрезка, который в противном случае полностью лежит вне многоугольника. Многоугольники, имеющие ровно два уха и один рот, называются антропоморфными многоугольниками. Согласно теореме о галерее искусств, в простом многоугольнике с n вершинами всегда можно найти подмножество, состоящее не более чем из ⌊n/3⌋ вершин, такое что каждая точка в многоугольнике видна хотя бы из одной выбранной вершины. Это означает, что для каждой точки в многоугольнике существует отрезок, соединяющий ее с выбранной вершиной и проходящий только через внутренние точки многоугольника. Один из способов доказать это – использовать раскраску графа на триангуляции многоугольника: всегда можно раскрасить вершины тремя цветами так, чтобы каждая сторона или диагональ в триангуляции имела два конца разных цветов. Каждая точка многоугольника видна вершине каждого цвета, например, одной из трех вершин треугольника, содержащего эту точку в выбранной триангуляции. Один из цветов используется не более чем для ⌊n/3⌋ вершин, что доказывает теорему.

Особые случаи

Каждый выпуклый многоугольник является простым многоугольником. Другим важным классом простых многоугольников являются звёздообразные многоугольники, то есть многоугольники, имеющие точку (внутри или на границе), из которой видна любая точка многоугольника. Монотонный многоугольник относительно прямой — это многоугольник, для которого любая прямая, перпендикулярная этой прямой, пересекает внутреннюю область многоугольника в связном множестве. Эквивалентно, это многоугольник, граница которого может быть разделена на две монотонные ломаные линии, являющиеся последовательностями рёбер, вершины которых при ортогональной проекции на прямую сохраняют тот же порядок, что и в самой ломаной линии.

Вычислительные задачи

В вычислительной геометрии несколько важных вычислительных задач оперируют входными данными в форме простого многоугольника. Задача проверки принадлежности точки многоугольнику заключается в определении, лежит ли заданная точка внутри простого многоугольника. Она может быть решена за линейное время; альтернативно, можно преобразовать данный многоугольник в структуру данных за линейное время, чтобы последующие проверки принадлежности точки многоугольнику выполнялись за логарифмическое время. Существуют известные простые формулы для вычисления площади внутренней части многоугольника, такие как формула шнурков для произвольных многоугольников и теорема Пика для многоугольников с целочисленными координатами вершин. Выпуклую оболочку простого многоугольника также можно найти за линейное время, что быстрее, чем алгоритмы для поиска выпуклых оболочек точек, не соединенных в многоугольник. Построение триангуляции простого многоугольника также может быть выполнено за линейное время, хотя алгоритм и сложен. Модификация того же алгоритма может быть использована для проверки, образует ли замкнутая полигональная цепь простой многоугольник (то есть, избегает ли она самопересечений) за линейное время. Это также приводит к алгоритму за линейное время для решения задачи об галерее искусств, использующему не более точек, хотя и не обязательно оптимальное их количество для данного многоугольника. Хотя любые две триангуляции одного и того же многоугольника можно преобразовать друг в друга с помощью операций переворота, заменяющих одну диагональ за раз, определение того, можно ли это сделать, используя только ограниченное число переворотов, является NP-полной задачей. Геодезический путь, кратчайший путь на плоскости, соединяющий две точки внутри многоугольника без выхода за его пределы, может быть найден за линейное время алгоритмом, использующим триангуляцию в качестве подпрограммы. То же самое верно и для геодезического центра – точки в многоугольнике, минимизирующей максимальную длину геодезических путей до всех остальных точек. Полигон видимости внутренней точки простого многоугольника, то есть множество точек, непосредственно видимых из данной точки по отрезкам, лежащим внутри многоугольника, может быть построен за линейное время. То же самое относится и к подмножеству, видимому хотя бы из одной точки заданного отрезка. Другие вычислительные задачи, изучаемые для простых многоугольников, включают построение самой длинной диагонали или самого длинного отрезка внутри многоугольника, выпуклого скелета (наибольшего выпуклого многоугольника, содержащегося в данном простом многоугольнике) и различных одномерных скелетов, аппроксимирующих его форму, включая медиальную ось и прямой скелет. Исследователи также изучали получение других многоугольников из простых многоугольников с использованием их параллельных кривых, объединений и пересечений, а также сумм Минковского, но эти операции не всегда приводят к простому многоугольнику в результате. Их можно определить таким образом, чтобы всегда создавать двумерную область, но для этого требуется тщательное определение операций пересечения и разности, чтобы избежать создания одномерных объектов или изолированных точек.

In computational geometry, several important computational tasks involve inputs in the form of a simple polygon. Point in polygon testing involves determining, for a simple polygon and a query point , whether lies interior to It can be solved in linear time; alternatively, it is possible to process a given polygon into a data structure, in linear time, so that subsequent point in polygon tests can be performed in logarithmic time. Simple formulae are known for computing the area of the interior of a polygon. These include the shoelace formula for arbitrary polygons, and Pick's theorem for polygons with integer vertex coordinates. The convex hull of a simple polygon can also be found in linear time, faster than algorithms for finding convex hulls of points that have not been connected into a polygon. Constructing a triangulation of a simple polygon can also be performed in linear time, although the algorithm is complicated. A modification of the same algorithm can also be used to test whether a closed polygonal chain forms a simple polygon (that is, whether it avoids self intersections) in linear time. This also leads to a linear time algorithm for solving the art gallery problem using at most points, although not necessarily using the optimal number of points for a given polygon. Although it is possible to transform any two triangulations of the same polygon into each other by flips that replace one diagonal at a time, determining whether one can do so using only a limited number of flips is NP complete. A geodesic path, the shortest path in the plane that connects two points interior to a polygon, without crossing to the exterior, may be found in linear time by an algorithm that uses triangulation as a subroutine. The same is true for the geodesic center, a point in the polygon that minimizes the maximum length of its geodesic paths to all other points. The visibility polygon of an interior point of a simple polygon, the points that are directly visible from the given point by line segments interior to the polygon, can be constructed in linear time. The same is true for the subset that is visible from at least one point of a given line segment. Other computational problems studied for simple polygons include constructions of the longest diagonal or the longest line segment interior to a polygon, of the convex skull (the largest convex polygon within the given simple polygon), and of various one dimensional skeletons approximating its shape, including the medial axis and straight skeleton. Researchers have also studied producing other polygons from simple polygons using their offset curves, unions and intersections, and Minkowski sums, but these operations do not always produce a simple polygon as their result. They can be defined in a way that always produces a two dimensional region, but this requires careful definitions of the intersection and difference operations in order to avoid creating one dimensional features or isolated points.

Связанные конструкции

Согласно теореме Римана о конформном отображении, любое простосвязное открытое подмножество плоскости может быть конформно отображено на диск. Отображение Шварца-Кристоффеля предоставляет метод для явного построения отображения из диска на любой простой многоугольник, используя заданные углы вершин и прообразы вершин многоугольника на границе диска. Эти прообразы обычно вычисляются численно. Любое конечное множество точек на плоскости, не лежащих на одной прямой, может быть соединено для формирования вершин простого многоугольника (допускающего углы в 180°); например, один из таких многоугольников является решением задачи коммивояжера. Соединение точек для формирования многоугольника таким образом называется полигонализацией. Каждый простой многоугольник может быть представлен формулой в конструктивной солидной геометрии, которая строит многоугольник (как замкнутое множество, включая внутреннюю область) из объединений и пересечений полуплоскостей, при этом каждая сторона многоугольника появляется ровно один раз в качестве полуплоскости в формуле. Преобразование -стороннего многоугольника в такое представление может быть выполнено за время . Граф видимости простого многоугольника соединяет его вершины ребрами, представляющими стороны и диагонали многоугольника. Он всегда содержит гамильтонов цикл, образованный сторонами многоугольника. Вычислительная сложность реконструкции многоугольника, имеющего заданный граф в качестве графа видимости и указанный гамильтонов цикл в качестве цикла сторон, остаётся открытой проблемой.