Қабықшасыз кесінділермен шектелген фигура

Кіріспе

Бір-бірімен қиылыспайтын сызық кесінділерімен шектелген пішін. Геометрияда қарапайым көпбұрыш – өзімен-өзі қиылыспайтын және ішкі тесіктері жоқ көпбұрыш. Яғни, ол шекті сандағы сызық кесінділерінен тұратын бөлшектік сызықтық Жордан қисығы. Бұл көпбұрыштарға ерекше жағдайларда дөңес көпбұрыштар, жұлдыз тәрізді көпбұрыштар және монотонды көпбұрыштар жатады. Қарапайым көпбұрыш сыртқы бұрыштарының қосындысы – әр қарапайым көпбұрыштың қабырғалары диагональдары арқылы үшбұрыштарға бөлінеді, ал арт галерея теоремасы бойынша оның ішкі бөлігі оның кейбір төбелерінен көрінеді. Қарапайым көпбұрыштар көбінесе есептеу геометриясы мәселелеріне кіріс ретінде қарастырылады, оның ішінде көпбұрыш ішіндегі нүктені тексеру, ауданын есептеу, қарапайым көпбұрыштың дөңес қабығы, үшбұрыштау және Евклидтік ең қысқа жолдар. Қарапайым көпбұрыштармен байланысты геометриядағы басқа құрылымдарға қарапайым көпбұрыштарды қамтитын конформдық карталарды табу үшін қолданылатын Шварц-Кристоффель бейнелеуі, нүктелік жиынтықтың полигонализациясы, көпбұрыштар үшін конструктивті қатты геометриялық формулалар және көпбұрыштардың көріну графиктері кіреді.

Анықтамалар

Қарапайым көпбұрыш – Евклид жазықтығында түзу сызық сегменттерінен тұратын жабық қисық, олар бір-бірімен ұштасып, көпбұрыш тізбегін құрайды. Кез келген екі сызық сегменті бір соңғы нүктеде түйіседі, ал сегменттердің арасында басқа қиылысқан нүктелер жоқ. Сызық сегменттерінің ешбір бөлігінің жиынтығы сол қасиеттерге ие болмайды. Кейде «қарапайым» деген сөзді қолданбайды, сонда «көпбұрыш» термині қарапайым көпбұрышты білдіреді. Көпбұрышты құрайтын сызық сегменттері оның қабырғалары немесе жақтары деп аталады. Сегменттің соңғы нүктесі – шыңы (көпше түрінде: шыңдар) немесе бұрыш деп аталады. Қабырғалар мен шыңдар формальды ұғымдар, бірақ олар графтың қабырғалары мен шыңдарын қамтитын жағдайларда екіұшты болуы мүмкін; осы екіұштылықты болдырмау үшін «жақтар» және «бұрыштар» сияқты көбірек қолданылатын терминдерді пайдалануға болады. Қабырғалардың саны шыңдардың санымен әрқашан тең болады. Кейбір дереккөздер екі сызық сегментінің 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°-тан кіші болса, онда төбе дөңес болады, ал егер ішкі бұрыш 180°-тан үлкен болса, онда төбе ойыс болады. Егер ішкі бұрыш 180°-қа тең болса, онда сол төбедегі сыртқы бұрыш оның толықтырғышы (supplement) болып табылады, яғни бір бағытталған қабырғадан келесі бағытталған қабырғаға бұрылу бұрышы. Сыртқы бұрыш дөңес төбеде оң, ал ойыс төбеде теріс болады. Кез келген қарапайым көпбұрыш үшін сыртқы бұрыштардың қосындысы 360°-қа (бір толық айналым) тең. Осылайша, қабырғалары бар қарапайым көпбұрыштың ішкі бұрыштардың қосындысы (n-2) * 180°-қа тең. Кез келген қарапайым көпбұрышты оның диагональдарының бір жиыны арқылы бір-бірімен қиыспайтын үшбұрыштарға бөлуге болады. Егер көпбұрыштың қабырғалары болса, онда диагональдармен бөлінген үшбұрыштар пайда болады. Осы бөлініске көпбұрыштың үшбұрыштау делінеді. Үшбұрыштарға бөлінген қарапайым көпбұрыштың пішінін оның ішкі бұрыштары және диагональдармен ортақ үшбұрыштар жұбынан құралған төртбұрыштардың қиылыс қатынастары анықтайды. Екі құлақ теоремасына сәйкес, үшбұрыш емес кез келген қарапайым көпбұрыштың кем дегенде екі құлағы болады, яғни екі көрші төбесі диагональдің соңғы нүктелері болып табылатын төбелер. Бұған байланысты теоремада: конвекс емес кез келген қарапайым көпбұрыштың аузы болады, яғни екі көрші төбесі көпбұрыштан сыртқа шығып тұратын түзу кесіндісінің соңғы нүктелері болып табылатын төбе. Дәл екі құлағы мен бір аузы бар көпбұрыштар антропоморфты көпбұрыштар деп аталады. Көркем галерея теоремасына сәйкес, төбелері бар қарапайым көпбұрышта әрқашан төбелердің кіші жиынын табуға болады, олардың саны көпбұрыштың әрбір нүктесі таңдалған төбелердің бірінен көрінетіндей болады. Бұл, көпбұрыштың әрбір нүктесі үшін, тек көпбұрыштың ішкі нүктелері арқылы өтетін таңдалған төбеге жалғасатын түзу кесіндісі бар дегенді білдіреді. Мұны дәлелдеудің бір жолы – көпбұрыштың үшбұрыштауын қолданып, графты бояу: төбелерді әрқашан үш түспен бояуға болады, сондықтан үшбұрыштаудағы әр қабырғаның немесе диагональдің екі ұшы әртүрлі түстерде болады. Көпбұрыштың әрбір нүктесі әр түстің төбесінен көрінеді, мысалы, сол нүктені қамтитын үшбұрыштың үш төбесінен бірінен. Түстердің бірі теореманы дәлелдеу үшін төбелердің көпбұрысында қолданылады.

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.

Ерекше жағдайлар

Әрбір дөңгелек көпбұрыш қарапайым көпбұрыш болып табылады. Қарапайым көпбұрыштардың тағы бір маңызды класы – жұлдыз тәрізді көпбұрыштар, яғни әрбір нүктесінен (ішкі немесе шекарасындағы) барлық нүктені көруге болатын көпбұрыштар. Бір түзу сызыққа қатысты монотонды көпбұрыш – бұл көпбұрыш, оған перпендикуляр жүргізілген әрбір түзу сызық көпбұрыштың ішкі бөлігін жалғасқан жиынтық ретінде қиып өтеді. Басқаша айтқанда, бұл көпбұрыштың шекарасын екі монотонды көпбұрышты тізбекке бөлуге болады, олардың бұрыштары түзуге перпендикуляр проекцияланғанда тізбектегідей ретпен орналасады.

Есептеу проблемалары

Есептеу геометриясында бірнеше маңызды есептеу тапсырмалары қарапайым көпбұрыш нысанындағы кіріс деректерді қамтиды. Көпбұрыштағы нүктені тексеру қарапайым көпбұрыш пен сұраныс нүктесінің берілген нүктесінің ішкі жағында жатқандығын анықтауды қамтиды. Бұл сызықтық уақытта шешіледі; сондай-ақ, берілген көпбұрышты сызықтық уақытта деректер құрылымына өңдеуге болады, соның арқасында келесі нүктені көпбұрышта тексеру логарифмдік уақытта орындалады. Көпбұрыштың ішкі ауданын есептеуге арналған қарапайым формулалар белгілі. Оларға кез келген көпбұрыш үшін аяқ киім тігісі формуласы және бүтін координаттары бар көпбұрыш үшін Пик теоремасы кіреді. Қарапайым көпбұрыштың сыртқы қабығын да сызықтық уақытта табуға болады, бұл көпбұрышқа қосылмаған нүктелердің сыртқы қабығын табу алгоритмдерінен жылдам. Қарапайым көпбұрышты үшбұрыштарға бөлу де сызықтық уақытта орындалуы мүмкін, бірақ алгоритм күрделі. Сол алгоритмнің өзгертілген түрі жабық көпбұрыштың тізбегі қарапайым көпбұрыш құрайтынын (яғни өзін-өзі қиылыстардан аулақ болатынын) сызықтық уақытта тексеру үшін де қолданылуы мүмкін. Бұл сондай-ақ, берілген көпбұрыш үшін нүктелердің ең оптималды санын міндетті түрде қолданбаса да, ең көп нүктелерді пайдалана отырып, галерея мәселесін шешуге мүмкіндік беретін сызықтық уақыт алгоритміне әкеледі. Бір көпбұрыштың кез келген екі үшбұрышталмасын бір диагональды алмастыратын флиптер арқылы бір-біріне айналдыру мүмкін болғанымен, оны шектеулі сандағы флиптерді пайдаланып жасауға болатынын анықтау 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° бұрыштарға рұқсат етіледі) төбелерін құру үшін байланыстырылуы мүмкін; мысалы, мұндай көпбұрыштардың бірі – саяхатшы сатушысының мәселесінің шешімі. Нүктелерді осылай байланыстырып көпбұрыш құру процесі көпбұрыштық деп аталады. Кез келген қарапайым көпбұрышты құрастырмалы геометриядағы формула арқылы көрсетуге болады, бұл формула көпбұрышты (ішкі бөлігімен қоса, жабық жиынтық ретінде) жарты жазықтықтардың бірігіп не қиылысуы арқылы құрастырады, сонда көпбұрыштың әр қабырғасы формулада жарты жазықтық ретінде бір рет пайда болады. -жақты көпбұрышты осы форматқа түрлендіру операциясы уақыт ішінде орындалуы мүмкін. Қарапайым көпбұрыштың көріну графигі оның төбелерін көпбұрыштың қабырғалары мен диагональдарын көрсететін қабырғалармен байланыстырады. Ол әрқашан көпбұрыш қабырғаларынан құралған Гамильтон циклін қамтиды. Көріну графигі ретінде берілген граф бойынша көпбұрышты қайта құрудың есептеу күрделілігі, оның қабырғалар циклы ретінде белгіленген Гамильтон циклімен бірге, әлі де шешілмеген мәселе болып табылады.