Гэр Амны хөндий Delaunay хоосон бөмбөг арга. Ерөнхий тохиолдолд барилгын ажил

Амны хөндий

Delaunay хоосон бөмбөг арга. Ерөнхий тохиолдолд барилгын ажил

2012 оны 8-р сарын 20-ны 22:41

Тойргийн тойргийн тэгшитгэлээр Delaunay нөхцөлийг шалгах алгоритмын оновчлол ба түүний хэрэглээ

Хоёр гурвалжны хувьд Делауны нөхцөлийг хэрхэн хурдан шалгах тухай нууцыг би танд хэлье.
Үнэн хэрэгтээ оновчлолыг өөрөө арай доогуур тайлбарласан байдаг ("Дэлоны нөхцөлийг тойргийн тэгшитгэлээр шалгах алгоритмыг оновчлох" хэсгийг үзнэ үү), гэхдээ би бүх зүйлийг дарааллаар нь хэлье.

Миний хувьд гурвалжин дүрслэлийг хавтгайг анхдагч секторт (гурвалжин) хуваахын тулд зураг зурахад ашигладаг. Таны мэдэж байгаагаар энэ нь хэд хэдэн үе шатанд хуваагддаг: тохируулах, хил хязгаарыг тодорхойлох, хил хязгаарыг тойрон алхах, контурыг шүүрдэх. Энэ нь маш их байна ерөнхий үзэл. Би больмоор байна гэж бодож байна хэцүү үе шат: онгоц шүүрдэж байна.

Орцонд

Хил хязгаарыг илрүүлж, давсны дараа би гаралт дээр олон тооны гадна гогцоо олж авсан. Хүрэх контур бүр нь байдаг өөр өөр өнгө. Ийм хэлхээ бүр нь тодорхой тооны дотоод хэлхээг агуулдаг.
Тиймээс, "онгоц шүүрдэх" үүднээс, хэрэв бид гаднах контурыг тусад нь авч үзвэл, тус бүр нь баруун, зүүн талдаа нэг хөрштэй байдаг. Тэдгээр. бүх цэгүүд гинжин хэлхээнд хаалттай, нэг ч "өлгөөтэй" цэг байхгүй, гинж бүр дор хаяж 3 цэгийг агуулна (Зураг 1).

Зураг 1

Юу хийх хэрэгтэй

Та дүрсийг гурвалжингаар бүрхэх хэрэгтэй.

Хайх

Номыг уншсаны дараа би Delaunay гурвалжин гурвалжин байгуулах ганц ч (ядаж нэг) аргыг олсонгүй, энэ нь миний хэрэг дээр ямар нэгэн байдлаар тохирсон. Би өөр ном хайгаагүй. Энэ нь хангалттай байсан, миний толгой дахь бодлуудыг эмх цэгцтэй болгосон. Үүний үр дүнд тэрээр өөрийн "унадаг дугуй" зохион бүтээжээ.

Алгоритм

1) Эхлэхийн тулд авч үзэж буй зурагт зөвхөн нэг дараалал байна гэж үзье. Дараа нь гурвалжингуудыг дараалан авахад бүх зүйл ирдэг. Бид ямар ч цэгийг авч, хөрш зэргэлдээ цэгүүдтэй гурвалжин байгуулахыг хичээдэг. Хэрэв гурвалжин барих боломжгүй байсан бол (эдгээр хоёр цэгийг холбосон шугам нь аль хэдийн баригдсан цэгүүдтэй огтлолцдог эсвэл шугам нь хасах бүсэд өнгөрдөг (Зураг 2), бид дараагийн цэг рүү шилжиж, баруун тийшээ хэлнэ. Дараагийн гурвалжин байх үед. олдсон бол бид үүнийг жагсаалтад нэмнэ (Зураг 3), бид түүнийг барьсан цэгийг устгана (Зураг 4).

Зураг 2

Зураг 3

Зураг 4

Өөр нэг зүйл бол: дараагийн гурвалжинг хадгалахдаа оройг цагийн зүүний дагуу (зөв координатын системээр) тэмдэглэх шаардлагатай. Энэ нь ирээдүйд тооцоолох нөөцийг багасгахад хэрэгтэй болно.

2) Бид бүхэл бүтэн онгоцыг шүүрч дуустал 1-р алхамыг давтана.

3) Хэрэв хэд хэдэн дараалал байгаа бол, i.e. нэг, дотор нь нэг буюу хэд хэдэн дотоод контур байдаг (Зураг 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). Үйлдвэрлэлийн дараа тодорхой болсон энэ арга"туузан дамжуулагч" дээр үр дүн нь тодорхойгүй байв. Энэ нь А өнцөг нь өөрөө 180 градусаас дээш байвал сонголт юм. Энэ нь номонд хувь хүний хувийн аргуудын нэг гэж тооцогддог. Ингэснээр түүний бүх дэгжин байдал, ил тод байдал, гүйцэтгэл алга болно. Мөн хожим нь №2 аргыг маш их оновчтой болгож болох нь тогтоогдсон.

Зураг 10

Тойргийн тэгшитгэлээр Delaunay нөхцөлийг шалгах алгоритмыг оновчтой болгох

Дараагийнх нь цэвэр математик.

Тиймээс бидэнд байна:
M(X, Y) цэгийн нөхцөлийг A(x1, y1), B(x2, y2), C(x3, y3) цэгүүдийг дайран өнгөрөх тойргийн тэгшитгэлээр шалгахдаа дараах байдлаар бичиж болно.

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ тэмдэг 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 х. ISBN 5-7511-1501-5

GRID загварууд нь ердийн эсийн загварууд юм.

Координатын системийг нэвтрүүлье
Тэгээд Тэгээд
. Хэрэглэгчийн багц
болон дээж авах үе шатууд
.

- цэгийн физик координат.

Бид тооцоолдог
Тэгээд
,
- битийн сүлжээ.

- тоон утгууд. Бодит:

- алгоритмын параметр - цэгийн тоо, - жин. Цэг ойртох тусам жин ихсэх болно.

- зайны зэрэг (1 эсвэл 2).

Нормчиллын коэффициент:

Хэрхэн 1-д ойртох тусам өндөр жинтэй оноог харгалзан үзнэ.

Энэ бол IDW арга юм - урт, t бүрийн хувьд хөршүүдээ олох шаардлагатай. Хөршүүдийн багцыг үр дүнтэй олох боломжтой - хамгийн ойр. Цэг бүр нь тодорхой өндөртэй "хоос" үүсгэдэг. Цэг тогтоох жигд бус байдлаас их зүйл шалтгаална, үүний тулд тэд авдаг
эсвэл
тэдгээр. салбаруудад хуваагдан ойр орчмын цэгүүдийг байгуулна.

Давуу тал- энгийн байдал

Алдаа:

------Тасалбар 14. Цагаан тугалганы загвар. Delaunay гурвалжингийн алгоритмууд------

1) Гурвалжин (цагаан тугалга).

Гурвалжинчлал– хэсэгчилсэн шугаман функцүүдийн багц хэлбэрээр функцийг бүтээх

Гурвалжинчлал– гүдгэр муж доторх интерполяци.

Гурвалжинчлал- бүх дотоод ирмэгүүд нь гурвалжин хэлбэртэй хавтгай график; орон зайг давхцалгүйгээр өөр хоорондоо зэргэлдээх гурвалжин хэлбэрээр дүрслэх арга. Гурвалжинг хэд хэдэн аргаар олон цэг дээр байгуулдаг.

Хамгийн оновчтой гурвалжинг бүтээхийн тулд алгоритм хэрэгтэй.

3 цэгийг дайран өнгөрч буй онгоц.

1) Ийм гурвалжинг ол
;

2)
- хавтгайн тэгшитгэл байгуулах.

Цэгүүд гурвалжин дотор байгаа эсэхийг шалгахын тулд та утгыг шугамын тэгшитгэлд - гурвалжны ирмэг дээр орлуулах хэрэгтэй. Хэрэв бүх 3 тэгшитгэл > 0 бол дотор нь.

Илтгэлийн бүтэц:

Гурвалжин бүр ижил тооны гурвалжинг агуулдаг.

, Хаана - дотоод цэгүүдийн тоо,
- онооны хэмжээ.

Шуналтай гурвалжин.

Бид бүх цэгүүдийг ирмэгээр холбож, хамгийн багадаа сонгож, гурвалжинд нэмнэ. Дараа нь бид өмнөхтэй огтлолцохгүй дараагийн доод хэмжээг авдаг. Үр дүн нь шунахайн гурвалжин юм.

Делоны гурвалжинчлал.

Аливаа гурвалжны эргэн тойронд хүрээлэгдсэн тойргийн дотор талд бусад гурвалжны цэгүүд хамаарахгүй. Энэ нь цорын ганц аргаар баригдсан.

Flip нь ирмэгийг шилжүүлэх явдал юм. Энэ нь ердийн гурвалжингаас Делонай гурвалжин руу шилжих боломжийг танд олгоно. Цэг тойрогт хамаарах эсэхийг шалгахын тулд: if гэж орлуулна< R, то внутри.

Делауны нөхцөл байдал.

Гурван цэгээр дамжин өнгөрөх тойргийн тэгшитгэл:

Хэрэв тэгээс бага бол гадаад, үгүй бол дотоод.

- Делауны нөхцөл байдал.

Делонай гурвалжин үүсгэх алгоритм:

1) Мөрдөн байцаалтын шатанд байгаа цэгүүдийг нэмэх- энгийн давталтын алгоритм:

иж бүрдэл байна
гурвалжин дээр нэмэхэд барилгын ажил хийгдэж байна
гурвалжин хуваах
сэргээн босгох. Тэг шатанд бид 3-4 зохиомол цэгийг нэмж оруулдаг бөгөөд энэ нь бидний дугтуй, доторх бүх цэгүүдийг хамардаг. Дараа нь бид цэгийг шидэж, аль гурвалжинд хүрч байгааг хараад, 3-т хувааж, гурвалжин бүрийн хувьд бид Делауны нөхцөлийг шалгаж, ирмэгийг эргүүлэх ажлыг гүйцэтгэдэг. Эгнээ солих дундаж тоо гурван байна.

Онолын нарийн төвөгтэй байдал

2) Хурдасгах аргууд.Статистикийн хамааралтай цэгүүд дээр үндэслэсэн. Үрийн гурвалжин нь өмнөх цэг унасан гурвалжин юм. Дараа нь бид хоёр цэгийг холбодог - өмнөх ба шинэ.

Бид эхний цэгээс нөгөө рүү шилждэг.

2012 оны 8-р сарын 20-ны 22:41

Тойргийн тойргийн тэгшитгэлээр Delaunay нөхцөлийг шалгах алгоритмын оновчлол ба түүний хэрэглээ

Зураг боловсруулах,
Програмчлал

Миний хувьд гурвалжин дүрслэлийг хавтгайг анхдагч секторт (гурвалжин) хуваахын тулд зураг зурахад ашигладаг. Таны мэдэж байгаагаар энэ нь хэд хэдэн үе шатанд хуваагддаг: тохируулах, хил хязгаарыг тодорхойлох, хил хязгаарыг тойрон алхах, контурыг шүүрдэх. Энэ бол хамгийн ерөнхий ойлголт юм. Би хамгийн хэцүү үе шатанд болмоор байна: онгоц шүүрдэх.

Орцонд

Хил хязгаарыг илрүүлж, давсны дараа би гаралт дээр олон тооны гадна гогцоо олж авсан. Хүрэх тойм бүр өөр өөр өнгөтэй байдаг. Ийм хэлхээ бүр нь тодорхой тооны дотоод хэлхээг агуулдаг.
Тиймээс, "онгоц шүүрдэх" үүднээс, хэрэв бид гаднах контурыг тусад нь авч үзвэл, тус бүр нь баруун, зүүн талдаа нэг хөрштэй байдаг. Тэдгээр. бүх цэгүүд гинжин хэлхээнд хаалттай, нэг ч "өлгөөтэй" цэг байхгүй, гинж бүр дор хаяж 3 цэгийг агуулна (Зураг 1).

Зураг 1

Юу хийх хэрэгтэй

Та дүрсийг гурвалжингаар бүрхэх хэрэгтэй.

Хайх

Алгоритм

Зураг 2

Зураг 3

Зураг 4

2) Бид бүхэл бүтэн онгоцыг шүүрч дуустал 1-р алхамыг давтана.

Тав дахь шатны талаар дэлгэрэнгүй

Одоо миний мэдэж байгаагаар гурвалжин Делоны нөхцөлийг хангаж байгаа эсэхийг тодорхойлох хоёр боломжит арга бий: 1) Эсрэг өнцгүүдийн нийлбэрийг шалга. Энэ нь 180-аас бага байх ёстой. 2) Хязгаарлагдсан тойргийн төвийг тооцоолж, 4-р цэг хүртэлх зайг тооцоол. Хэрэв цэг нь хязгаарлагдмал тойргоос гадуур байвал Делоны нөхцөл хангагддаг гэдгийг хүн бүр мэддэг.

Жишээлбэл, номонд тооцоолсон тооцоолох хүчин чадлын үүднээс 1-р сонголт илүү ашигтай байдаг. Би үүнийг хэрэгжүүлэх байсан, үгүй бол ... (Зураг 10). Энэ аргыг "конвейер" дээр тавьсны дараа тодорхойгүй байдал үүссэн. Энэ нь А өнцөг нь өөрөө 180 градусаас дээш байвал сонголт юм. Энэ нь номонд хувь хүний хувийн аргуудын нэг гэж тооцогддог. Ингэснээр түүний бүх дэгжин байдал, ил тод байдал, гүйцэтгэл алга болно. Мөн хожим нь №2 аргыг маш их оновчтой болгож болох нь тогтоогдсон.

Зураг 10

Тойргийн тэгшитгэлээр Delaunay нөхцөлийг шалгах алгоритмыг оновчтой болгох

Дараагийнх нь цэвэр математик.

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ тэмдэг 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 гурвалжин нь бүх баригдсан гурвалжны бүх өнцгүүдийн хамгийн бага өнцгийг дээд зэргээр нэмэгдүүлж, улмаар "нимгэн" гурвалжингаас зайлсхийдэг.

· Delaunay гурвалжин нь бичээстэй бөмбөрцгийн радиусын нийлбэрийг хамгийн их болгодог.

· Delaunay гурвалжин нь дискрет Дирихле функцийг багасгадаг.

· Delaunay гурвалжин нь хамгийн бага орчны бөмбөрцгийн хамгийн их радиусыг багасгадаг.

· Хавтгай дээрх Делонай гурвалжин нь бүх боломжит гурвалжны дунд гурвалжны эргэн тойронд дүрслэгдсэн тойргийн радиусуудын хамгийн бага нийлбэртэй байна.

Зураг 1. Гурвалжингийн хэлбэр.

Гүдгэр гурвалжинг гэдэг нь бүх гурвалжныг хүрээлэх хамгийн бага олон өнцөгт нь гүдгэр байх гурвалжин юм. Гүдгэр биш гурвалжинг гүдгэр бус гэж нэрлэдэг.

Өгөгдсөн хоёр хэмжээст цэгээс гурвалжин байгуулах асуудал нь өгөгдсөн цэгүүдийг огтлолцохгүй хэрчмүүдээр холбож гурвалжин үүсгэх асуудал юм.

Өгөгдсөн гурвалжны цэгүүдийн аль нь ч баригдсан гурвалжны эргэн тойронд хүрээлэгдсэн тойрог дотор орохгүй бол гурвалжинг Делоны нөхцөлийг хангана гэж хэлнэ.

Гурвалжингийн гурвалжин нь гүдгэр бөгөөд Делоны нөхцөлийг хангаж байвал түүнийг Делонай гурвалжин гэнэ.

Зураг 2. Delaunay гурвалжин.

Delaunay хоосон бөмбөг арга. Ерөнхий тохиолдолд барилгын ажил

Системийн (A) цэгүүдэд хүрч болохуйц хэмжээгээрээ өөрчилсөн хоосон бөмбөгийг ашиглая, гэхдээ үргэлж хоосон хэвээр үлдэнэ.

Тиймээс (А) цэгийн системд хоосон Делонай бөмбөгийг байрлуулцгаая. Хэрэв та хангалттай жижиг бөмбөг сонговол энэ нь үргэлж боломжтой байдаг. Бөмбөгний төвийг хэвээр үлдээж, түүний радиусыг нэмэгдүүлж эхэлцгээе. Хэзээ нэгэн цагт бөмбөгний гадаргуу нь системийн (A) i цэгтэй тулгарах болно. Энэ нь гарцаагүй тохиолдох болно, учир нь манай системд хязгааргүй том хоосон зай байдаггүй. Бид хоосон бөмбөгний радиусыг үргэлжлүүлэн нэмэгдүүлэх бөгөөд ингэснээр i цэг түүний гадаргуу дээр үлдэх болно. Үүнийг хийхийн тулд та бөмбөгний төвийг i цэгээс хөдөлгөх хэрэгтэй болно. Бөмбөлөг эрт орой хэзээ нэгэн цагт гадаргуутайгаа системийн өөр нэг цэгт хүрэх болно (A).

Зураг 3

Delaunay симплекс нь хоосон зай, давхцалгүйгээр орон зайг дүүргэдэг.

Аливаа симплексийн тайлбарласан бөмбөрцөг нь системийн бусад цэгүүдийг агуулдаггүй.

Үүнийг j цэг гэж үзье. Бөмбөгийнхөө радиусыг үргэлжлүүлэн нэмэгдүүлж, хоёр цэгийг гадаргуу дээр нь үлдээцгээе. Бөмбөлөг нэмэгдэх тусам системийн гурав дахь цэг болох k цэгт хүрнэ. Хоёр хэмжээст тохиолдолд бидний "хоосон тойрог" энэ мөчид тогтмол байх болно, өөрөөр хэлбэл. Тойргийг хоосон байлгахын зэрэгцээ түүний радиусыг цаашид нэмэгдүүлэх боломжгүй болно. Үүний зэрэгцээ бид тодорхой гурвалжинг тодорхойлсон гурван цэгийн (i, j, k) энгийн хоёр хэмжээст тохиргоог тодорхойлдог бөгөөд түүний онцлог нь түүний тойрог дотор системийн (A) өөр цэгүүд байдаггүй явдал юм. Гурван хэмжээст орон зайд бөмбөг гурван цэгээр тодорхойлогддоггүй. Түүний гадаргуу дээрх бүх гурван цэгийг хадгалан түүний радиусыг үргэлжлүүлэн нэмэгдүүлцгээе. Бөмбөгний гадаргуу нь системийн дөрөв дэх l цэгтэй таарах хүртэл энэ нь боломжтой болно. Үүний дараа хоосон бөмбөгний хөдөлгөөн, өсөлт боломжгүй болно. Олдсон дөрвөн цэг (i,j,k,l) нь тетраэдрийн оройг тодорхойлдог бөгөөд энэ нь түүний хүрээлэгдсэн бөмбөрцөг дотор системийн (A) өөр цэгүүд байдаггүй гэдгээрээ онцлог юм. Ийм тетраэдрийг Делонай симплекс гэж нэрлэдэг.

Математикийн хувьд симплекс нь өгөгдсөн хэмжээсийн орон зайд хамгийн энгийн дүрс юм: тетраэдр - гурван хэмжээст орон зайд; гурвалжин - хоёр хэмжээст. Нэг хавтгайд оршдоггүй системийн дурын гурав (дөрөв) цэг нь тодорхой симплексийг тодорхойлдог. Гэсэн хэдий ч, хэрэв тайлбарласан бөмбөрцөг нь хоосон байвал энэ нь Delaunay симплекс байх болно. Өөрөөр хэлбэл, Delaunay энгийн байдлыг (A) систем дэх цэгүүдийн гурвалсан (дөрөв дахин) тусгай сонголтоор тодорхойлно.

Бид нэг Delaunay симплекс бүтээсэн боловч хоосон бөмбөгийг өөр газар байрлуулж, ижил процедурыг давтснаар бид бусдыг тодорхойлж чадна. (А) системийн бүх Делонай энгийн багц нь орон зайг давхцал, цоорхойгүйгээр дүүргэдэг гэж заасан байдаг. орон зайг хуваахыг хэрэгжүүлдэг боловч энэ удаад тетраэдрүүдэд хуваагдана. Энэ хуваалтыг гэж нэрлэдэг Delaunay хавтанцар(Зураг 3).

Delaunay гурвалжингийн хэрэглээ

Евклидийн орон зайд Delaunay гурвалжинг ихэвчлэн ашигладаг. Евклидийн хамгийн бага хүрээний мод нь Делонай гурвалжин дээр байх нь баталгаатай тул зарим алгоритмууд гурвалжинг ашигладаг. Мөн Делонай гурвалжингаар Евклидийн аялагч худалдагчийн асуудал ойролцоогоор шийдэгдэнэ.

2 хэмжээст интерполяцийн хувьд Delaunay гурвалжин нь хэт хурц, хэт мохоо өнцгөөс зайлсхийж, хавтгайг хамгийн зузаан гурвалжин болгон хуваадаг. Эдгээр гурвалжнуудын тусламжтайгаар та жишээлбэл, хоёр шугаман интерполяцийг үүсгэж болно.

Геоинформатикт байнга тулгардаг өөр нэг асуудал бол налууг барих явдал юм. Энд налуугийн давамгайлах чиглэлийг үндсэн чиглэлд тодорхойлж, гадаргууг тодорхой чиглэл давамгайлж буй бүсүүдэд хуваах шаардлагатай. Гадаргуугийн хэвтээ хэсгүүдийн хувьд өртөлтийг тодорхойлох нь утгагүй тул хэвтээ эсвэл бага зэрэг налуу газрыг тусдаа бүсэд хуваарилдаг.<5 о. По странам света деление обычно выполняется на 4, 8 или 16 частей.

Зураг 4.

Налуугийн өртөлтийг тооцоолох асуудлыг ихэвчлэн дэлхийн гэрэлтүүлгийг шинжлэхэд ашигладаг. Үүнтэй холбогдуулан нарны одоогийн байрлалыг нэмэлтээр авч үзэх шаардлагатай байдаг, өөрөөр хэлбэл. өртөлтийг гурвалжингийн норм ба нарны чиглэлийн хоорондох чиглэл гэж тооцдог.

Тиймээс гурвалжин гурвалжин бүрийг тодорхой бүс нутагт хамаарах зарчмын дагуу ангилж болно. Үүний дараа та зөвхөн бүс сонгох алгоритмыг дуудах хэрэгтэй.

Гурвалжин гэдэг нь загварчлагдсан объектын гадаргууг тодорхой заасан хэмжээнээс хэтрүүлэхгүй зайд байрлуулсан гурвалжин хавтангуудаар ойртуулахыг хэлнэ 6. Бүх гурвалжин хавтангуудыг хооронд нь холбох ёстой. Тэдний орой нь гадаргуу дээр байрладаг. Гурвалжин хавтангийн багц нь ерөнхий гадаргуугаас илүү хялбар байдаг. Бид гурвалжин хавтанг гурвалжин гэж нэрлэх болно. Гурвалжны хувьд өгөгдсөн цэг хүртэлх зай эсвэл огторгуйн өгөгдсөн шугамтай огтлолцох цэгийг хурдан тооцдог. Нүүрний гурвалжинг нь геометрийн загварыг нүдээр мэдрэхийн тулд хийдэг тул гурвалжны талуудыг нүд нь муруйлтыг анзаарахгүй байхаар сонгосон.

Гадаргуугийн параметрийн хавтгай дээр геометрийн объектуудыг гурвалжингаар дүрслэхдээ орон зайн цэгүүдийн массив ба эдгээр цэгүүд дэх биеийн нүүрний массивын массивыг тооцоолох замаар биеийн нүүрний орон зайн гурвалжинг хийх ёстой. Хоёр хэмжээст цэгүүд.Биеийг хурдан харуулахын тулд тэдгээрийн нүүрийг гурвалжин хавтангаар ойролцоолсон байдаг. Биеийн нүүртэй харьцаж буй гэрлийн цацрагийн үйл ажиллагааг тодорхойлохын тулд хэвийн цэгүүд шаардлагатай. Өмнөх бүлгүүд болон энэ бүлгийн өнгө аястай зургуудыг гурвалжингаар хийсэн болно.

Гадаргуугийн гурвалжингийн үр дүнд бид параметрийн хавтгай дээрх хоёр хэмжээст цэгүүдийн массив ба эхний дурдсан массив дахь цэгүүдийн тоо болох бүхэл тоонуудын гурвалсан массивтай болохыг хүсч байна. Тиймээс гурвалжин бүрийг параметрийн массив дахь оройнхоо гурван тоогоор илэрхийлнэ. Параметрийн домайн хоёр хэмжээст цэг бүрийн хувьд гадаргуу дээрх орон зайн цэг ба түүний доторх хэвийн гадаргууг тооцоолж болно. Орон зайн цэгүүд болон нормуудыг 2D цэгийн массивтай төстэй массивуудад хадгалж болно.

Гурвалжингийн зарим аргыг авч үзье. Хавтгай гадаргуугийн хувьд гадаргуугийн хилийн цэгүүд дээр гурвалжин байгуулдаг, параметрийн бүс дотор цэг хайх шаардлагагүй, хэмнэлттэй гурвалжингийн аргууд байдаг.

Делоны гурвалжинчлал.

Онгоцны зарим хэсгийг авч үзье. Хэрэв та түүний хилийн дагуу шилжихдээ зөвхөн нэг чиглэлд (зөвхөн зүүн тийш эсвэл зөвхөн баруун тийш) эргэх шаардлагатай бол бид талбайг гүдгэр гэж нэрлэнэ. Гүдгэр хавтгай мужуудыг гурвалжин болгоход Делонай алгоритмыг ашиглаж болно. Бид чөлөөт хэлбэрийн гадаргууг гурвалжин болгохын тулд энэ алгоритмыг шууд ашиглах боломжгүй, гэхдээ бид гурвалжин бүтээх аргыг ашиглана.

Цагаан будаа. 9.7.1. Дотор нь өгөгдсөн цэг бүхий гүдгэр бүс

Битүү тасархай шугамаар хүрээлэгдсэн зарим гүдгэр хоёр хэмжээст муж ба энэ муж доторх цэгүүдийн багцыг өгье (Зураг 9.7.1).

Заасан талбайг гурвалжинд хуваах шаардлагатай бөгөөд тэдгээрийн орой нь тухайн талбайн доторх өгөгдсөн цэгүүд ба түүнийг хязгаарлаж буй тасархай шугамын оройнууд юм. Гурвалжингууд нь хоорондоо давхцаж болохгүй бөгөөд тэдгээрийн талууд нь зөвхөн оройн хэсгүүдэд огтлолцох боломжтой.

Тодорхой талбайг дүүргэхийн тулд хэд хэдэн гурвалжны багцыг барьж болно. Бүх тохиолдолд гурвалжны тоо нь -тэй тэнцүү байх ба энд K нь хязгаарлах олон шугамын оройн тоо, I нь тухайн муж доторх өгөгдсөн цэгүүдийн тоо юм.

Цагаан будаа. 9.7.2. Delaunay алгоритмын гурав дахь цэгийг сонгох

Гурвалжин бүрийн эргэн тойронд дүрслэгдсэн тойрог дотор бусад гурвалжны орой байхгүй бол бүс нутгийн гурвалжин нь Делонай гурвалжин болно. Delaunay гурвалжин нь тэгш өнцөгттэй аль болох ойрхон гурвалжинг барьдаг (үндэслэлгүй уртасгасан гурвалжин барихыг зөвшөөрдөггүй).

Үүнийг тэнцвэртэй гэж нэрлэж болно. Нэг тойрог дээр дөрвөн орой байхгүй бол Делонай гурвалжин нь өвөрмөц байх болно.

Делонай гурвалжинг авч үзье. Бүс нутгийг хязгаарлаж буй олон шугамын оройнууд ба муж доторх өгөгдсөн цэгүүдийг гурвалжингийн орой гэж нэрлэнэ. Бид гурвалжны талуудыг ирмэг гэж нэрлэнэ. Ирмэгүүдийн дунд бид хилийн ирмэг гэж нэрлэгдэх хилийн шугамын сегментүүдийг сонгодог. Гүдгэр бүс нь ирмэг бүрийн зүүн талд байхаар бүх хилийн ирмэгийг чиглүүлье. Зурагт үзүүлсэн тал нь AB хилийн ирмэг болох гурвалжин байгуулах шаардлагатай болно. 9.7.2.

A, B оройнууд болон тэдгээртэй нэг шулуун дээр ороогүй аливаа оройгоор дамжуулан тойрог зурж болно. Гурвалжны гурав дахь орой болохын хувьд бид V оройг сонгох ба харгалзах тойрог нь V цэг дээр байрлах AB сегменттэй харьцуулахад нэг талдаа байгаа бусад оройг агуулдаггүй.Хилийн ирмэгийн хувьд ерөнхий тохиолдолд ийм нэг орой байж болно. олдох. Бид үүнийг хамгийн ойрын нэг гэж нэрлэх болно. 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 параметр нь хамгийн бага утгатай байна.

Бүх хилийн ирмэгийг гурвалжин болгох талбай нь тус бүрийн зүүн талд байхаар чиглүүлье. Бид ямар ч хилийн ирмэгээс гурвалжин байгуулж эхэлдэг. Харгалзах тойрог нь бусад оройг агуулаагүй хамгийн ойрын оройг олъё. AB хилийн ирмэгийн хувьд хамгийн ойрын V оройг олъё.Дараа нь ABV гурвалжин байгуулж, AB ирмэгийг идэвхгүй гэсэн ангилалд шилжүүлнэ. Бид гурвалжингийн алгоритмд оролцдоггүй идэвхгүй ирмэг ба оройг дуудах болно. Хэрэв хилийн ирмэгүүдийн дунд BV ирмэг байхгүй бол бид VB сегмент дээр шинэ хилийн ирмэгийг байгуулна. Хэрэв хилийн ирмэгүүдийн дунд BV ирмэг байгаа бол бид үүнийг болон В оройг идэвхгүй ангилалд шилжүүлнэ. Хэрэв хилийн ирмэгүүдийн дунд VA ирмэг байхгүй бол бид AV сегмент дээр шинэ хилийн ирмэгийг байгуулна. Хэрэв хилийн ирмэгүүдийн дунд VA ирмэг байгаа бол бид үүнийг болон А оройг идэвхгүй ангилалд шилжүүлнэ. Гурвалжингийн процессыг Зураг дээр үзүүлэв. 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 ирмэг байгаа бол түүнийг болон В оройг идэвхгүй ангилалд шилжүүлнэ. Хэрэв хилийн ирмэгүүдийн дунд VA ирмэг байхгүй бол бид AV сегмент дээр шинэ хилийн ирмэгийг байгуулах боловч хилийн ирмэгүүдийн дунд VA ирмэг байгаа бол бид түүнийг болон А оройг идэвхгүй ангилалд шилжүүлнэ.

Хэрэв сегмент эсвэл VA нь бусад хилийн ирмэгүүдтэй огтлолцдог бол бид өөр хилийн ирмэгийн хамгийн ойрын оройг хайх руу шилжинэ. Бүх ирмэг ба оройг идэвхгүй гэж ангилсны дараа гурвалжинг дуусгана.

Цагаан будаа. 9.7.7. Залруулгын аргаар гурвалжин

Зураг дээр. 9.7.7-д хилийн шугамаар огтлолцсон нүднүүдийн гурвалжинг засах аргаар гадаргуугийн гурвалжинг үзүүлэв. Зураг дээр. 9.7.8, үүссэн гурвалжингийн тусламжтайгаар гадаргууг өөрөө харуулна.

Хэрэв хилийн олон өнцөгт ба гадаргуу нь зарим тэгш хэмтэй бол залруулгын аргаар гурвалжин хийх нь ижил төстэй тэгш хэмтэй байх болно.

Шингээлтийн аргаар гурвалжин .

Гурвалжингийн өөр аргыг авч үзье. Хурдны хувьд энэ нь Delaunay гурвалжин болон түүний өөрчлөлтүүдээс доогуур юм. Гурвалжингийн процедурыг эхлүүлэхийн тулд гадаргуугийн хил хязгаарыг хаалттай олон өнцөгт хэлбэрээр дүрслэх шаардлагатай. Гурвалжингийн процессын явцад бид гадаргуугийн параметрүүд дээр үндэслэн алхмуудыг тодорхойлох шаардлагатай болно. Хөдөлгөөний тодорхой чиглэлтэй бол эдгээр алхмуудыг (9.4.6) томъёогоор тодорхойлно. Гадаргуугийн параметрийн ойролцоо алхмуудыг дараах байдлаар олж болно. Тодорхой цэгийн эргэн тойронд параметрийн хавтгай дээрх мужийг энэ муж дахь цэгээс цэг хүртэлх орон зайн сегмент нь гадаргуугаас өгөгдсөн S утгаас цаашгүй байхаар тодорхойлъё.

Үүнийг хийхийн тулд бид координатын шугамын дагуу параметрийн зөвшөөрөгдөх өсөлтийг тооцоолно

цэг дээрх гадаргуугийн нэг ба хоёрдугаар квадрат хэлбэрийн коэффициентүүд хаана байна. Хүссэн бүсийн хилийн хувьд бид нэг цэг дээр төвтэй, хагас тэнхлэгтэй эллипсийг авдаг. Энэ эллипс нь тэгшитгэлтэй

Хэрэв та хавтгай дээрх цэгийг тэнхлэгтэй өнцгөөр өгөгдсөн чиглэлийн цэгийн хажууд олохыг хүсвэл түүний параметрүүд дараах байдалтай байна.

Нэгдүгээрт, гадаргуугийн параметрийн талбайг нэг гадаад контураар хязгаарлах энгийн тохиолдлыг авч үзье. Бид гадаргуугийн хил хязгаарыг параметрийн домэйн дээр битүү олон өнцөгтөөр ойртуулна. Гурвалжин үүсгэх үед бид ажлын олон өнцөгтийг ашиглах бөгөөд энэ тохиолдолд бид гадаад контурын олон өнцөгтийг авна. Бид үүссэн хоёр хэмжээст цэгүүдийн массив дээр олон өнцөгт цэгүүдийг нэмнэ. Бид ажлын талбайн ирмэгээс гурвалжин байгуулж, ажлын талбайд зөвхөн гурван цэг үлдэх хүртэл нарийсгана.

Ажлын олон өнцөгт нь муж болж хувирах оройг олъё. Ийм цэг үргэлж байдаг бөгөөд түүний эргэлтийн өнцөг бага байдаг. Энэ цэгийг О, параметрүүдийг нь энэ цэгийн ойролцоо эргэлтийн өнцгөөс хамааран нэг эсвэл хоёр гурвалжин байгуулна. Хэрэв өнцөг нь бага бол бид эдгээр гурван цэг дээр нэг гурвалжин байгуулна (Зураг 9.7.9). Үгүй бол бид үүн дээр хоёр хөрш, нэг шинэ цэг бүхий хоёр гурвалжин байгуулна (Зураг 9.7.11). Шинэ цэгийг P гэж тодорхойлсон. Бид B OS P параллелограммын диагональ дээр P цэгийг хайж олох болно. Хэрэв параллелограммын орой нь эллипсийн дотор орвол (Зураг 9.7.10), бид үүнийг P цэг гэж авна. Үгүй бол бид эллипсийн огтлолцол ба параллелограммын диагональыг P цэг гэж авна. Сүүлчийн тохиолдолд эллипс ба сегментийн огтлолцлыг хайх шаардлагагүй болно.

P цэгийн координатыг МЭӨ О цэгүүдийн координатаар тодорхойлно

OP сегментийн хэвтээтэй өнцөг нь тэгшитгэлээр тодорхойлогддог

(9.7.8)

Эдгээр өгөгдөл нь эллипс (9.7.5) -тай харьцуулахад P цэгийн байрлалыг тодорхойлох боломжийг олгодог.

Зурагт үзүүлсэн тохиолдолд. 9.7.9-д гурвалжин байгуулж (түүний оройнуудын тоог санаарай) ажлын талбар дахь О цэгийг устгацгаая. Зурагт үзүүлсэн тохиолдолд. 9.7.11-д бид хоёр гурвалжин байгуулж, ажлын талбарт О цэгийг P цэгээр сольж, үүссэн цэгүүдийн массив дотор байрлуулна. Зураг дээр. Зураг 9.7.12-т хоёр гурвалжин байгуулж, О цэгийг арилгасны дараа олж авсан олон өнцөгтийг үзүүлэв. Аль ч тохиолдолд ажлын олон өнцөгтөөс О цэг хасагдах ба ажлын олон өнцөгт нарийсах болно. Ажлын талбайг нарийсгасны дараа огтлолцохгүй байх үед л гурвалжин байгуулж болно гэдгийг анхаарна уу.

Цагаан будаа. 9.7.9. Гурвалжин барих

Цагаан будаа. 9.7.10. Үр дүн нь полигон

Цагаан будаа. 9.7.11. Хоёр гурвалжин барих

Цагаан будаа. 9.7.12. Үр дүн нь полигон

Ийм нөхцөл байдлыг Зураг дээр үзүүлэв. 9.7.13. Баригдсан гурвалжингийн талууд нь тэдгээрийн зэргэлдээ биш ажлын талбайн талуудтай огтлолцох үед тэдгээр нь тохиолдож болно. Зурагт үзүүлсэн шиг шинэ гурвалжин бүтээхээс өмнө. 9.7.9, мөн зурагт үзүүлсэн тохиолдолд. 9.7.11. Үүссэн олон өнцөгт өөрөө огтлолцоогүй эсэхийг шалгах шаардлагатай.

Түүнчлэн, P цэгийн байрлалыг тодорхойлохдоо энэ нь ажлын талбайн бусад цэгүүдээс хангалттай зайд байх бөгөөд тухайн хэсгийн цэгүүдийг холбосон сегментүүдэд ойртохгүй байх нь чухал юм. Үгүй бол ирээдүйд гурвалжин барихад хүндрэл гарч болзошгүй. Тиймээс ажлын олон өнцөгтийг нарийсгахаасаа өмнө үүссэн олон өнцөгтийг өөрөө огтлолцсон эсэхийг шалгах хэрэгтэй. Хэрэв О цэгийн ойролцоо гурвалжин (гурвалжин) байгуулах боломжгүй бол түүний оронд олон өнцөгт нь контур дотор бусдаас илүү ороож байх өөр цэгийг олж, үүн дээр тайлбарласан үйлдлүүдийг хийх хэрэгтэй.

Дараа нь өөрчлөгдсөн ажлын талбайн тусламжтайгаар бид саяхан тайлбарласан үйлдлүүдийг хийх болно. Ажлын олон өнцөгтийн талбайн дотор бусад цэгүүдээс илүү эргэдэг цэгийг олж, нэг эсвэл хоёр гурвалжин байгуулж олон өнцөгтийг нарийсгах боломжийг шалгаж, олон өнцөгтийг нарийсгая.

Цагаан будаа. 9.7.13. Та энэ буланд гурвалжин барьж болохгүй.

Энэ үйл явцыг үргэлжлүүлснээр бид хоёр хэмжээст цэгийн массив болон гурвалжингийн массивыг өргөжүүлэхийн зэрэгцээ ажлын олон өнцөгтийг нарийсгаж, түүний хамрах талбай болон цэгүүдийн тоог багасгах болно. Эдгээр үйлдлүүдийн зарим үе шатанд бид гурван цэгээс бүрдэх ажлын олон өнцөгтийг хүлээн авах болно. Эдгээр цэгүүдэд сүүлчийн гурвалжинг барьж, ажлын талбайг арилгаж, гурвалжинг дуусгацгаая. Тайлбарласан гурвалжингийн аргын хувьд ажлын талбайгаар хязгаарлагдсан талбайг гурвалжинг таслах замаар арилгадаг.

Гадаргуугийн параметрийн талбайг бүхэлд нь гаднах контурын дотор байрлах нэг гадаад контур ба хэд хэдэн дотоод контураар хязгаарлах ерөнхий тохиолдлыг авч үзье. Бид гадаргуугийн хил хязгаарыг параметрийн домэйн дээрх хаалттай полигонуудаар ойртуулдаг. Контур бүрийн хувьд бид өөрсдийн олон өнцөгтийг барих болно. Контурын хувьд, тэдгээрт баригдсан олон өнцөгтүүдийн хувьд тэдгээрийн харилцан чиг баримжаа олгох дүрмийг дагаж мөрдөх ёстой. Дотоод олон өнцөгтийн чиглэл нь гадна талын олон өнцөгтийн чиглэлийн эсрэг байх ёстой. Гаднах контурын олон өнцөгт гурвалжинг хийж эхэлцгээе. Үүний цэгүүдийг хоёр хэмжээст цэгүүдийн массив болгон оруулаад, олон өнцөгтийг өөрөө ажиллаж байгаа нэг болгоцгооё.

Бид гурвалжингуудыг зүгээр л холбосон мужтай адил аргаар байгуулна. Ажлын талбайн О цэгийг олж, тэнд ажлын талбайг нарийсгах боломжийг шалгаж, талбайг нарийсгая. Хэрэв дотоод контур байгаа бол сонгосон цэг дээр ажлын талбайг нарийсгах боломжийг шалгах нь илүү хэцүү болно. Гурвалжны талуудыг ажлын талбайн талуудтай огтлолцох талаар тайлбарласан шалгалтаас гадна гурвалжны талуудыг бүх дотоод олон өнцөгтүүдийн талуудтай огтлолцсон эсэхийг шалгах шаардлагатай.

О цэг дээр хоёр гурвалжин байгуулах боломжийг шалгаж үзье (Зураг 9.7.11), шинэ P цэг нь баригдсаны дараа дотоод олон өнцөгтүүдийн аль нэгний дотор унах эсвэл түүний сегментүүдэд хүлээн зөвшөөрөгдөхгүй ойрхон байх болно. Энэ тохиолдолд бид P цэгийг байгуулахгүй, харин оронд нь энэ дотоод олон өнцөгтийг ажлын олон өнцөгт оруулах болно. 9.7.14.

Дотоод олон өнцөгтүүдийн аль нэгнийх нь цэгүүдийг ажлын олон өнцөгт оруулахын тулд дотоод олон өнцөгтийн цэгүүдийн дунд ажлын олон өнцөгтийн С цэгтэй (О цэгтэй зэргэлдээ) хамгийн ойр байгаа цэгийг олно.

OCF ба CEF цэгүүд дээр гурвалжин байгуулж, ажлын талбайн О ба С цэгүүдийн хооронд дотоод олон өнцөгтийн цэгүүдийг F цэгээс эхлэн Е цэгээр төгсгөж оруулъя. Тиймээс бид OS сегмент дээрх ажлын хэсгийг эвдэж, EF сегмент дээрх дотоод олон өнцөгтийг OF ба ЕХ сегментүүдтэй нэгтгэнэ.

Цагаан будаа. 9.7.14. Хоёр гурвалжин барих

Цагаан будаа. 9.7.15. Гадаад болон дотоод олон өнцөгтүүдийг нэгтгэх

Нэгдлийн үр дүнг Зураг дээр үзүүлэв. 9.7.15. Мэдээжийн хэрэг, гаднах болон дотоод олон өнцөгтийг нэгтгэхийн өмнө энэ үйлдлийн зөв эсэхийг шалгах шаардлагатай.

Дараа нь бид өөр дотоод бүстэй ойрхон байгааг олж мэдээд ажлын талбарт оруулах хүртлээ ажлын талбайг тодорхойлсон арга замаар нарийсгах болно. Үүний үр дүнд бүх дотоод олон өнцөгтүүд нь ажлын олон өнцөгт багтах бөгөөд үүнийг сүүлийн гурван цэг хүртэл нарийсгах ёстой. Үүний үр дүнд гадаргуугийн параметрүүдийг тодорхойлох үржвэрийн холболтын бүсийг бүхэлд нь гурвалжингаар бүрхэх болно.

Цагаан будаа. 9.7.16. Та энэ буланд гурвалжин барьж болохгүй.

Өгөгдсөн олон өнцөгт дээр нэг гурвалжин байгуулах боломжгүй нөхцөл байдал байж болно. Зураг дээр. Зураг 9.7.16-д тус бүр дөрвөн сегментээс бүрдэх хоёр олон өнцөгтөөр хязгаарлагдсан талбайг үзүүлэв. Гаднах олон өнцөгтийн хувьд бид гурвалжинг үргэлжлүүлж чадахгүй, учир нь дотоод олон өнцөгт нь саад болж байна. Энэ тохиолдолд бид олон өнцөгтийн B ба C хоёр хөрш зэргэлдээ цэгүүдийг олох бөгөөд үүнд зориулж HRV гурвалжин байгуулж болно. P цэг нь ВС талын голд байрладаг бөгөөд шинэ гурвалжин нь олон өнцөгтүүдийг огтлохгүй тийм зайд байрладаг.

Гурвалжингийн бусад аргууд.

Гурвалжингийн өөр аргууд байдаг. Жишээлбэл, гадаргуугийн тодорхойлолтын талбайн гадаад ба дотоод контурын олон өнцөгтийг байгуулсны дараа гурвалжин байгуулах өөр стратегийг сонгож болно. Өөр нэг сонголт бол гурвалжинг эхлэхээс өмнө гаднах болон дотоод олон өнцөгтийг нэг олон өнцөгт болгон нэгтгэх явдал юм. Та тодорхой алгоритмыг ашиглан параметр тодорхойлох талбар дотор цэгүүдийг зурж, тэдгээрийн болон хилийн контурын олон өнцөгтийн цэгүүдийг ашиглан Delaunay гурвалжинг хийж болно. Эхлээд том гурвалжин байгуулж, дараа нь тэдгээрийг удирдах боломжтой хэмжээтэй болгон хуваах алгоритмууд байдаг.

Биеийн гурвалжин.

Биеийн гурвалжин гэдэг нь түүний нүүрний гадаргууг гурвалжин болгох замаар олж авсан гурвалжны багц юм. Тусдаа гадаргуугийн гурвалжинг нь биеийн нүүрний гурвалжингаас ялгаатай бөгөөд сүүлийн тохиолдолд зэргэлдээх нүүрний хилийн олон өнцөгтүүд нь нийцтэй байх ёстой (Зураг 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) томъёогоор тооцоолно.