Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Төрт қырлы деректер құрылымы – екі өлшемді немесе үш өлшемді картаның топологиясын компьютерде бейнелеу тәсілі, яғни жабық бетке салынған граф. Оны алғаш рет Хорхе Столфи және Леонидас Дж. Гибас сипаттаған. Бұл қанатты жиектер деректер құрылымының бір түрі.
A quad edge data structure is a computer representation of the topology of a two dimensional or three dimensional map, that is, a graph drawn on a (closed) surface. It was first described by Jorge Stolfi and Leonidas J. Guibas. It is a variant of the earlier winged edge data structure.
Егжей-тегжейлер
Төртбұрышты қабаттар құрылымы олар сақталу әдісінен атын алды. Бір Edge құрылымы түсінік бойынша екі бетке, екі төбелікке және 4 жиекке сілтемелерді сақтайды. Сақталатын төрт жиек – екі сақталған бетке тіркелген екі төбеліктен басталатын жиектер.
The quad edge structure gets its name from the general mechanism by which they are stored. A single Edge structure conceptually stores references to up to two faces, two vertices, and 4 edges. The four edges stored are the edges starting with the two vertices that are attached to the two stored faces.
Қолданылуы
Winged Edge сияқты, төртбұрышты жиектік құрылымдар 2D немесе 3D көпбұрышты тордың топологиясын сақтау үшін бағдарламаларда қолданылады. Дұрыс төртбұрышты құрылымды қалыптастыру үшін тордың өзі жабық болуы міндетті емес. Төртбұрышты жиектік құрылымды пайдаланып, топология бойынша итерация жасау өте оңай. Көбінесе төртбұрышты топологияларға қол жеткізу бағытталған жиектер арқылы жүзеге асырылады. Бұл екі төбеге нақты атаулар беруге мүмкіндік береді (басталу және аяқталу), сондай-ақ беттерге де нақты атаулар береді (сол және оң, басталу тұрғысынан қарағанда және аяқталу бағытына қарайтын адамға қатысты). Төрт жиекке де төбелер мен беттерге сәйкес атаулар беріледі: басталудан сол, басталудан оң, аяқталудан сол және аяқталудан оң. Бағытталған жиекті кері бағыттағы жиекке айналдыруға болады. Белгілі бір беттің бойымен итерация жасау үшін тек сол беттің сол жағындағы (келісім бойынша) бағытталған бір жиек болуы және бастапқы жиекке жеткенше барлық сол жақ жиектерді аралау қажет.
Much like Winged Edge, quad edge structures are used in programs to store the topology of a 2D or 3D polygonal mesh. The mesh itself does not need to be closed in order to form a valid quad edge structure. Using a quad edge structure, iterating through the topology is quite easy. Often, the interface to quad edge topologies is through directed edges. This allows the two vertices to have explicit names (start and end), and this gives faces explicit names as well (left and right, relative to a person standing on start and looking in the direction of end). The four edges are also given names, based on the vertices and faces: start left, start right, end left, and end right. A directed edge can be reversed to generate the edge in the opposite direction. Iterating around a particular face only requires having a single directed edge to which that face is on the left (by convention) and then walking through all of the start left edges until the original edge is reached.