Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Қарапайым көпбұрыштарды үшбұрыштарға бөлу
Partition of a simple polygon into triangles
Есептеу геометриясында көпбұрыштарды үшбұрыштау – бұл көпбұрыштық аумақты (қарапайым көпбұрыш) P үшбұрыштар жиынтығына бөлу, яғни, өзара қиылыспайтын ішкі бөліктері бар және біріктірілгенде P-ге тең болатын үшбұрыштар жиынтығын табу.
In computational geometry, polygon triangulation is the partition of a polygonal area (simple polygon) P into a set of triangles, i. e., finding a set of triangles with pairwise non intersecting interiors whose union is P.
Үшбұрыштауды жазықтықтағы түзу сызықты графиктердің ерекше жағдайлары ретінде қарастыруға болады. Егер тесіктер немесе қосымша нүктелер болмаса, үшбұрыштау максималды сыртқы жазықтық графиктерді құрайды.
Triangulations may be viewed as special cases of planar straight line graphs. When there are no holes or added points, triangulations form maximal outerplanar graphs.
Қосымша ұштары жоқ көпбұрышты үшбұрышты есептеу
Уақыт өте келе, көпбұрыштарды үшбұрыштау үшін бірнеше алгоритмдер ұсынылған.
Over time, a number of algorithms have been proposed to triangulate a polygon.
Құлақтарды кесу әдісі
Қарапайым көпбұрыштарды үшбұрыштаудың бір жолы екі құлақ теоремасына негізделген, себебі кем дегенде 4 төбесі бар, тесігі жоқ кез келген қарапайым көпбұрышта кем дегенде екі "құлақ" болады – екі қабырғасы көпбұрыштың қабырғаларынан тұратын және үшіншісі толығымен оның ішінде жатқан үшбұрыштар. Алгоритм осындай құлақты табудан, оны көпбұрыштан жоюдан (соның нәтижесінде шарттарды орындамайтын жаңа көпбұрыш пайда болады) және тек бір үшбұрық қалғанша қайталаудан тұрады. Бұл алгоритмді іске асыру оңай, бірақ кейбір басқа алгоритмдерге қарағанда баяу, және ол тек тесігі жоқ көпбұрыштар үшін ғана жұмыс істейді. Дөңес және ойыс төбелердің жеке тізімдерін сақтайтын іске асыру O(n²) уақытта жұмыс істейді. Бұл әдіс құлақ кесілу және кейде құлақ қысу деп аталады. Құлақ кесудің тиімді алгоритмін Хоссам ЭльГинди, Хейзел Эверетт және Годфрид Туссент ашты.
One way to triangulate a simple polygon is based on the two ears theorem, as the fact that any simple polygon with at least 4 vertices without holes has at least two "ears", which are triangles with two sides being the edges of the polygon and the third one completely inside it. The algorithm then consists of finding such an ear, removing it from the polygon (which results in a new polygon that still meets the conditions) and repeating until there is only one triangle left. This algorithm is easy to implement, but slower than some other algorithms, and it only works on polygons without holes. An implementation that keeps separate lists of convex and concave vertices will run in O(n^(2)) time. This method is known as ear clipping and sometimes ear trimming. An efficient algorithm for cutting off ears was discovered by Hossam ElGindy, Hazel Everett, and Godfried Toussaint.
Байланысты объектілер мен мәселелер
Екі үшбұрыштылау мәселесі де үшбұрыштылаудың (геометрия) және көпбұрышты бөлудің ерекше жағдайы болып табылады. Минималды салмақты үшбұрыштылау – бұл үшбұрыштылау, ондағы мақсат – қабырғалардың жалпы ұзындығын барынша азайту. Нүктелер жиынының үшбұрыштылауы – нүктелер жиынының дөңгелек қабығының көпбұрышты үшбұрыштылауы. Делоне үшбұрыштылауы – нүктелер жиынына негізделген үшбұрыштылау құрудың тағы бір тәсілі. Ассоциаэдр – бұрыштары дөңгелек көпбұрыштың үшбұрыштылауларына сәйкес келетін политоп. Көпбұрыштармен үшбұрышты жабу, онда үшбұрыштар бір-бірін жабуы мүмкін. Көпбұрыштармен мозаикалау, мұндағы мақсат – бүкіл жазықты алдын ала белгіленген пішіндегі көпбұрыштармен жабу.
Both triangulation problems are a special case of triangulation (geometry) and a special case of polygon partition. Minimum weight triangulation is a triangulation in which the goal is to minimize the total edge length. A point set triangulation is a polygon triangulation of the convex hull of a set of points. A Delaunay triangulation is another way to create a triangulation based on a set of points. The associahedron is a polytope whose vertices correspond to the triangulations of a convex polygon. Polygon triangle covering, in which the triangles may overlap. Tiling by polygons, where the goal is to cover the entire plane with polygons of pre specified shapes.