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

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

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

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

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

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

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

есептейік. 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

деп аталады. 

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

ішінде 

ешбір 

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

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

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

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

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

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

ізделінеді. 

жүктеу/скачать 0,98 Mb.

Достарыңызбен бөлісу: