տուն Բերանի խոռոչ Դելոնի դատարկ գնդակի մեթոդ. Շինարարությունը ընդհանուր դեպքում

Բերանի խոռոչ

Դելոնի դատարկ գնդակի մեթոդ. Շինարարությունը ընդհանուր դեպքում

օգոստոսի 20-ին, 20:41-ին, 2012 թ

Շրջանագծի հավասարման միջոցով Դելոնեի վիճակի ստուգման ալգորիթմի օպտիմիզացում և դրա կիրառում

Ես ձեզ գաղտնիք կպատմեմ այն մասին, թե ինչպես արագ ստուգել Դելոնեի վիճակը երկու եռանկյունների համար:
Իրականում, օպտիմիզացիան ինքնին նկարագրված է մի փոքր ավելի ցածր (տե՛ս «Դելոնեի պայմանը շրջանագծի հավասարման միջոցով ստուգելու ալգորիթմի օպտիմիզացում»), բայց ես ձեզ ամեն ինչ կարգով կասեմ:

Իմ դեպքում, եռանկյունավորումն օգտագործվում է պատկերների հետագծման մեջ՝ հարթությունը պարզունակ հատվածների (եռանկյունների) բաժանելու համար։ Ինչպես գիտեք, այն նույնպես բաժանված է մի քանի փուլերի՝ ճշգրտում, սահմանների բացահայտում, սահմանների շուրջ քայլում, ուրվագծերի մաքրում: Դա շատ է ընդհանուր տեսարան. Ես իսկապես կցանկանայի կանգ առնել, կարծում եմ դժվար փուլավլում է ինքնաթիռը.

Մուտքի մոտ

Սահմանները հայտնաբերելուց և անցնելուց հետո ես ստացա շատ արտաքին օղակներ ելքի վրա: Յուրաքանչյուր շոշափող ուրվագիծ ունի տարբեր գույներ. Յուրաքանչյուր նման շղթա պարունակում է նաև ներքին սխեմաների հայտնի քանակ:
Այսպիսով, «ինքնաթիռը ավլելու» տեսակետից, եթե արտաքին ուրվագծերը դիտարկենք առանձին, ապա մենք ունենք կետերի մի շարք, որոնցից յուրաքանչյուրն ունի մեկ հարևան աջ և ձախ: Նրանք. բոլոր կետերը փակված են շղթայի մեջ, չկա մեկ «կախված» կետ, և յուրաքանչյուր շղթա պարունակում է առնվազն 3 կետ (Նկար 1):

Նկար 1

Ինչ պետք է անել

Դուք պետք է ծածկեք գործիչը եռանկյուններով:

Որոնում

Գիրքը կարդալուց հետո ես չգտա Դելոնի եռանկյունաձևության կառուցման մեկ (գոնե մեկ) մեթոդ, որը գոնե ինչ-որ չափով հարմար լինի իմ դեպքին: Ես այլ գրքեր չեմ փնտրել։ Եվ սա բավական էր, մտքերս կարգի բերեց։ Արդյունքում նա հորինեց իր սեփական «հեծանիվը»։

Ալգորիթմ

1) Սկսելու համար, ենթադրենք, որ դիտարկվող նկարում կա միայն մեկ հաջորդականություն։ Այնուհետև ամեն ինչ հանգում է նրան, որ հաջորդաբար վերցնում ենք եռանկյունները: Մենք վերցնում ենք ցանկացած կետ և փորձում ենք եռանկյունի կառուցել հարևան կետերով: Եթե հնարավոր չեղավ կառուցել եռանկյուն (այս երկու կետերը միացնող գիծը հատվում է արդեն կառուցվածների հետ կամ ուղիղն անցնում է բացառման գոտում (Նկար 2), անցնում ենք հաջորդ կետ, ասենք աջ: Երբ հաջորդ եռանկյունին գտնվել է, մենք այն ավելացնում ենք ցանկում (Նկար 3) և հեռացնում ենք այն կետը, որտեղից այն կառուցվել է (Նկար 4):

Նկար 2

Նկար 3

Նկար 4

Եվս մեկ բան. հաջորդ եռանկյունը պահպանելիս անհրաժեշտ է գագաթները գրանցել ժամացույցի սլաքի ուղղությամբ (ճիշտ կոորդինատային համակարգում): Սա ապագայում օգտակար կլինի հաշվողական ռեսուրսները նվազեցնելու համար:

2) Կրկնեք 1-ին քայլը, մինչև մենք ավլենք ամբողջ ինքնաթիռը:

3) Եթե կան մի քանի հաջորդականություններ, այսինքն. մեկը, և դրա ներսում կա մեկ կամ մի քանի ներքին ուրվագիծ (Նկար 1): Այստեղ անհրաժեշտ է դիտարկել յուրաքանչյուր հաջորդականությունը առանձին: Վերցնենք մեկ այլ ներքին ուրվագիծ. Մեկ արտաքին և մեկ ներքինից մենք կկատարենք երկու միայնակ սխեման: Դա անելու համար դուք պետք է գտնեք երկու «պորտ» մի շրջանից մյուսը: «Պորտերի» պայման. դրանք չպետք է հատվեն միմյանց հետ (նույնիսկ դրանց ծայրերը չպետք է դիպչեն), և չպետք է հատվեն եզրագծային գծերով (Նկար 5):

Նկար 5

Նկար 6
4) Հաջորդը, դուք պետք է մեկ առ մեկ մուտքագրեք բոլոր ներքին հաջորդականությունները արդեն կազմված հաջորդականությունների մեջ՝ միմյանցից անջատված (կետ 3): Դուք պետք է այն միաձուլեք այն մեկի հետ, որը պարունակում է նորը: Ըստ սահմանման, ոչ մի ներքին հաջորդականություն չի շոշափվում կամ հատվում մյուսների հետ (և՛ արտաքին, և՛ բոլոր հնարավոր ներքինները), այնպես որ ամեն ինչ հարթ կընթանա:
Գտնելով նավահանգիստները (Նկար 6), հեշտ է կառուցել նոր հաջորդականություններ և շրջանցել դրանք՝ օգտագործելով ընթացիկ ալգորիթմի 1-ին և 2-րդ կետերը (Նկար 7):

Նկար 7

5) 4-րդ փուլից հետո մենք ունենք եռանկյունների ցանկ (Նկար 8): Կարծես առաջադրանքն արդեն ավարտված է, բայց մնում է նկարը գեղեցիկ դարձնել. ստուգել, որ Դելոնեի պայմանը կատարված է (Նկար 9):

Նկար 8

Նկար 9

6) Նայելով առաջ՝ ես ձեզ կասեմ վեցերորդ կետի մասին։ Այն բաղկացած է ստացված եռանկյունների ցանկի միջով հաջորդաբար անցնելուց՝ օգտագործելով թիվ 5 քայլը: Նախ, մենք բոլոր եռանկյունները նշում ենք որպես «կեղտոտ»: Յուրաքանչյուր ցիկլում մենք ստուգում ենք Դելոնի պայմանը յուրաքանչյուր եռանկյունու համար: Եթե պայմանը չկատարվում է, ապա մենք վերակառուցում և նշում ենք հարևանները և ընթացիկ եռանկյունը որպես «կեղտոտ»: Եթե պայմանը բավարարված է, ապա այն նշում ենք մաքուր։ Ալգորիթմի իմ ներդրման ժամանակ յուրաքանչյուր եռանկյունին կապ ունի իր հարևանների հետ: Այս դեպքում ամենաարագ աշխատում է 6-րդ կետը։

Ավելին հինգերորդ փուլի մասին

Հիմա, որքան գիտեմ, երկուսն են հնարավոր ուղիներըորոշեք, արդյոք եռանկյունները բավարարում են Դելոնի պայմանին, թե ոչ. 1) Ստուգեք հակադիր անկյունների գումարը. Այն պետք է լինի 180-ից փոքր: 2) Հաշվե՛ք շրջագծված շրջանագծի կենտրոնը և հաշվե՛ք 4-րդ կետի հեռավորությունը: Բոլորը գիտեն, որ Դելոնեի պայմանը բավարարվում է, եթե կետը գտնվում է սահմանափակ շրջանակից դուրս։

Հաշվողական հզորություն #1. 10 բազմապատկել/բաժանել և 13 գումարել/հանել:
Հաշվողական հզորություն #2. 29 բազմապատկել/բաժանել և 24 գումարել/հանել:

Հաշվողական հզորության տեսանկյունից, որը հաշվարկված է օրինակ գրքում, թիվ 1 տարբերակն ավելի շահավետ է։ Ես դա կիրականացնեի, եթե ոչ... (Նկար 10): Ինչպես պարզվեց արտադրությունից հետո այս մեթոդը«փոխակրիչի» վրա, արդյունքը անորոշություն էր: Սա տարբերակ է, երբ A անկյունն ինքնին ավելի քան 180 աստիճան է: Գրքում այն դիտարկվում է որպես անհատական մասնավոր մեթոդներից մեկը։ Եվ սրանով անհետանում է նրա ողջ նրբագեղությունը, թափանցիկությունն ու կատարումը։ Եվ նաև հետագայում պարզվեց, որ թիվ 2 մեթոդը կարող է շատ զգալիորեն օպտիմիզացվել։

Նկար 10

Շրջանակի հավասարման միջոցով Դելոնեի վիճակի ստուգման ալգորիթմի օպտիմիզացում

Հաջորդը մաքուր մաթեմատիկան է:

Այսպիսով, մենք ունենք.
M(X, Y) կետի պայմանի ստուգումը A(x1, y1), B(x2, y2), C(x3, y3) կետերով անցնող շրջանագծի հավասարմամբ կարելի է գրել հետևյալ կերպ.

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − դ) ⋅ նշան a ≥ 0

Մանրամասները կարելի է գտնել հիանալի գրքում: (Ոչ, ես հեղինակը չեմ)
Այսպիսով, ա նշանը անցման ուղղության նշանն է, հենց սկզբից ես եռանկյունները կառուցեցի ժամացույցի սլաքի ուղղությամբ, այնպես որ այն կարելի է բաց թողնել (հավասար է մեկին)։

A (x1 - X, y1 - Y), B (x2 - X, y2 - Y), B (x3 - X, y3 - Y);

D>=0

Նկար 11

Պարզ չէ՞:

Ըստ գրքի, կրկին.

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)* (y1*x2 - x1*y2)<= 0

Մենք ունենք՝ 15 բազմապատկման/բաժանման և 14 գումարման/հանման գործողություն:

Շնորհակալություն ուշադրության համար. Սպասում եմ քննադատության.

Մատենագիտություն

1. Սկվորցով Ա.Վ. Դելոնեի եռանկյունավորումը և դրա կիրառումը. - Տոմսկ: Հրատարակչություն Թոմ. Համալսարան, 2002. – 128 p. ISBN 5-7511-1501-5

GRID մոդելները սովորական բջիջների մոդելներ են:

Թող ներկայացվի կոորդինատային համակարգը
Եվ Եվ
. Օգտագործողի հավաքածուներ
և նմուշառման քայլերը
.

- կետի ֆիզիկական կոորդինատները.

Մենք հաշվարկում ենք
Եվ
,
- բիտ ցանց:

- քվանտացված արժեքներ. Իրական:

- ալգորիթմի պարամետր - միավորների քանակը, - քաշը. Որքան մոտ է կետը, այնքան մեծ է քաշը:

- հեռավորության աստիճանը (1 կամ 2):

Նորմալացման գործակից.

Ինչպես 1-ին մոտ, այնքան ավելի մեծ կշիռներով միավորներ են հաշվի առնվում:

Սա IDW մեթոդն է՝ երկար է, յուրաքանչյուր տ-ի համար անհրաժեշտ է գտնել հարևաններ։ Հարևանների հավաքածուն կարելի է արդյունավետորեն գտնել՝ ամենամոտ: Յուրաքանչյուր կետ արտադրում է որոշակի բարձրության «կեռ»: Շատ բան կախված է կետի սահմանման անկանոնությունից, դրա համար նրանք վերցնում են
կամ
դրանք. բաժանել հատվածների և կառուցել մոտակայքում գտնվող կետեր:

Առավելություն- պարզություն

Թերություն:

------Տոմս 14. Թիթեղյա մոդել. Դելոնի եռանկյունավորման ալգորիթմներ ------

1) Եռանկյունավորում (անագ).

Եռանկյունավորում– ֆունկցիայի կառուցում` մաս-մաս գծային ֆունկցիաների բազմության տեսքով

Եռանկյունավորում- ինտերպոլացիա ուռուցիկ տարածաշրջանում:

Եռանկյունավորում- հարթ գրաֆիկ, որի բոլոր ներքին եզրերը եռանկյուններ են. տարածությունը միմյանց կից եռանկյունների տեսքով առանց համընկնման ներկայացնելու եղանակ: Եռանկյունաձևությունը կառուցված է մի քանի կետերի վրա մի քանի ձևով:

Օպտիմալ եռանկյունավորում կառուցելու համար անհրաժեշտ է ալգորիթմ:

3 կետով անցնող ինքնաթիռ.

1) Գտեք եռանկյուն, որը
;

2)
- Կառուցեք հարթության հավասարումը.

Ստուգելու համար կետերը գտնվում են եռանկյան ներսում, թե ոչ, դուք պետք է արժեքը փոխարինեք գծերի հավասարման մեջ՝ եռանկյունու եզրեր: Եթե բոլոր 3 հավասարումները > 0, ապա ներսում:

Ներկայացման կառուցվածքը.

Յուրաքանչյուր եռանկյունություն պարունակում է նույն թվով եռանկյուններ:

, Որտեղ - ներքին միավորների քանակը,
- միավորների քանակը.

Ագահ եռանկյունաձևություն.

Բոլոր կետերը միացնում ենք եզրերով, ընտրում ենք նվազագույնը և ավելացնում եռանկյունաձևին։ Հաջորդը վերցնում ենք հաջորդ նվազագույնը, որը չի հատվում նախորդների հետ և այլն։ Արդյունքը ագահ եռանկյունավորումն է։

Դելոնեի եռանկյունավորում.

Ցանկացած եռանկյունու շուրջ շրջագծված շրջանագծի ներսը չի ներառում այլ եռանկյունների կետերը: Այն կառուցված է միակ ձևով։

Flip-ը եզրերի փոխանցում է: Այն թույլ է տալիս սովորական եռանկյունավորումից անցնել Դելոնեի եռանկյունավորում: Ստուգելու համար, թե արդյոք կետը պատկանում է շրջանագծին, փոխարինի՛ր, եթե< R, то внутри.

Դելոնեի վիճակ.

Երեք կետերով անցնող շրջանագծի հավասարումը.

Եթե զրոյից պակաս է, ապա արտաքին, հակառակ դեպքում՝ ներքին։

– Դելոնայի վիճակ.

Դելոնեի եռանկյունաձևության կառուցման ալգորիթմ.

1) Հետազոտվող կետերի ավելացում- պարզ կրկնվող ալգորիթմ.

Առկա է հավաքածու
ավելացնել եռանկյունին, կատարվում է շինարարություն
եռանկյունի պառակտում
վերակառուցում։ Զրոյական փուլում ավելացնում ենք 3-4 ֆիկտիվ կետեր, որոնք ակնհայտորեն ծածկում են մեր ծրարը, ներսում գտնվող բոլոր կետերը։ Այնուհետև մենք նետում ենք կետը, նայում, թե որ եռանկյունին է այն հարվածում, այն բաժանում ենք 3-ի, յուրաքանչյուր եռանկյունու համար ստուգում ենք Դելոնի պայմանը և կատարում եզրերի շրջադարձային փոխանցում։ Գոտիների փոփոխության միջին թիվը երեքն է:

Տեսական բարդություն

2) արագացման մեթոդներ.Վիճակագրորեն կախված կետերի հիման վրա: Սերմերի եռանկյունը այն եռանկյունն է, որի մեջ ընկել է նախորդ կետը: Այնուհետև մենք միացնում ենք երկու կետ `նախորդը և նորը:

Մենք անցնում ենք առաջին կետից մյուսը:

օգոստոսի 20-ին, 20:41-ին, 2012 թ

Շրջանագծի հավասարման միջոցով Դելոնեի վիճակի ստուգման ալգորիթմի օպտիմիզացում և դրա կիրառում

Պատկերի մշակում,
Ծրագրավորում

Իմ դեպքում, եռանկյունավորումն օգտագործվում է պատկերների հետագծման մեջ՝ հարթությունը պարզունակ հատվածների (եռանկյունների) բաժանելու համար։ Ինչպես գիտեք, այն նույնպես բաժանված է մի քանի փուլերի՝ ճշգրտում, սահմանների բացահայտում, սահմանների շուրջ քայլում, ուրվագծերի մաքրում: Սա ամենաընդհանուր տերմիններով է: Կցանկանայի կանգ առնել, կարծում եմ, ամենադժվար փուլում՝ ինքնաթիռը ավլելու։

Մուտքի մոտ

Սահմանները հայտնաբերելուց և անցնելուց հետո ես ստացա շատ արտաքին օղակներ ելքի վրա: Յուրաքանչյուր հուզիչ ուրվագիծ ունի տարբեր գույն: Յուրաքանչյուր նման շղթա պարունակում է նաև ներքին սխեմաների հայտնի քանակ:
Այսպիսով, «ինքնաթիռը ավլելու» տեսակետից, եթե արտաքին ուրվագծերը դիտարկենք առանձին, ապա մենք ունենք կետերի մի շարք, որոնցից յուրաքանչյուրն ունի մեկ հարևան աջ և ձախ: Նրանք. բոլոր կետերը փակված են շղթայի մեջ, չկա մեկ «կախված» կետ, և յուրաքանչյուր շղթա պարունակում է առնվազն 3 կետ (Նկար 1):

Նկար 1

Ինչ պետք է անել

Դուք պետք է ծածկեք գործիչը եռանկյուններով:

Որոնում

Ալգորիթմ

Նկար 2

Նկար 3

Նկար 4

2) Կրկնեք 1-ին քայլը, մինչև մենք ավլենք ամբողջ ինքնաթիռը:

Ավելին հինգերորդ փուլի մասին

Այժմ, որքան ես գիտեմ, երկու հնարավոր եղանակ կա որոշելու, թե արդյոք եռանկյունները բավարարում են Դելոնի պայմանին, թե ոչ. 1) Ստուգեք հակառակ անկյունների գումարը: Այն պետք է լինի 180-ից փոքր: 2) Հաշվե՛ք շրջագծված շրջանագծի կենտրոնը և հաշվե՛ք 4-րդ կետի հեռավորությունը: Բոլորը գիտեն, որ Դելոնի պայմանը բավարարվում է, եթե կետը գտնվում է սահմանափակ շրջանակից դուրս։

Հաշվողական հզորության տեսանկյունից, որը հաշվարկված է օրինակ գրքում, թիվ 1 տարբերակն ավելի շահավետ է։ Ես դա կիրականացնեի, եթե ոչ... (Նկար 10): Ինչպես պարզվեց, այս մեթոդը «կոնվեյերի» վրա դնելուց հետո անորոշություն առաջացավ։ Սա տարբերակ է, երբ A անկյունն ինքնին ավելի քան 180 աստիճան է: Գրքում այն դիտարկվում է որպես անհատական մասնավոր մեթոդներից մեկը։ Եվ սրանով անհետանում է նրա ողջ նրբագեղությունը, թափանցիկությունն ու կատարումը։ Եվ նաև հետագայում պարզվեց, որ թիվ 2 մեթոդը կարող է շատ զգալիորեն օպտիմիզացվել։

Նկար 10

Շրջանակի հավասարման միջոցով Դելոնեի վիճակի ստուգման ալգորիթմի օպտիմիզացում

Հաջորդը մաքուր մաթեմատիկան է:

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − դ) ⋅ նշան a ≥ 0

A (x1 - X, y1 - Y), B (x2 - X, y2 - Y), B (x3 - X, y3 - Y);

D>=0

Նկար 11

Պարզ չէ՞:

Ըստ գրքի, կրկին.

(x1^2 + y1^2)*(y2*x3 - x2*y3) + (x2^2 + y2^2)*(x1*y3 - y1*x3) + (x3^2 + y3^2)* (y1*x2 - x1*y2)<= 0

Մենք ունենք՝ 15 բազմապատկման/բաժանման և 14 գումարման/հանման գործողություն:

Շնորհակալություն ուշադրության համար. Սպասում եմ քննադատության.

Մատենագիտություն

Հիմնական սահմանումներ և հատկություններ

Եռանկյունաձևը հարթ գրաֆիկ է, որի ներքին տարածքները բոլորը եռանկյուններ են:

Հատկություններ:

· Դելոնեի եռանկյունաձևը մեկ առ մեկ համապատասխանում է Վորոնոյի դիագրամին նույն կետերի համար:

· Որպես հետևանք. եթե միևնույն շրջանագծի վրա չորս կետ չկա, Դելոնի եռանկյունաձևը եզակի է:

· Delaunay եռանկյունաձևությունը առավելագույնի է հասցնում նվազագույն անկյունը բոլոր կառուցված եռանկյունների բոլոր անկյունների միջև, դրանով իսկ խուսափելով «բարակ» եռանկյուններից:

· Դելոնեի եռանկյունավորումը առավելագույնի է հասցնում ներգծված գնդերի շառավիղների գումարը:

· Դելոնեի եռանկյունացումը նվազագույնի է հասցնում Դիրիխլեի դիսկրետ ֆունկցիոնալությունը:

· Դելոնեի եռանկյունավորումը նվազագույնի է հասցնում շրջակա միջավայրի նվազագույն շրջանակի առավելագույն շառավիղը:

· Ինքնաթիռի վրա Դելոնի եռանկյունությունն ունի եռանկյունների շուրջ նկարագրված շրջանագծերի շառավիղների նվազագույն գումարը բոլոր հնարավոր եռանկյունաձևությունների միջև:

Նկար 1. Եռանկյունաձևություն:

Ուռուցիկ եռանկյունությունը եռանկյունաձև է, որի համար բոլոր եռանկյունները պարփակող նվազագույն բազմանկյունը ուռուցիկ է: Եռանկյունաձևությունը, որը ուռուցիկ չէ, կոչվում է ոչ ուռուցիկ:

Երկչափ կետերի տրված բազմությունից եռանկյունություն կառուցելու խնդիրը տրված կետերն անջատված հատվածներով միացնելու խնդիրն է, որպեսզի ձևավորվի եռանկյունություն։

Եռանկյունաձևությունը բավարարում է Դելոնեի պայմանը, եթե տրված եռանկյունաձև կետերից ոչ մեկը չի ընկնում որևէ կառուցված եռանկյունի շուրջը շրջագծված շրջանագծի ներսում:

Եռանկյունությունը կոչվում է Դելոնեի եռանկյունություն, եթե այն ուռուցիկ է և բավարարում է Դելոնի պայմանը։

Նկար 2. Դելոնեի եռանկյունավորում:

Դելոնի դատարկ գնդակի մեթոդ. Շինարարությունը ընդհանուր դեպքում

Օգտագործենք դատարկ գնդակը, որը կշարժենք՝ փոխելով չափը, որպեսզի կարողանա դիպչել համակարգի (A) կետերին, բայց միշտ դատարկ մնա։

Այսպիսով, եկեք Դելոնի դատարկ գնդակը տեղադրենք միավորների համակարգում (A): Դա միշտ հնարավոր է, եթե ընտրեք բավական փոքր գնդակ: Եկեք սկսենք մեծացնել նրա շառավիղը՝ թողնելով գնդակի կենտրոնը տեղում: Ինչ-որ պահի գնդակի մակերեսը կհանդիպի համակարգի որոշ i կետի (A): Դա անպայման տեղի կունենա, քանի որ մեր համակարգում անսահման մեծ դատարկություններ չկան։ Մենք կշարունակենք մեծացնել դատարկ գնդակի շառավիղը, որպեսզի i կետը մնա դրա մակերեսին: Դա անելու համար դուք պետք է տեղափոխեք գնդակի կենտրոնը i կետից: Վաղ թե ուշ գնդակը իր մակերեսով կհասնի համակարգի մեկ այլ կետի (A):

Նկ.3

Delaunay simplexes-ը լրացնում է տարածությունը առանց բացերի կամ համընկնումների:

Ցանկացած սիմպլեքսի նկարագրված ոլորտն իր ներսում չի պարունակում համակարգի այլ կետեր։

Թող սա լինի կետ j. Շարունակենք մեծացնել մեր գնդակի շառավիղը՝ երկու կետերն էլ պահելով նրա մակերեսին։ Երբ գնդակը մեծանում է, այն կհասնի համակարգի ինչ-որ երրորդ կետի՝ k կետին: Երկչափ դեպքում մեր «դատարկ շրջանակը» այս պահին կֆիքսվի, այ. Շրջանակը դատարկ պահելով հանդերձ նրա շառավիղն ավելի մեծացնելն անհնար կդառնա։ Միևնույն ժամանակ մենք բացահայտում ենք երեք կետերի (i, j, k) տարրական երկչափ կոնֆիգուրացիա, որը սահմանում է որոշակի եռանկյուն, որի առանձնահատկությունն այն է, որ համակարգի (A) այլ կետեր չկան նրա շրջանագծի ներսում: Եռաչափ տարածության մեջ գնդակը չի սահմանվում երեք կետով: Շարունակենք մեծացնել նրա շառավիղը՝ պահպանելով նրա մակերեսի վրա հայտնաբերված բոլոր երեք կետերը։ Դա հնարավոր կլինի այնքան ժամանակ, քանի դեռ գնդակի մակերեսը չի հանդիպել համակարգի չորրորդ l կետին: Սրանից հետո դատարկ գնդակի շարժումն ու աճն անհնարին կդառնա։ Գտնված չորս կետերը (i, j, k, l) սահմանում են քառանիստի գագաթները, որը բնութագրվում է նրանով, որ դրա շրջագծված ոլորտի ներսում համակարգի այլ կետեր չկան (A): Նման քառաեդրոնը կոչվում է Դելոնի սիմպլեքս։

Մաթեմատիկայի մեջ սիմպլեքսը ամենապարզ պատկերն է տվյալ չափման տարածության մեջ. քառաեդրոնը՝ եռաչափ տարածության մեջ; եռանկյուն - երկու չափսերով: Համակարգի կամայական երեք (չորս) կետերը, որոնք չեն գտնվում նույն հարթության վրա, միշտ սահմանում են որոշակի սիմպլեքս: Այնուամենայնիվ, դա կլինի Delaunay simplex միայն այն դեպքում, եթե դրա նկարագրված գունդը դատարկ է: Այլ կերպ ասած, Դելոնեի պարզեցումները որոշվում են (A) համակարգի կետերի եռյակների (քառապատիկի) հատուկ ընտրությամբ:

Մենք կառուցել ենք մեկ Delaunay simplex, բայց դատարկ գնդակը տեղադրելով տարբեր տեղերում և կրկնելով նույն ընթացակարգը, մենք կարող ենք սահմանել մյուսները: Նշվում է, որ (A) համակարգի բոլոր Դելոնեի պարզեցումների բազմությունը լրացնում է տարածությունը առանց համընկնումների և բացերի, այսինքն. իրականացնում է տարածության բաժանումը, բայց այս անգամ քառաեդրոնների։ Այս բաժանումը կոչվում է Delaunay սալիկապատում(նկ. 3):

Դելոնեի եռանկյունավորման կիրառումը

Դելոնեի եռանկյունավորումները հաճախ օգտագործվում են էվկլիդյան տարածության մեջ։ Էվկլիդյան նվազագույն ընդգրկող ծառը երաշխավորված է, որ ընկած է Դելոնեի եռանկյունավորման վրա, ուստի որոշ ալգորիթմներ օգտագործում են եռանկյունավորում: Նաև Դելոնեի եռանկյունավորման միջոցով Էվկլիդեսյան ճանապարհորդող վաճառողի խնդիրը մոտավորապես լուծվում է։

2D ինտերպոլացիայի դեպքում Դելոնեի եռանկյունաձևությունը հարթությունը բաժանում է հնարավոր ամենահաստ եռանկյունների՝ խուսափելով չափազանց սուր և չափազանց բութ անկյուններից: Օգտագործելով այս եռանկյունները, դուք կարող եք կառուցել, օրինակ, երկգծային ինտերպոլացիա:

Գեոինֆորմատիկայում հաճախ հանդիպող մեկ այլ խնդիր լանջերի բացահայտման կառուցումն է: Այստեղ անհրաժեշտ է որոշել լանջերի գերիշխող ուղղությունները ըստ կարդինալ ուղղությամբ և մակերեսը բաժանել այն շրջանների, որոնցում գերակշռում է որոշակի ուղղություն։ Քանի որ բացահայտումը որոշելը իմաստ չունի մակերեսի հորիզոնական տարածքների համար, այն տարածքները, որոնք հորիզոնական են կամ ունեն թեթև թեքություն, հատկացվում են առանձին շրջանի, օրինակ.<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.

Նկ.4.

Լանջերի ազդեցության հաշվարկի խնդիրը սովորաբար օգտագործվում է Երկրի լուսավորությունը վերլուծելու համար: Այս առումով հաճախ անհրաժեշտություն է առաջանում լրացուցիչ հաշվի առնել Արեգակի ներկայիս դիրքը, այսինքն. ճառագայթումը հաշվարկվում է որպես ուղղություն դեպի եռանկյունի նորմալի և դեպի Արև ուղղության միջև:

Այսպիսով, յուրաքանչյուր եռանկյունաձև եռանկյունին կարելի է դասակարգել ըստ որոշակի տարածաշրջանին պատկանելու սկզբունքի: Դրանից հետո պարզապես անհրաժեշտ է զանգահարել տարածաշրջանի ընտրության ալգորիթմը:

Եռանկյունավորումը մոդելավորված առարկայի մակերևույթի մերձեցումն է եռանկյուն թիթեղներով, որոնք բաժանված են նրանից 6-ը չգերազանցող որոշակի արժեքից չգերազանցող հեռավորության վրա: Բոլոր եռանկյուն թիթեղները պետք է միացված լինեն միմյանց: Նրանց գագաթները ընկած են մակերեսի վրա: Եռանկյուն ափսեների հավաքածուն ավելի հեշտ է աշխատել, քան ընդհանուր մակերեսը: Եռանկյուն ափսեները մենք կանվանենք եռանկյուններ։ Եռանկյունու համար արագորեն հաշվարկվում է հեռավորությունը տվյալ կետից կամ տարածության մեջ տվյալ գծի հետ հատման կետից: Դեմքերի եռանկյունավորումն իրականացվում է երկրաչափական մոդելի տեսողական ընկալման համար, ուստի եռանկյունների կողմերն ընտրվում են այնպես, որ աչքը չկարողանա նկատել ոլորումները։

Մակերեւույթների պարամետրային հարթությունների վրա երկրաչափական առարկաները եռանկյուններով ցուցադրելիս պետք է կառուցվի մարմնի երեսների տարածական եռանկյունավորում՝ հաշվարկելով տարածության կետերի զանգվածը և այդ կետերում մարմնի երեսներին նորմալների զանգվածը՝ օգտագործելով զանգվածի զանգվածը: Երկչափ կետերը մարմիններն արագ ցուցադրելու համար նրանց դեմքերը մոտավորվում են եռանկյունաձև թիթեղներով, որոնք կառուցված են մարմնի դեմքերի հետ փոխազդող լուսային ճառագայթների վարքագիծը որոշելու համար: Նախորդ գլուխներում և այս գլխում հնչյունային գծագրերը պատրաստված են եռանկյունաձևության միջոցով:

Մակերեւութային եռանկյունավորման արդյունքում ցանկանում ենք պարամետրային հարթության վրա ունենալ երկչափ կետերի զանգված և ամբողջ թվերի եռյակներ, որոնք առաջին նշված զանգվածի կետերի թիվն են։ Այսպիսով, յուրաքանչյուր եռանկյուն կներկայացվի իր գագաթների երեք թվերով պարամետրային զանգվածում: Պարամետրային տիրույթի յուրաքանչյուր երկչափ կետի համար կարելի է հաշվարկել մակերեսի տարածական կետ և դրանում գտնվող նորմալ մակերես։ Տարածական կետերը և նորմալները կարող են պահվել 2D կետային զանգվածի նման զանգվածներում:

Դիտարկենք եռանկյունացման որոշ մեթոդներ: Հարթ մակերեսների համար կան ծախսարդյունավետ եռանկյունավորման մեթոդներ, որոնցում եռանկյունները կառուցվում են մակերեսի սահմանային կետերում, և պարամետրային շրջանի ներսում կետեր փնտրելու կարիք չկա:

Դելոնեի եռանկյունավորում.

Դիտարկենք ինքնաթիռի որոշ տարածք: Տարածքը ուռուցիկ կանվանենք, եթե նրա սահմանով շարժվելիս պետք է շրջվել միայն մեկ ուղղությամբ (միայն ձախ կամ միայն աջ): Դելոնեի ալգորիթմը կարող է օգտագործվել ուռուցիկ հարթ շրջանները եռանկյունավորելու համար։ Մենք չենք կարողանա ուղղակիորեն կիրառել այս ալգորիթմը ազատ ձևի մակերեսները եռանկյունավորելու համար, բայց մենք կօգտագործենք դրա մեթոդը եռանկյուններ կառուցելու համար:

Բրինձ. 9.7.1. Ուռուցիկ շրջան՝ ներսում տրված կետերով

Թող բերվի մի ուռուցիկ երկչափ շրջան, որը սահմանափակված է փակ ճեղքված գծով և այս շրջանի ներսում գտնվող կետերի հավաքածու (նկ. 9.7.1):

Պահանջվում է նշված տարածքը բաժանել եռանկյունների, որոնց գագաթները տարածքի ներսում տրված կետերն են և այն սահմանափակող կոտրված գծի գագաթները։ Եռանկյունները չպետք է համընկնեն միմյանց, և դրանց կողմերը կարող են հատվել միայն գագաթներով:

Որոշված տարածքը լրացնելու համար կարող են կառուցվել եռանկյունների մի քանի տարբեր խմբեր: Բոլոր դեպքերում եռանկյունների թիվը հավասար է , որտեղ K-ը սահմանող բազմուղիների գագաթների թիվն է, I՝ տարածքի ներսում տրված կետերի թիվը։

Բրինձ. 9.7.2. Ընտրելով Դելոնի ալգորիթմի երրորդ կետը

Տարածաշրջանի եռանկյունաձևությունը կլինի Դելոնեի եռանկյունություն, եթե յուրաքանչյուր եռանկյունու շուրջ նկարագրված շրջանագծի ներսում այլ եռանկյունների գագաթներ չկան: Դելոնեի եռանկյունաձևը կառուցում է եռանկյուններ հնարավորինս մոտ հավասարանկյուն (թույլ չի տալիս կառուցել անհիմն երկարաձգված եռանկյուններ):

Այն կարելի է անվանել հավասարակշռված: Դելոնի եռանկյունաձևությունը եզակի կլինի, եթե նույն շրջանի վրա չկան չորս գագաթներ:

Դիտարկենք Դելոնեի եռանկյունաձևությունը։ Տարածքը սահմանափակող բազմուղիների գագաթները և շրջանի ներսում տրված կետերը կանվանենք եռանկյունության գագաթներ։ Եռանկյունների կողմերը մենք կանվանենք եզրեր։ Եզրերից մենք ընտրում ենք սահմանափակող պոլիգծի հատվածներ, որոնք կանվանենք սահմանային եզրեր։ Եկեք կողմնորոշենք բոլոր սահմանային եզրերը, որպեսզի ուռուցիկ շրջանը ընկնի յուրաքանչյուր եզրից ձախ: Թող անհրաժեշտ լինի կառուցել եռանկյուն, որի կողմը AB սահմանային եզրն է, որը ներկայացված է Նկ. 9.7.2.

A, B գագաթների և ցանկացած գագաթի միջոցով, որը չի գտնվում նրանց հետ նույն գծի վրա, կարելի է շրջանագիծ գծել: Որպես եռանկյան երրորդ գագաթ, մենք ընտրում ենք V գագաթը, համապատասխան շրջանագիծը չի պարունակում AB հատվածի նկատմամբ այլ գագաթներ, որոնց վրա գտնվում է V կետը, ընդհանուր դեպքում, այդպիսի գագաթը կարող է գտնվել. Մենք այն կանվանենք ամենամոտը: A, B և V կետերով անցնող շրջանագծի կենտրոնը գտնվում է AB, BV և VA հատվածների միջնակետերին ուղղահայաց խաչմերուկում: Շրջանակի կենտրոնի դիրքը կբնութագրվի MN հատվածի t պարամետրով, որը ուղղահայաց է AB եզրին, երկարությամբ հավասար է և անցնում է AB եզրի կեսից:

Բրինձ. 9.7.3. Դելոնեի եռանկյունացման գործընթացը

AB հատվածի ձախ կողմում գտնվող բոլոր գագաթների համար մոտակա գագաթն ունի t ամենափոքր պարամետրը: Մոտակա գագաթին համապատասխան շրջանագիծը չի պարունակում AB հատվածից ձախ այլ գագաթներ։ Թող A, B և V գագաթները նկարագրվեն համապատասխանաբար երկչափ շառավղով վեկտորներով: AB և BV հատվածների միջնակետերի շառավղային վեկտորները հավասար կլինեն

A, B և V կետերով անցնող շրջանագծի կենտրոնի դիրքին համապատասխան տողի t պարամետրի արժեքը հավասար է.

AB հատվածի ձախ կողմում ամենամոտ գագաթի համար t պարամետրն ունի նվազագույն արժեք:

Եկեք կողմնորոշենք բոլոր սահմանային եզրերը, որպեսզի եռանկյունավորվող տարածքը ընկնի դրանցից յուրաքանչյուրից ձախ: Մենք սկսում ենք եռանկյուններ կառուցել ցանկացած սահմանային եզրից: Գտնենք նրա համար ամենամոտ գագաթը, որի համապատասխան շրջանագիծն այլ գագաթներ չի պարունակում։ Թող գտնվի մոտակա V գագաթը AB սահմանային եզրի համար, այնուհետև մենք կառուցում ենք ABV եռանկյունին և AB եզրը տեղափոխում ենք ոչ ակտիվի կատեգորիա: Մենք կանվանենք ոչ ակտիվ եզրեր և գագաթներ, որոնք չեն մասնակցում եռանկյունավորման ալգորիթմին: Եթե սահմանային եզրերի մեջ չկա BV եզր, ապա մենք կառուցում ենք նոր սահմանային եզր VB հատվածի վրա: Եթե սահմանային եզրերի մեջ կա BV եզր, ապա այն և B գագաթը տեղափոխում ենք ոչ ակտիվների կատեգորիա։ Եթե սահմանային եզրերի մեջ չկա VA եզր, ապա մենք կկառուցենք նոր սահմանային եզր AV հատվածի վրա: Եթե սահմանային եզրերի մեջ կա VA եզր, ապա այն և A գագաթը տեղափոխում ենք ոչ ակտիվների կատեգորիա։ Եռանկյունացման գործընթացը ներկայացված է Նկ. 9.7.3.

Բրինձ. 9.7.4. Դելոնեի եռանկյունավորում

Մենք ավարտում ենք եռանկյունաձևությունը, երբ բոլոր գագաթները և ծայրերը դառնում են անգործուն: Տվյալ տարածքի եռանկյունացման արդյունքը ներկայացված է Նկ. 9.7.4.

Եռանկյունավորում ուղղման մեթոդով.

Դիտարկենք ուղղանկյուն տիրույթով որոշակի մակերևույթի եռանկյունաձևությունը՝ պարամետրերի սահմանման համար։ Համաձայն (9.4.7) բանաձևի հարակից տողերի միջև պարամետրային հեռավորությունները հավասար են:

Համաձայն (9.4.8) բանաձևի հարակից տողերի միջև պարամետրային հեռավորությունները հավասար են:

Բոլոր ուղղանկյուն բջիջներում շեղանկյուններ կառուցելով` մենք ստանում ենք մակերեսի եռանկյունաձևություն (ստացվում է պահանջներին համապատասխանող եռանկյունների մի շարք): Նկ. 9.7.5-ում ներկայացված է պտույտի մակերեսի եռանկյունաձևությունը՝ օգտագործելով նկարագրված մեթոդը:

Դիտարկենք կամայական սահման ունեցող մակերեսի եռանկյունացումը: Եռանկյունավորման մեթոդը մենք կկառուցենք վերը նկարագրված մակերևույթի եռանկյունաձևության սահմանային ուրվագծերով ուղղման վրա՝ պարամետրերը որոշելու համար ուղղանկյուն տարածքով:

Բրինձ. 9.7.5. Ուղղանկյուն տիրույթով մակերևույթի եռանկյունավորում՝ պարամետրերի սահմանման համար

Թող մակերևույթի սահմանը պարամետրի սահմանման տիրույթում նկարագրվի մի քանի չհատվող երկչափ ուրվագծերով (2.12.7): Եզրագծերից մեկը արտաքին է և պարունակում է մնացած ուրվագծերը: Յուրաքանչյուր ուրվագծի դրական ուղղության համար մենք կվերցնենք այն ուղղությունը, որի երկայնքով շարժվելիս մակերեսի սահմանման տարածքը միշտ գտնվում է եզրագծի ձախ կողմում, երբ նայում ենք դեպի մակերևույթը նորմալ: Մակերեւույթի սահմանման տարածքի սահմանային ուրվագծերի դրական ուղղությամբ կառուցենք բազմանկյուններ։ Սահմանային բազմանկյուններ կառուցելու համար անհրաժեշտ է որոշակի փոփոխական քայլով քայլել մակերեսի սահմանային ուրվագծերով և լրացնել երկչափ կետերի զանգված, որոնց կոորդինատներն են մակերեսի պարամետրերը: Մենք պարամետրային հարթության կետերից կկառուցենք բազմանկյուն, բայց մի կետից մյուսը տեղափոխելիս քայլը կորոշվի տարածական երկրաչափությունից, այն է՝ այն պայմանից, որ հարակից կետերի միջև կորի աղեղի շեղումը տրվածից ոչ ավելի է։ արժեքը։ Մակերեւույթի սահմանային եզրագծի կորի համար բազմանկյուն կառուցելու պարամետրային քայլերը մենք հաշվարկում ենք (9.4.4) բանաձևով:

Յուրաքանչյուր բազմանկյուն բաղկացած է երկչափ կետերի դասավորված բազմությունից։ Նման տարածքները մենք կօգտագործենք որպես սահմանային եզրեր, իսկ պոլիգոնների այն կետերը, որոնց վրա հիմնված են եզրերը, կօգտագործվեն որպես եռանկյունաձև գագաթներ: Քանի որ մակերեսի պարամետրերի որոշման տարածքը գտնվում է սահմանային բազմանկյունների ձախ կողմում, յուրաքանչյուր սահմանային եռանկյունության եզրի համար եռանկյուններ կառուցելիս պետք է փնտրել եռանկյան երրորդ գագաթը եզրից ձախ:

Եկեք որոշենք, թե որ հանգույցներն են գտնվում սահմանային բազմանկյունների ներսում, և որոնք են գտնվում եզրագծի վրա կամ մակերեսի սահմանման տարածքից դուրս: Օգտագործելով այս տեղեկությունը՝ մենք ուղղանկյուն ցանցի բջիջները դասավորում ենք երկու խմբի: Առաջին խումբը ներառում է բջիջներ, որոնք ամբողջությամբ գտնվում են այն տարածքում, որտեղ որոշվում են մակերեսի պարամետրերը (բջիջները չպետք է դիպչեն սահմանային բազմանկյուններին): Երկրորդ խումբը ներառում է մնացած բջիջները (պառկած են մակերեսի սահմանման տարածքից դուրս կամ հատվում են սահմանային բազմանկյուններով):

Բրինձ. 9.7.6. Մակերեւույթի անավարտ եռանկյունավորում

Առաջին խմբի յուրաքանչյուր բջիջի ներսում, օգտագործելով անկյունագիծ, մենք կկառուցենք երկու եռանկյուն: Այսպիսով, մենք ստանում ենք անավարտ եռանկյունություն: Եզրագծերով սահմանափակված պտույտի մակերևույթի համար առաջին խմբի բջիջներում եռանկյուններ կառուցելու օրինակ ներկայացված է Նկ. 9.7.6.

Երկրորդ խմբի բջիջների չհատվող կողմերի վրա կկառուցենք սահմանային եզրեր և ուղղենք այնպես, որ համապատասխան բջիջը լինի եզրից ձախ։ Առաջին խմբի բջիջների շուրջ մենք կկառուցենք փակ կոտրված գիծ (հնարավոր է մի քանի փակ գիծ), որպեսզի դրա երկայնքով շարժվելիս տարածքի այն հատվածը, որը եռանկյունների չբաժանված է, ընկնի ձախ կողմում, երբ նայում է դեպի մակերեսը նորմալ: . Մենք նաև կօգտագործենք այս կոտրված գծի ուղիղ հատվածները որպես սահմանային եզրեր: Մենք բոլոր եզրերը հավասար կհամարենք։ Եռանկյունությունը ավարտելու համար մենք պետք է եռանկյուններ կառուցենք սահմանային եզրերի միջև: Յուրաքանչյուր եզրի համար մենք կփնտրենք գագաթ, որը գտնվում է դրա ձախ կողմում և կարող է օգտագործվել եռանկյունի կառուցման համար: Մենք կփնտրենք գագաթ միայն այն գագաթների մեջ, որոնք գտնվում են եզրի հետ նույն բջիջում: Գագաթն ընտրելու համար մենք օգտագործում ենք վերևում նկարագրված Դելոնեի մեթոդը և նկարազարդված Նկ. 9.7.2. Եթե գտնվի նման գագաթ, ապա պետք է ստուգել, թե արդյոք եռանկյան երկու նոր եզրերը հատվում են որևէ սահմանային եզրի հետ: Թող AB սահմանային եզրի համար գտնվի մոտակա V գագաթը և ստուգենք, որ BV և VA հատվածները չհատեն մյուս սահմանային եզրերը: Այնուհետև մենք կկառուցենք ABV եռանկյունը և AB եզրը կփոխանցենք ոչ ակտիվ կատեգորիայի: Եթե սահմանային եզրերի մեջ չկա BV եզր, ապա VB հատվածի վրա կկառուցենք նոր սահմանային եզր, իսկ եթե սահմանային եզրերի մեջ կա BV եզր, ապա այն և B գագաթը կտեղափոխենք ոչ ակտիվների կատեգորիա։ Եթե սահմանային եզրերի մեջ չկա VA եզր, ապա AV հատվածի վրա կկառուցենք նոր սահմանային եզր, իսկ եթե սահմանային եզրերի մեջ կա VA եզր, ապա այն և գագաթը A կտեղափոխենք ոչ ակտիվների կատեգորիա:

Եթե հատվածը կամ VA-ն հատում է այլ սահմանային եզրեր, ապա մենք անցնում ենք մոտակա գագաթի որոնմանը մեկ այլ սահմանային եզրի համար: Եռանկյունավորումը կավարտվի այն բանից հետո, երբ բոլոր եզրերն ու գագաթները դասակարգվեն որպես ոչ ակտիվ:

Բրինձ. 9.7.7. Եռանկյունավորում ուղղման մեթոդով

Նկ. 9.7.7-ում ներկայացված է մակերևույթի եռանկյունաձևությունը սահմանային ուրվագծերով հատված բջիջներում եռանկյունների ուղղման մեթոդով: Նկ. 9.7.8, օգտագործելով ստացված եռանկյունացումը, մակերեսը ինքնին ցուցադրվում է:

Եթե սահմանային բազմանկյունները և մակերեսը ունեն որոշակի սիմետրիա, ապա ուղղիչ մեթոդով եռանկյունավորումը կունենա նմանատիպ համաչափություն։

Եռանկյունավորում կլանման մեթոդով.

Դիտարկենք եռանկյունավորման ևս մեկ մեթոդ. Արագությամբ զիջում է Դելոնեի եռանկյունաձևությանը և նրա մոդիֆիկացիաներին։ Եռանկյունավորման ընթացակարգը սկսելու համար անհրաժեշտ է մակերևույթի սահմանը ներկայացնել փակ բազմանկյունների տեսքով: Եռանկյունավորման գործընթացում մենք պետք է որոշենք քայլերը՝ հիմնված մակերեսի պարամետրերի վրա: Շարժման հայտնի ուղղության դեպքում այս քայլերը որոշվում են բանաձևերով (9.4.6): Մակերեւույթի պարամետրերի մոտավոր քայլերը կարելի է գտնել հետևյալ կերպ. Եկեք որոշենք պարամետրային հարթության վրա մի շրջան որոշակի կետի շուրջ այնպես, որ այս շրջանի ցանկացած տարածական հատված կետից կետ մակերևույթից ոչ ավելի հեռու լինի, քան տրված S արժեքը:

Դա անելու համար մենք հաշվարկում ենք պարամետրերի թույլատրելի ավելացումները կոորդինատային գծերի երկայնքով

որտեղ են կետում մակերեսի առաջին և երկրորդ քառակուսային ձևերի գործակիցները: Որպես անհրաժեշտ շրջանի սահման՝ մենք կվերցնենք էլիպս՝ կենտրոնով կետում և կիսաառանցքներով: Այս էլիպսը ունի հավասարումը

Եթե ցանկանում եք հարթության վրա գտնել կետ և առանցքի անկյան կողմից տրված կետի կողքին, ապա դրա պարամետրերը կլինեն.

Նախ, եկեք դիտարկենք ավելի պարզ դեպք, երբ մակերեսի պարամետրերի տարածքը սահմանափակվում է մեկ արտաքին եզրագծով: Մակերեւույթի սահմանը մենք մոտեցնում ենք պարամետրային տիրույթի փակ բազմանկյունով: Եռանկյունաձևություն կառուցելիս կօգտագործենք աշխատանքային բազմանկյունը, որն այս դեպքում կընդունենք որպես արտաքին եզրագծի բազմանկյուն։ Ստացված երկչափ կետերի զանգվածին կավելացնենք բազմանկյան կետերը։ Աշխատանքային տարածքի եզրից կկառուցենք եռանկյուններ՝ նեղացնելով այն այնքան, մինչև աշխատանքային տարածքում մնա ընդամենը երեք կետ։

Եկեք գտնենք մի գագաթ աշխատանքային բազմանկյունում, որտեղ այն վերածվում է շրջանի: Այդպիսի կետ միշտ գոյություն ունի, և նրա մոտ պտտման անկյունն ավելի փոքր է։ Այս կետը նշանակենք O-ով, իսկ դրա պարամետրերը՝ Այս կետի մոտակայքում կկառուցենք մեկ կամ երկու եռանկյուն՝ կախված պտտման անկյունից։ Եթե անկյունն ավելի փոքր է, ապա այս երեք կետերի վրա կկառուցենք մեկ եռանկյուն (նկ. 9.7.9): Հակառակ դեպքում սրա վրա կկառուցենք երկու եռանկյուն, երկու հարևան և մեկ նոր կետ (նկ. 9.7.11): Նոր կետը նշանակված է P-ով: Մենք կփնտրենք P կետ B OS P զուգահեռագծի անկյունագծի վրա: Եթե զուգահեռագծի գագաթն ընկած է էլիպսի ներսում (նկ. 9.7.10), ապա այն կընդունենք որպես P կետ: Հակառակ դեպքում, որպես P կետ կվերցնենք էլիպսի և զուգահեռագծի անկյունագիծը: Վերջին դեպքում ամենևին էլ պետք չէ փնտրել էլիպսի և հատվածի հատումը։

P կետի կոորդինատները որոշվում են O BC կետերի կոորդինատների միջոցով

OP հատվածի անկյունը հորիզոնականի հետ որոշվում է հավասարությամբ

(9.7.8)

Այս տվյալները հնարավորություն են տալիս որոշել P կետի դիրքը էլիպսի նկատմամբ (9.7.5):

Այն դեպքում, որը ցույց է տրված Նկ. 9.7.9, եկեք կառուցենք եռանկյուն (հիշենք նրա գագաթների թվերը) և ջնջենք O կետը աշխատանքային տարածքում, Նկարում ներկայացված դեպքում: 9.7.11, մենք կկառուցենք երկու եռանկյունի և աշխատանքային տարածքում O կետը կփոխարինենք P կետով և վերջինս կտեղադրենք ստացված կետերի զանգվածում: Նկ. Նկար 9.7.12-ում ներկայացված է երկու եռանկյուններ կառուցելուց և O կետը վերացնելուց հետո ստացված բազմանկյունը: Երկու դեպքում էլ O կետը կհեռացվի աշխատանքային բազմանկյունից և աշխատանքային բազմանկյունը կնեղանա: Նշենք, որ եռանկյունները կարելի է կառուցել միայն այն դեպքում, երբ աշխատանքային տարածքը նեղացնելուց հետո ինքն իրեն չի հատվում:

Բրինձ. 9.7.9. Եռանկյունի կառուցում

Բրինձ. 9.7.10. Արդյունք բազմանկյուն

Բրինձ. 9.7.11. Երկու եռանկյունների կառուցում

Բրինձ. 9.7.12. Արդյունք բազմանկյուն

Նման իրավիճակները ներկայացված են Նկ. 9.7.13. Նրանք կարող են առաջանալ, երբ կառուցված եռանկյունների կողմերը հատում են աշխատանքային տարածքի կողմերը, որոնք հարակից չեն նրանց: Նախքան նոր եռանկյուն կառուցելը, ինչպես ցույց է տրված Նկ. 9.7.9-ում, իսկ նկ. 9.7.11, պետք է ստուգել, որպեսզի համոզվեք, որ ստացված բազմանկյունն ինքն իրեն չի հատվում:

Ընդ որում, P կետի դիրքը որոշելիս կարևոր է, որ այն գտնվի աշխատանքային տարածքի այլ կետերից բավարար հեռավորության վրա և մոտ չգա տարածքի կետերը միացնող հատվածներին։ Հակառակ դեպքում, ապագայում կարող են դժվարություններ առաջանալ եռանկյուններ կառուցելիս: Հետեւաբար, նախքան աշխատանքային բազմանկյունը նեղացնելը, դուք պետք է ստուգեք ստացված բազմանկյունը ինքնահատման համար: Եթե անհնար է եռանկյունի (եռանկյունի) կառուցել O կետի մոտ, ապա դրա փոխարեն պետք է գտնել մեկ այլ կետ, որտեղ բազմանկյունը ավելի շատ է փաթաթվում եզրագծի ներսում, քան մյուսներում և կատարել նկարագրված գործողությունները:

Հաջորդը, փոփոխված աշխատանքային տարածքով, մենք կկատարենք նույն գործողությունները, որոնք մենք հենց նոր նկարագրեցինք: Գտնենք աշխատանքային բազմանկյունի մի կետ, որում այն ավելի շատ է պտտվում տարածքի ներսում, քան մյուս կետերում, ստուգենք նրանում գտնվող բազմանկյունը նեղացնելու հնարավորությունը՝ կառուցելով մեկ կամ երկու եռանկյուն և նեղացնել բազմանկյունը։

Բրինձ. 9.7.13. Դուք չեք կարող եռանկյուններ կառուցել այս անկյունում

Շարունակելով այս գործընթացը՝ մենք կընդլայնենք երկչափ կետերի և եռանկյունների զանգվածը, և միևնույն ժամանակ կնեղացնենք աշխատանքային բազմանկյունը՝ փոքրացնելով նրա ծածկած տարածքը և կետերի քանակը։ Այս գործողությունների ինչ-որ փուլում մենք կստանանք երեք կետից բաղկացած աշխատանքային բազմանկյուն: Եկեք այս կետերում կառուցենք վերջին եռանկյունը, վերացնենք աշխատանքային տարածքը և ավարտենք եռանկյունաձևությունը: Նկարագրված եռանկյունավորման մեթոդում աշխատանքային տարածքով սահմանափակված տարածքը, ինչպես ասվում է, վերացվում է դրանից եռանկյուններ կտրելով:

Դիտարկենք ընդհանուր դեպքը, երբ մակերեսի պարամետրերի տարածքը սահմանափակվում է մեկ արտաքին եզրագծով և մի քանի ներքին եզրագծով, որոնք ամբողջությամբ գտնվում են արտաքին եզրագծի ներսում: Մակերեւույթի սահմանը մենք մոտեցնում ենք պարամետրային տիրույթի փակ բազմանկյուններով: Յուրաքանչյուր եզրագծի համար մենք կկառուցենք մեր սեփական բազմանկյունը: Ինչպես ուրվագծերի, այնպես էլ դրանց վրա կառուցված բազմանկյունների դեպքում, պետք է պահպանվի նրանց փոխադարձ կողմնորոշման կանոնը։ Ներքին բազմանկյունների կողմնորոշումը պետք է հակառակ լինի արտաքին բազմանկյունի կողմնորոշմանը: Սկսենք եռանկյունաձևը կառուցել արտաքին ուրվագծային բազմանկյունով: Եկեք դրա կետերը դնենք ստացված երկչափ կետերի զանգվածի մեջ և բազմանկյունն ինքնին դարձնենք աշխատանքային:

Մենք կկառուցենք եռանկյուններ այնպես, ինչպես պարզապես միացված շրջանի դեպքում: Եկեք աշխատանքային տարածքում գտնենք O կետը, ստուգենք այնտեղ աշխատանքային տարածքը նեղացնելու հնարավորությունը և նեղացնենք տարածքը: Եթե կան ներքին եզրագծեր, ապա ավելի դժվար է դառնում ստուգել ընտրված կետում աշխատանքային տարածքը նեղացնելու հնարավորությունը: Ի հավելումն աշխատանքային տարածքի կողմերի հետ եռանկյունների կողմերի հատման նկարագրված ստուգումների, անհրաժեշտ է ստուգել եռանկյունների կողմերի հատումը բոլոր ներքին բազմանկյունների կողմերի հետ:

Եկեք ստուգենք O կետում երկու եռանկյունի կառուցելու հնարավորությունը (նկ. 9.7.11) և գտնենք, որ նոր P կետը, երբ կառուցվի, կընկնի ներքին բազմանկյուններից մեկի ներսում կամ անընդունելի մոտ կլինի նրա հատվածներին: Այս դեպքում մենք չենք կառուցի P կետը, փոխարենը կներառենք այս ներքին բազմանկյունը աշխատանքային բազմանկյունի մեջ՝ կառուցելով Նկարում ներկայացված երկու եռանկյունները։ 9.7.14.

Ներքին բազմանկյուններից մեկի կետերը աշխատանքային բազմանկյունում ներառելու համար ներքին բազմանկյունի կետերից գտնում ենք աշխատանքային բազմանկյունի C կետին (O կետին կից) ամենամոտ կետը։

Եկեք կառուցենք եռանկյուններ OCF և CEF կետերում և աշխատանքային տարածքի O և C կետերի միջև, տեղադրենք ներքին բազմանկյունի կետերը, սկսած F կետից և վերջացրած E կետով: Այսպիսով, մենք կկոտրենք OS հատվածի աշխատանքային տարածքը, կջարդենք ներքին բազմանկյուն EF հատվածի վրա և միավորել դրանք OF և EU հատվածների հետ:

Բրինձ. 9.7.14. Երկու եռանկյունների կառուցում

Բրինձ. 9.7.15. Արտաքին և ներքին բազմանկյունների միաձուլում

Միաձուլման արդյունքը ներկայացված է Նկ. 9.7.15. Իհարկե, արտաքին և ներքին բազմանկյունների միաձուլումից առաջ պետք է ստուգումներ կատարվեն՝ ապահովելու այս գործողության ճիշտությունը։

Հաջորդիվ, մենք կշարունակենք նեղացնել աշխատանքային տարածքը նկարագրված ձևով, մինչև հայտնվենք մեկ այլ ներքին տարածքի մոտ և ներառենք այն աշխատանքային տարածքում: Արդյունքում բոլոր ներքին բազմանկյունները կներառվեն աշխատանքային բազմանկյունի մեջ, որը պետք է նեղացվի մինչև վերջին երեք կետերը։ Արդյունքում, մակերևույթի պարամետրերի որոշման բազմապատկված միացված շրջանը ծածկվելու է եռանկյուններով:

Բրինձ. 9.7.16. Դուք չեք կարող եռանկյուններ կառուցել այս անկյունում

Կարող են լինել իրավիճակներ, երբ տվյալ բազմանկյունների վրա անհնար է կառուցել մեկ եռանկյուն: Նկ. 9.7.16-ը ցույց է տալիս երկու բազմանկյուններով սահմանափակված տարածք, որոնցից յուրաքանչյուրը բաղկացած է չորս հատվածից: Արտաքին բազմանկյունի համար մենք չենք կարող շարունակել եռանկյունությունը, քանի որ ներքին բազմանկյունը ճանապարհին է: Այս դեպքում մենք կգտնենք բազմանկյան երկու հարեւան B և C կետեր, որոնց համար կարող ենք կառուցել HRV եռանկյուն: P կետը նախագծված է BC կողմի կեսին և գտնվում է նրանից այնպիսի հեռավորության վրա, որ նոր եռանկյունը չի հատում բազմանկյունները:

Եռանկյունավորման այլ մեթոդներ.

Եռանկյունավորման այլ եղանակներ կան. Օրինակ, մակերեսի սահմանման տարածքի արտաքին և ներքին ուրվագծերի բազմանկյունները կառուցելուց հետո կարելի է ընտրել եռանկյունների կառուցման այլ ռազմավարություն։ Մեկ այլ տարբերակ է արտաքին և ներքին բազմանկյունները միավորել մեկ բազմանկյունի մեջ՝ նախքան եռանկյունաձևությունը սկսելը: Դուք կարող եք «ուրվագծել» կետերը պարամետրի սահմանման տարածքում՝ օգտագործելով որոշակի ալգորիթմ և կատարել Դելոնեի եռանկյունավորում՝ օգտագործելով դրանք և սահմանային ուրվագծային պոլիգոնների կետերը: Կան ալգորիթմներ, որոնք սկզբում կառուցում են մեծ եռանկյուններ, իսկ հետո դրանք բաժանում կառավարելի չափերի։

Մարմնի եռանկյունավորում.

Մարմնի եռանկյունաձևությունը եռանկյունների ամբողջություն է, որը ստացվում է նրա երեսների մակերեսները եռանկյունավորելով։ Առանձին մակերեսների եռանկյունավորումը տարբերվում է մարմնի երեսների եռանկյունավորումից նրանով, որ վերջին դեպքում հարակից երեսների սահմանային բազմանկյունները պետք է լինեն համահունչ (նկ. 9.7.17):

Բրինձ. 9.7.17. Մարմնի դեմքի սահմանային բազմանկյունի հետևողականություն

Հարևան երեսների բազմանկյունների հատվածները, որոնք անցնում են ընդհանուր եզրերով, համահունչ կլինեն, եթե դրանց կետերը համընկնեն տարածության մեջ:

Եռանկյունավորման կիրառում.

Եռանկյունավորման արդյունքում կառուցված եռանկյունները օգտագործվում են տոնային պատկերներ ստանալու համար։ Նկ. 9.7.18-ը և 9.7.19-ը ցույց են տալիս թերթիկի մարմնի երեսի եռանկյունաձևությունը, որի տոնային պատկերը ներկայացված է Նկ. 6.5.1.

Բրինձ. 9.7.18. Մարմնի դեմքի եռանկյունավորում՝ ուղղման մեթոդով

Մակերեւույթի պարամետրերի որոշման տիրույթը եռանկյունների բաժանելը կարող է օգտագործվել (8.6.2), (8.6.3), (8.6.12), (8.7.17)-(8.7.22) ինտեգրալներում՝ մարմինների երկրաչափական բնութագրերը հաշվարկելիս։ . Թվային ինտեգրման ժամանակ կորերի պարամետրային քայլը պետք է հաշվարկվի բանաձևով (8.11.5), իսկ մակերեսների համար պարամետրական քայլերը պետք է հաշվարկվեն (8.11.1) և (8.11.2) բանաձևերով: