Көпбұрышқа қажетті нүктелер тесті

Көпбұрыш  –  ол  жазықтықта  қарапайым  (өзара  қиылыспайтын),  сынық 

жабық сызықпен шектелген фигура.   

Сынық төбелерімен беріледі А

i 

(х

i

i

 ), i = 1,2,...,n. 

Есеп:  көпбұрыштың  растрлы  бұрандамасын  алу,  яғни  оның  ішкі 

нүктелеріне иницирлеу жүргізу.  

 Жордан таеоремасы: 

Қарапайым  жабық  тегіс  сынық  жазықтықты  байланысқан  екі 

компонентке бөледі: 

- шектелген, көпбұрыштың іші ; 

- шектелмеген сыртқы бөлік.  

Бұл  теорема  келесіде  қарастырылатын  алгоритмдердің  барлығы 

шектелген  уақыт  бойынша  жұмыс  істейтіндігін  білдіреді,  себебі  оларда  растр 

элементтерінің  соңғы  саны  қарастырылады.  Алгоритм  сыртқы  және  ішкі 

нүктелерді айыру керек.  

Көпбұрыштың қабырғаларын Е

i

 белгілейік:  [A

 , A

 ], i=1,2,...,n (n+1=1). 

Р

i

(х,у)  –  сыныққа  қатысты  емес  жазықтықтың  кейбір  нүктелері  болсын. 

Р

i

i

i

  нүктесінен  Q  нүктесін  алшақтату 

- көпбұрыш шекарасымен қиылысу болмайды, Р

i

 – сыртқы нүкте; 

i

 - сыртқы; 

i

 – ішкі нүкте. 

Егер  ешқандай  төбелеріне  тиместен 

сынықпен  қиылысатын  болса,  онда  мұндай 

қиылысуды маңызды деп атайды. 

Ереже: 

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

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