«техникалық физиканың машиналық графика элементтері» ПӘні бойынша



Pdf көрінісі
бет58/62
Дата15.01.2022
өлшемі0,98 Mb.
#111954
1   ...   54   55   56   57   58   59   60   61   62
Байланысты:
9282 (1)

Триангуляция тұрғызу алгоритмі  

Сонымен:  жазықтықта  N  нүкте  бар,  оларды  шығыңқы  қабыршақ  іші 

үшбұрыш  болатындай  етіп  қиылыспайтын  кесінділермен  қосу  керек.  В 

результате мы должны получить список ребер, образующих триангуляцию. 

Делоне  триангуляциясының  алгоритмін  қарастырайық.  Процесс 

жазықтықты Вороного аумақтарына бөлуден басталады. 

S N нүктелерден түратын көпшілік. 4 нүкте бір шеңберде жатпайды деп 

есептейік. 

р S нүктесі үшін Вороного аумағы V деп жазықтықтың осындай көптеген 

нүктелерін айтады, р қашықтық басқа S нүктелеріне қарағанда аз болады. 

S  екі  нүкте  арасындағы  кесіндінің  ортасындағы  перпендикуляр 

жазықтықты  екі  Вороного  аумағына  бөледі.  р  нүктесінің  Вороного  аумағы-

барлық осындай түзулердің қиылысуы. 

Пайда  болған  тордың  қабырғалары  ол-  орта  перпендикулярладың 

кесінділері.  Орта  перпендикулярларының  АВ,  ВС  кесінділеріне  қиылысуы 

сырттай  салынған  шеңбер  центрі  болып  табылады;  онда  АС  да  ортасынан 

перпендикулярмен бөлінеді. 

Соңында  аумақты  үшбұрыштармен  бөлеміз-  бұл  S  аумақтағы  Делоне 

триангуляциясы. 

Бұл триангуляцияның қасиеттері: 

1.  Делоне  триангуляцисын  кез  келген  локалды  өзгертуден  кейін 

үшбұрыштар  дұрыс  емес  болады.  АВС,  ABD  -дан  ACD,  BCD  –ға  өту  "флип" 

деп аталады. 

 

2.  Кез  келген  үшбұрышқа  іштей  сызылған 



шеңбер 

ішінде 


енді 

ешбір 


Делоне 

триангуляциясының ұшы жоқ. 

Жаңа нүкте үшін: 

1.  Орналасқан  үшбүрыш  ізделінеді,  егер  ол 

алдында  тұрғызылған  триангуляция  қабығында 

орналасқан болса; немесе 

2.  Егер  ол  қабыршақ  сыртында  болса,  жаңа  нүктені  жалғайтын  ұштар 

ізделінеді. 






Достарыңызбен бөлісу:
1   ...   54   55   56   57   58   59   60   61   62




©engime.org 2024
әкімшілігінің қараңыз

    Басты бет