2012 წლის 20 აგვისტო, 10:41 სთ

დელონეს მდგომარეობის შემოწმების ალგორითმის ოპტიმიზაცია შემოხაზული წრის განტოლებისა და მისი გამოყენების გზით

• გამოსახულების დამუშავება,
• პროგრამირება

მე გეტყვით საიდუმლოს, თუ როგორ სწრაფად შეამოწმოთ დელონეს მდგომარეობა ორი სამკუთხედისთვის.
სინამდვილეში, ოპტიმიზაცია თავისთავად აღწერილია ოდნავ უფრო დაბალი (იხ. "დელონის მდგომარეობის შემოწმების ალგორითმის ოპტიმიზაცია შემოხაზული წრის განტოლების მეშვეობით"), მაგრამ მე გეტყვით ყველაფერს თანმიმდევრობით.

ჩემს შემთხვევაში, სამკუთხედი გამოიყენება გამოსახულების მიკვლევისას, რათა დაყოს თვითმფრინავი პრიმიტიულ სექტორებად (სამკუთხედებად). როგორც მოგეხსენებათ, ის ასევე იყოფა რამდენიმე ეტაპად: მორგება, საზღვრების გამოვლენა, საზღვრების გვერდის ავლით, კონტურების ამოღება. ეს არის ყველაზე ზოგადი გზით. მე მინდა შევჩერდე, ვფიქრობ, ყველაზე რთულ ეტაპზე: თვითმფრინავის წმენდა.

Შესასვლელთან

გამომავალზე საზღვრების აღმოჩენისა და გვერდის ავლით, მე მივიღე ბევრი გარე კონტური. თითოეულ შეხების კონტურს განსხვავებული ფერი აქვს. თითოეული ასეთი კონტური ასევე შეიცავს შიდა კონტურების ცნობილ რაოდენობას.
ამრიგად, „თვითმფრინავის გაწმენდის“ თვალსაზრისით, თუ გარე კონტურებს ცალკე განვიხილავთ, გვაქვს წერტილების ნაკრები, რომელთაგან თითოეულს აქვს ერთი მეზობელი მარჯვნივ და მარცხნივ. იმათ. ყველა წერტილი დახურულია ჯაჭვში, არ არის ერთი "ჩაკიდებული" წერტილი და თითოეული ჯაჭვი შეიცავს მინიმუმ 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 გრადუსზე მეტი. წიგნში ის განიხილება, როგორც ერთ-ერთი ცალკეული კერძო მეთოდი. და ამით ქრება მთელი მისი ელეგანტურობა, გამჭვირვალობა და შესრულება. და ასევე მოგვიანებით გაირკვა, რომ მეთოდი No2 შეიძლება იყოს ძალიან მნიშვნელოვანი ოპტიმიზაცია.

სურათი 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 არის გადაკვეთის მიმართულების ნიშანი, თავიდანვე ავაშენე სამკუთხედები საათის ისრის მიმართულებით, რომ გამოტოვოთ (ის უდრის ერთს).

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. სკვორცოვი ა.ვ. Delaunay triangulation და მისი გამოყენება. - ტომსკი: გამომცემლობა ტ. უნ-ტა, 2002. - 128გვ. ISBN 5-7511-1501-5 2012 წლის 20 აგვისტო, 10:41 სთ

დელონეს მდგომარეობის შემოწმების ალგორითმის ოპტიმიზაცია შემოხაზული წრის განტოლებისა და მისი გამოყენების გზით

მე გეტყვით საიდუმლოს, თუ როგორ სწრაფად შეამოწმოთ დელონეს მდგომარეობა ორი სამკუთხედისთვის.
სინამდვილეში, ოპტიმიზაცია თავისთავად აღწერილია ოდნავ უფრო დაბალი (იხ. "დელონის მდგომარეობის შემოწმების ალგორითმის ოპტიმიზაცია შემოხაზული წრის განტოლების მეშვეობით"), მაგრამ მე გეტყვით ყველაფერს თანმიმდევრობით.

ჩემს შემთხვევაში, სამკუთხედი გამოიყენება გამოსახულების მიკვლევისას, რათა დაყოს თვითმფრინავი პრიმიტიულ სექტორებად (სამკუთხედებად). როგორც მოგეხსენებათ, ის ასევე იყოფა რამდენიმე ეტაპად: მორგება, საზღვრების გამოვლენა, საზღვრების გვერდის ავლით, კონტურების ამოღება. ეს არის ყველაზე ზოგადი გზით. მე მინდა შევჩერდე, ვფიქრობ, ყველაზე რთულ ეტაპზე: თვითმფრინავის წმენდა.

Შესასვლელთან

გამომავალზე საზღვრების აღმოჩენისა და გვერდის ავლით, მე მივიღე ბევრი გარე კონტური. თითოეულ შეხების კონტურს განსხვავებული ფერი აქვს. თითოეული ასეთი კონტური ასევე შეიცავს შიდა კონტურების ცნობილ რაოდენობას.
ამრიგად, „თვითმფრინავის გაწმენდის“ თვალსაზრისით, თუ გარე კონტურებს ცალკე განვიხილავთ, გვაქვს წერტილების ნაკრები, რომელთაგან თითოეულს აქვს ერთი მეზობელი მარჯვნივ და მარცხნივ. იმათ. ყველა წერტილი დახურულია ჯაჭვში, არ არის ერთი "ჩაკიდებული" წერტილი და თითოეული ჯაჭვი შეიცავს მინიმუმ 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 გრადუსზე მეტი. წიგნში ის განიხილება, როგორც ერთ-ერთი ცალკეული კერძო მეთოდი. და ამით ქრება მთელი მისი ელეგანტურობა, გამჭვირვალობა და შესრულება. და ასევე მოგვიანებით გაირკვა, რომ მეთოდი No2 შეიძლება იყოს ძალიან მნიშვნელოვანი ოპტიმიზაცია.

სურათი 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 არის გადაკვეთის მიმართულების ნიშანი, თავიდანვე ავაშენე სამკუთხედები საათის ისრის მიმართულებით, რომ გამოტოვოთ (ის უდრის ერთს).

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. სკვორცოვი ა.ვ. Delaunay triangulation და მისი გამოყენება. - ტომსკი: გამომცემლობა ტ. უნ-ტა, 2002. - 128გვ. ISBN 5-7511-1501-5

აგებული სამკუთხედის ხარისხის გასაზომად, ჩვენ განვსაზღვრავთ ორი ტიპის კრიტერიუმს, ტოპოლოგიურ და გეომეტრიულს.

ტოპოლოგიური კრიტერიუმი ეფუძნება წერტილის უახლოეს მეზობლებს სიმრავლიდან. იდეალურ შემთხვევაში, წერტილს ჰყავს 6 მეზობელი 2D რეგიონისთვის და 12 მეზობელი 3D რეგიონისთვის. ჩვენ ვიღებთ ტოპოლოგიურ შეფასებას (1) ფორმულის გამოყენებით, სადაც არის პუნქტების საერთო რაოდენობა რეგიონში, არის მეზობელი წერტილების ხარისხი ან რაოდენობა, რომლებიც დაკავშირებულია შიდა წერტილთან.

გეომეტრიული კრიტერიუმი დაფუძნებულია გამოთვლილი სამკუთხა ელემენტის გარშემო შემოხაზულ და შემოხაზულ წრეებს შორის განსხვავებაზე. ჩვენ ვიღებთ გეომეტრიულ შეფასებას ფორმულის გამოყენებით (2), სადაც არის სამკუთხედების რაოდენობა, არის შემოხაზული წრის რადიუსი, არის შემოხაზული წრის რადიუსი.

სამკუთხედის აგების ალგორითმები

არსებობს დიდი რაოდენობით ალგორითმები სამკუთხედის ასაგებად. ისინი ერთმანეთისგან განსხვავდებიან შრომისმოყვარეობით, კომპიუტერზე განხორციელების სირთულით და მშენებლობისადმი მიდგომებით. ალგორითმების შესახებ მეტი შეგიძლიათ გაიგოთ წიგნში A.V. სკვორცოვა. განვიხილოთ რამდენიმე ალგორითმი.

ერთ-ერთი პირველი შემოთავაზებული ხარბ ალგორითმისამკუთხედის აგება. დელონეს სამკუთხედს უწოდებენ ხარბს, თუ იგი აგებულია ხარბი ალგორითმის გამოყენებით. ხარბ ალგორითმის სირთულე მისი ზოგიერთი გაუმჯობესებით არის . პრაქტიკაში ასეთი დიდი სირთულის გამო იგი თითქმის არასოდეს გამოიყენება. განვიხილოთ ალგორითმი ეტაპობრივად:

Ნაბიჯი 1.ყველა შესაძლო ხაზის სეგმენტების სია, რომლებიც აკავშირებს წყაროს წერტილების წყვილებს, გენერირებულია და დალაგებულია სეგმენტების სიგრძის მიხედვით.

ნაბიჯი 2უმოკლესიდან დაწყებული, სეგმენტები თანმიმდევრულად არის ჩასმული სამკუთხედში. თუ სეგმენტი არ იკვეთება სხვა ადრე ჩასმული სეგმენტებთან, მაშინ ის ჩასმულია, წინააღმდეგ შემთხვევაში ის უგულებელყოფილია.

გაითვალისწინეთ, რომ თუ ყველა შესაძლო სეგმენტს აქვს სხვადასხვა სიგრძე, მაშინ ამ ალგორითმის შედეგი ცალსახაა, წინააღმდეგ შემთხვევაში ეს დამოკიდებულია იმავე სიგრძის სეგმენტების ჩასმის თანმიმდევრობაზე.

განმეორებითი ალგორითმიდაფუძნებულია ძალიან მარტივ იდეაზე ქულების თანმიმდევრული დამატების შესახებ ნაწილობრივ აგებულ დელონეს სამკუთხედზე. ამ ალგორითმის სირთულე მოიცავს სამკუთხედის პოვნის სირთულეს, რომელსაც ემატება წერტილი შემდეგ ეტაპზე, ახალი სამკუთხედების აგების სირთულეს, ასევე სამკუთხედის სტრუქტურის შესაბამისი აღდგენის სირთულეს არადამაკმაყოფილებლის შედეგად. მიღებული სამკუთხედის მეზობელი სამკუთხედების წყვილების შემოწმება დელონეს მდგომარეობისთვის. განვიხილოთ ალგორითმი ეტაპობრივად:

Ნაბიჯი 1.პირველ სამ საწყის წერტილზე ვაშენებთ ერთ სამკუთხედს.

ნაბიჯი 2ყველა სხვა პუნქტის მარყუჟში შეასრულეთ ნაბიჯები 3-5.

ნაბიჯი 3უკვე აგებულ სამკუთხედის სტრუქტურას შემდეგი მე-ე წერტილი ემატება შემდეგნაირად. ჯერ წერტილი ლოკალიზებულია, ე.ი. არის სამკუთხედი (ადრე აგებული), რომელშიც მოდის შემდეგი წერტილი. ან, თუ წერტილი არ მოხვდება სამკუთხედის შიგნით, სამკუთხედის საზღვარზე არის სამკუთხედი, რომელიც ყველაზე ახლოს არის შემდეგ წერტილთან.

ნაბიჯი 4თუ წერტილი მოხვდება ადრე ჩასმული სამკუთხედის კვანძში, მაშინ ასეთი წერტილი ჩვეულებრივ უგულვებელყოფილია, წინააღმდეგ შემთხვევაში წერტილი ჩასმულია სამკუთხედში, როგორც ახალი კვანძი. უფრო მეტიც, თუ წერტილი რომელიმე ზღვარზე მოხვდა, მაშინ ის იყოფა ორ ახალად, ხოლო კიდესთან მიმდებარე ორივე სამკუთხედი ასევე იყოფა ორ უფრო მცირედ. თუ წერტილი მკაცრად არის რომელიმე სამკუთხედის შიგნით, ის იყოფა სამ ახალ სამკუთხედად. თუ წერტილი სამკუთხედის გარეთაა, მაშინ აგებულია ერთი ან მეტი სამკუთხედი.

ნაბიჯი 5ტარდება ახლად მოპოვებული სამკუთხედების ლოკალური შემოწმება დელონეს პირობასთან შესაბამისობაში და საჭირო გადაწყობები.

ახალი სამკუთხედების აგებისას შესაძლებელია ორი სიტუაცია, როდესაც დამატებული წერტილი ეცემა სამკუთხედის შიგნით ან მის გარეთ. პირველ შემთხვევაში აგებულია ახალი სამკუთხედები და ფიქსირდება ალგორითმის მიერ შესრულებული მოქმედებების რაოდენობა. მეორეში აუცილებელია მიმდინარე სამკუთხედის გარეგანი დამატებითი სამკუთხედების აგება და მათი რიცხვი უარეს შემთხვევაში შეიძლება იყოს ტოლი? 3. თუმცა, ალგორითმის ყველა საფეხურისთვის, არაუმეტეს სამკუთხედები დაემატება, სადაც არის საწყისი წერტილების საერთო რაოდენობა. აქედან გამომდინარე, ორივე შემთხვევაში, სამკუთხედების აშენებაზე დახარჯული მთლიანი დრო არის.

ჯაჭვის ალგორითმიერთ-ერთი პირველი ეფექტური სამკუთხედის აგების ალგორითმი დაფუძნებულია პლანშეტური გრაფიკის რეგულაციის პროცედურასა და მონოტონურ მრავალკუთხედის სამკუთხედზე. ამ ალგორითმის სირთულე არის ის, სად არის საწყისი სეგმენტების რაოდენობა. განვიხილოთ ალგორითმი ეტაპობრივად:

Ნაბიჯი 1.საწყისი სტრუქტურული სეგმენტების სიმრავლიდან ჩვენ ვქმნით დაკავშირებულ პლანტურ გრაფიკს (სურათი 4, ა).

ნაბიჯი 2გრაფიკი მოწესრიგებულია, ე.ი. ემატება ახალი კიდეები, რომლებიც არ კვეთენ სხვებს, ისე, რომ გრაფის თითოეული წვერო მიმდებარედ იქცეს მინიმუმ ერთ წვეროსთან მის ზემოთ და ერთი მის ქვემოთ. რეგულაცია ხდება ორ უღელტეხილზე ვერტიკალური ბრტყელი სვირის გამოყენებით. პირველ გადასასვლელში ქვემოდან ზევით, თანმიმდევრულად ვპოულობთ ყველა წვეროს, საიდანაც არ არის წინ წამოწეული კიდეები. მაგალითად, (სურათი 4, ბ)-ზე ეს არის B წვერო. ჰორიზონტალური ხაზის დახატვით ვპოულობთ მის მიერ გადაკვეთილ AD და EF გრაფიკების უახლოეს კიდეებს მარცხნივ და მარჯვნივ. შემდეგ DEHG ოთხკუთხედში ვპოულობთ ყველაზე დაბალ წვეროს და ვხატავთ მასში B-დან კიდეს. ანალოგიურად, მეორე გადასასვლელი სრულდება ზემოდან ქვევით (სურათი 4, გ). ამ ნაბიჯის შედეგად, პლანშეტური გრაფიკის თითოეული არე იქცევა მონოტონურ მრავალკუთხედად.

ნაბიჯი 3გრაფიკის თითოეული ტერიტორია უნდა დაიყოს სამკუთხედებად. ამისათვის შეგიძლიათ გამოიყენოთ ორი სამკუთხედის არაამოზნექილი შერწყმის ალგორითმი (სურათი 4, დ).

ნახაზი 4. სამკუთხედის ჯაჭვის ალგორითმის მოქმედების სქემა: ა) - საწყისი სეგმენტები; ბ - გადასასვლელი გრაფის რეგულაცია ქვემოდან ზევით; გ) - გადასასვლელი ზემოდან ქვემოდან; დ) - ერთფეროვანი მრავალკუთხედების სამკუთხედი

ჯაჭვის ალგორითმის განსახორციელებლად, უმჯობესია გამოვიყენოთ მონაცემთა სტრუქტურები, რომლებშიც კიდეები აშკარად არის წარმოდგენილი, როგორიცაა "ორმაგი კიდეები" ან "კვანძები, კიდეები და სამკუთხედები".

ჯაჭვის ალგორითმის მინუსი არის ის, რომ წინასწარ არაფერი შეიძლება ითქვას მიღებული სამკუთხედის ფორმის შესახებ. ეს არ არის ოპტიმალური სამკუთხედი, არც ხარბი და არც დელონეს შეზღუდული სამკუთხედი. ჯაჭვის ალგორითმს შეუძლია შექმნას ძალიან გრძელი წაგრძელებული სამკუთხედები.

შედეგად მიღებული სამკუთხედის ხარისხის გასაუმჯობესებლად, მეზობელი სამკუთხედების ყველა წყვილი, რომელიც არ არის გამოყოფილი სტრუქტურული კიდით, შეიძლება შემოწმდეს დელონეს მდგომარეობის შესასრულებლად და, საჭიროების შემთხვევაში, ხელახლა აშენება. შედეგად მიიღება დელონეს სამკუთხედი შეზღუდვებით.

GRID მოდელები არის ჩვეულებრივი უჯრედების მოდელები.

მოდით კოორდინატთა სისტემა
და და
. მომხმარებლის ნაკრები
და შერჩევის ნაბიჯები
.

,

- წერტილის ფიზიკური კოორდინატები.

გამოთვალეთ
და
,
- ბიტიანი ბადე.

- კვანტური მნიშვნელობები. რეალური:

- ალგორითმის პარამეტრი - ქულების რაოდენობა, - წონა. რაც უფრო ახლოსაა წერტილი, მით მეტია წონა.

- მანძილის ხარისხი (1 ან 2).

ნორმალიზების ფაქტორი:

Როგორ 1-თან უფრო ახლოს, მხედველობაში მიიღება მეტი შეწონილი ქულა.

ეს არის IDW მეთოდი - გრძელი, ყოველი თ-ისთვის საჭიროა მეზობლების პოვნა. მეზობლების ნაკრები შეიძლება ეფექტურად მოიძებნოს - უახლოესი. თითოეული წერტილი აწარმოებს გარკვეული სიმაღლის „სამაგრს“. ბევრი რამ არის დამოკიდებული წერტილის დაყენების არარეგულარულობაზე, ამისათვის ისინი იღებენ
ან
იმათ. დაყავით სექტორებად და ააგეთ წერტილის სიახლოვეს.

უპირატესობა- სიმარტივე

ხარვეზი:

------ბილეთი 14. თუნუქის მოდელი. დელონეს სამკუთხედის ალგორითმები ------

1) ტრიანგულაცია (კალის).

სამკუთხედი– ფუნქციის აგება ცალი წრფივი ფუნქციის სიმრავლის სახით

სამკუთხედი- ინტერპოლაცია ამოზნექილი რეგიონის შიგნით.

სამკუთხედიარის პლანშეტური გრაფიკი, რომლის შიდა კიდეები სამკუთხედია; სივრცის წარმოდგენის გზა სამკუთხედების სახით, რომლებიც ერთმანეთს ემთხვევა გადახურვის გარეშე. სამკუთხედი აგებულია წერტილების ერთობლიობაზე რამდენიმე გზით.

ჩვენ გვჭირდება ალგორითმი ოპტიმალური სამკუთხედის ასაშენებლად.

თვითმფრინავი, რომელიც გადის 3 წერტილს.

1) იპოვეთ სამკუთხედი, რომელიც
;

2)
- ჩვენ ვქმნით თვითმფრინავის განტოლებას.

იმის შესამოწმებლად, არის თუ არა წერტილები სამკუთხედის შიგნით, თქვენ უნდა ჩაანაცვლოთ მნიშვნელობა ხაზების განტოლებაში - სამკუთხედის კიდეები. თუ სამივე განტოლება > 0, მაშინ შიგნით.

სტრუქტურის ნახვა:

თითოეული სამკუთხედი შეიცავს სამკუთხედების იგივე რაოდენობას.

, სად არის შიდა ქულების რაოდენობა,
- ქულების რაოდენობა.

ხარბი სამკუთხედი.

ჩვენ ვაკავშირებთ ყველა წერტილს კიდეებით, ვირჩევთ მინიმუმს, ვამატებთ სამკუთხედს. შემდეგი, ვიღებთ შემდეგ მინიმუმს, რომელიც არ იკვეთება წინასთან და ა.შ. შედეგი არის ხარბი სამკუთხედი.

დელონეს სამკუთხედი.

სხვა სამკუთხედების წერტილები არ ხვდება რომელიმე სამკუთხედის გარშემო შემოხაზულ წრეში. აგებულია ერთი გზით.

Flip არის Flip of კიდეები. ის საშუალებას გაძლევთ გადახვიდეთ ჩვეულებრივი სამკუთხედიდან Delaunay triangulation-ზე. იმის შესამოწმებლად, მიეკუთვნება თუ არა წერტილი წრეს: ჩაანაცვლეთ თუ< R, то внутри.

დელონეს მდგომარეობა.

წრის განტოლება, რომელიც გადის სამ წერტილში:

თუ ნულზე ნაკლებია, მაშინ გარე, წინააღმდეგ შემთხვევაში - შიდა.

არის დელონეს მდგომარეობა.

დელონეს სამკუთხედის აგების ალგორითმი:

1) გამოძიების პროცესშია ქულების დამატებაარის მარტივი განმეორებითი ალგორითმი:

არის კომპლექტი
სამკუთხედის დამატება, მშენებლობა ხორციელდება
სამკუთხედის დანაყოფი
აღმშენებლობა. ნულოვან ეტაპზე ვამატებთ 3-4 ფიქტიურ წერტილს, რომელიც აშკარად ფარავს ჩვენს კონვერტს, ყველა წერტილი შიგნით არის. წერტილის დაყრის შემდეგ შეხედეთ რომელ სამკუთხედს მოხვდა, გაყავით 3-ად, თითოეული სამკუთხედისთვის ვამოწმებთ დელონეს მდგომარეობას და ვაბრუნებთ კიდეებს. აღდგენის საშუალო რაოდენობა არის სამი.

თეორიული სირთულე

2) აჩქარების მეთოდები.სტატისტიკურად დამოკიდებულ წერტილებზე დაყრდნობით. სათესლე სამკუთხედი არის სამკუთხედი, რომელშიც წინა წერტილი დაეცა. შემდეგ ჩვენ ვაკავშირებთ ორ წერტილს - წინა და ახალი.

პირველი წერტილიდან მეორეზე გადავდივართ.

(შეზღუდული მოცულობის სამკუთხედების ალგორითმების შემუშავება და დანერგვა: განმეორებითი ალგორითმები
წინასწარი ბეჭდვა, ინსტ. აპლ. მათემატიკა, რუსეთის მეცნიერებათა აკადემია)

გალანინი მ.პ., შჩეგლოვი ი.ა.
(მ.პ.გალანინი, ი.ა.შეგლოვი)

IPM მათ. M.V. Keldysh RAS

მოსკოვი, 2006 წ
ნაშრომი მხარდაჭერით განხორციელდა რუსეთის საბაზისო კვლევების ფონდის მიერ (პროექტი No. 06-01-00421)

ანოტაცია

განიხილება სივრცითი დომენების სამგანზომილებიანი დისკრეტიზაციის იტერაციული მეთოდები (ტეტრაედრული ბადეების აგება): საზღვრების კორექტირების მეთოდები, დელონის კრიტერიუმზე დაფუძნებული მეთოდები და ამოწურვის მეთოდები. მოცემულია ალგორითმების ვარიანტები თითოეული ამ მეთოდისთვის. განხილულია კომპლექსურ დომენებში ბადეების აგების თავისებურებები.

Აბსტრაქტული

აღწერილია განმეორებითი ალგორითმების სამი ძირითადი ოჯახი თავისუფალი და შეზღუდული მარტივი მოცულობის სამკუთხედისთვის: საზღვრების კორექცია (მათ შორის "octree" ალგორითმი), Delaunay-ზე დაფუძნებული მეთოდები და წინსვლის წინსვლის მიდგომა. თითოეული მეთოდისთვის მოცემულია მაგალითის ალგორითმი.

1. შესავალი 3

2. საზღვრების კორექტირების მეთოდები4

2.1 პირველადი ბადის მშენებლობა4

2.2 პირველადი ბადის კორექტირება6

3. დელონის კრიტერიუმზე დაფუძნებული მეთოდები9

3.1 დელონეს სამკუთხედის აგება 12 წერტილების მოცემულ კომპლექტზე

3.2. Delaunay triangulation შეზღუდვებით17

3.3 ალგორითმების ტექნიკური განხორციელების თავისებურებები ეფუძნება
დელონეს კრიტერიუმი 22

4. ამოწურვის მეთოდები23

4.1 ამოწურვის ალგორითმის მაგალითი26

ცნობები 3 0

1. შესავალი

სამკუთხედის მეთოდების ორ კლასს შორის - პირდაპირი და განმეორებითი - ამ უკანასკნელს აქვს საკმარისი უნივერსალურობა და, შესაბამისად, პირდაპირისგან განსხვავებით, შეიძლება გამოყენებულ იქნას საკმაოდ თვითნებური ფორმის რეგიონების სამკუთხედისთვის. ეს მრავალფეროვნება მოდის რესურსების მნიშვნელოვნად მაღალი მოხმარებისა და მეთოდის უფრო შრომატევადი განხორციელების ხარჯზე კონკრეტულ ალგორითმში.

ამჟამად შემუშავებულია პროგრამული პაკეტების დიდი რაოდენობა ამა თუ იმ განმეორებითი მეთოდის საფუძველზე, რომელიც ახორციელებს ბადეების აგებას (ნაწილობრივ ან მთლიანად) ავტომატურ რეჟიმში. ძირითადად, ეს პაკეტები კომერციულია, რაც სავსებით გამართლებულია მათ შექმნაზე დახარჯული ძალისხმევის გათვალისწინებით, რადგან სამგანზომილებიან სივრცეს აქვს არაერთი უსიამოვნო მახასიათებელი, რაც მნიშვნელოვნად ართულებს დეველოპერის ცხოვრებას.

განმეორებითი მეთოდებით აგებული ბადეები, როგორც წესი, არასტრუქტურირებული და არაერთგვაროვანია. არასტრუქტურულობა განპირობებულია იმით, რომ ბადის ტოპოლოგია ყალიბდება მშენებლობის პროცესში და, შესაბამისად, ის ბუნებრივად შეიძლება განსხვავდებოდეს იმავე ქვედომენშიც კი. ამავე მიზეზით, ჰომოგენურობა, თუ შეიძლება წარმოიშვას, მხოლოდ შემთხვევითია.

იმის გამო, რომ ბადის აშენებამდე მის მომავალ სტრუქტურაზე ვერაფერს ვიტყვით, მისი ხარისხის გარანტიაც შეუძლებელია. ხშირად, აშენებული ბადე შეიძლება მნიშვნელოვნად გაუმჯობესდეს ოპტიმიზაციის მრავალი ტექნიკის გამოყენებით. ეს შესაძლებლობა, როგორც წესი, არ არის უგულებელყოფილი, რადგან ოპტიმიზაციაზე დახარჯული დრო, როგორც წესი, მნიშვნელოვნად ნაკლებია მშენებლობაზე დახარჯულ დროს.

ამ სამუშაოს მიზანია სამგანზომილებიანი დომენების ტეტრაედრული ბადეების აგების არსებული მეთოდების მიმოხილვა და კლასიფიკაცია. ინფორმაციის მნიშვნელოვანი მოცულობის გათვალისწინებით, ქვემოთ განიხილება მხოლოდ ე.წ. „იტერაციული მეთოდები“. პირდაპირი მეთოდები აღწერილია ში.

ეს ნაშრომი ნაწილობრივ მხარდაჭერილი იყო რუსეთის ძირითადი კვლევების ფონდის მიერ (პროექტი No. 06-01-00421).

ბრინჯი. 11. დომენის სამკუთხედი, რომელიც წარმოადგენს დოდეკედრონისა და იკოსაედრის გაერთიანებას (დელონეის სამკუთხედი შეზღუდვებით)

ამ მეთოდით აგებული ბადეების ხარისხი საშუალო დონეზეა (საზღვრებთან ახლოს ტეტრაედრებს შეიძლება ჰქონდეს ძალიან ცუდი ფორმა), ამიტომ, როგორც წესი, დამატებით მიმართავენ ოპტიმიზაციის ერთ-ერთ მეთოდს.

ბ.ჯოს ნაშრომებში შემოთავაზებულია ალგორითმის სხვა ვარიანტები, რომლებიც არ იყენებენ დამატებით წერტილებს და მთლიანად ეფუძნება „ვაჭრობის“ მსგავს ლოკალურ გარდაქმნებს.

4) ტეტრაედრის მოცულობა არ არის მაქსიმალურ დასაშვებზე ().

ყველა ტეტრაჰედრიდან () შეირჩევა საუკეთესო ხარისხის ტეტრაედონი და ხდება მე-5 საფეხურზე გადასვლა; თუ არ არსებობს ტეტრაჰედრები, რომლებიც აკმაყოფილებენ მითითებულ პირობებს, მაშინ ხდება მე-4 საფეხურზე გადასვლა.

4. ჯერ კიდევ ამოუწურავი რეგიონის შიგნით არის ისეთი წერტილი, რომ:

1) ტეტრაედონი () აკმაყოფილებს მე-3 პუნქტის ყველა პირობას;

2) ბურთში არ არის დისტანციური წერტილიფ(ეს ხელს უშლის კვანძის განთავსებასგვ ძალიან ახლოს არსებული ტეტრაედრების სახეებთან და წვეროებთან).

კვანძის ძიების ალგორითმის ვარიანტიგვგანხილული ქვემოთ.

5. ამოიღეთ ყველა წვეროფჩამოყალიბებული ტეტრაედონის შიგნით (და საზღვრებზე) დაცემა. შემდეგ წინა მხარე განახლდება შემდეგი სქემის მიხედვით: განიხილება ჩამოყალიბებული ტეტრაედონის თითოეული სახე და

1) თუ სახე არის წინა სახე, მაშინ იგი ამოღებულია წინა მხრიდან;

2) თუ სახე არ არის წინა სახე, ის ემატება წინა მხარეს.

6. თუ ჯერ კიდევ არის წაშლილი ქულებიფან (რომელიც ექვივალენტურია) წინა მხარე ცარიელი არ არის (ანუ რეგიონი ჯერ ბოლომდე არ არის ამოწურული), შესრულებულია გადასვლა 1-ლ საფეხურზე, წინააღმდეგ შემთხვევაში პროცესი დასრულებულია.

ასე რომ, მასივიფგამოიყენება ერთდროულად რამდენიმე მიზნით: მყარი კუთხის მნიშვნელობის შესაფასებლად, კონსტრუქციის სისწორის გასაკონტროლებლად და ახალი კვანძების განლაგების გასაკონტროლებლად. ასევე მასივიფსასარგებლოა პროგრესის აღსანიშნავად. ალგორითმის მუშაობისას ამოღებული წერტილების რაოდენობის თანაფარდობაფარსებული პუნქტების საწყის რაოდენობამდეფრეალურად გვიჩვენებს რა ფართობის უკვე ამოწურულია.

დავუბრუნდეთ ტეტრაედრის ასაგებად ახალი კვანძის კოორდინატების პოვნის საკითხს (აღწერილი ალგორითმის მე-4 პუნქტი). დაე, სამი კვანძი - მიეცეს.

1. პირველ საფეხურზე ვპოულობთ - სამკუთხედის მასის ცენტრს (როგორც მისი კვანძების კოორდინატების არითმეტიკული საშუალო) და სახის სიბრტყის ნორმალურ ერთეულს (ნორმალიზებული ვექტორული პროდუქტის მეშვეობით).

2. შემდეგი, პირველი მიახლოება განისაზღვრება მანძილით სასურველ წერტილამდეგვ (ჰ), ტეტრაედრის მაქსიმალური მოცულობის საფუძველზე: . გაითვალისწინეთ, რომ სახის ფართობისრეალურად ნაპოვნია წინა საფეხურზე (ორი კიდეების ჯვარედინი პროდუქტის შედეგი უდრის სახის ფართობის ორჯერ), ხოლო მაქსიმალური მოცულობა განისაზღვრება საკონტროლო ფუნქციის მნიშვნელობით.

3. წერტილი შემოწმებულია. თუ ტეტრაჰედონი () აკმაყოფილებს ყველა მოთხოვნას, გადადით მე-6 საფეხურზე, წინააღმდეგ შემთხვევაში გადადით მე-4 საფეხურზე.

4. წერტილი შემოწმებულია. თუ ტეტრაჰედონი () აკმაყოფილებს ყველა მოთხოვნას, გადადით მე-6 საფეხურზე, წინააღმდეგ შემთხვევაში გადადით მე-5 საფეხურზე.

5. გჯეროდეთ და გადადით მე-3 საფეხურზე.

6. მოიძებნა სასურველი კვანძი.

გაითვალისწინეთ, რომ 99% შემთხვევაში სასურველი წერტილი მდებარეობს ამ ალგორითმის 1 ან 2 გამეორებაზე.

ზემოთ აღწერილი ამოწურვის ალგორითმში თითო ტეტრაედონი ამოღებულია რეგიონიდან ყოველ საფეხურზე. ნასას თანამშრომელი შ.პირზადე (შაჰიარ პირზადე ) შემოგვთავაზა ალგორითმის კიდევ ერთი ვერსია, რომელშიც ტეტრაჰედრების მთელი ფენა ერთდროულად ამოღებულია რეგიონიდან (ანუ, ყოველი გამეორებისას, ტეტრაჰედრები აგებულია დაუყოვნებლივ მიმდინარე ფრონტის ყველა სახისთვის). მოლოდინის საპირისპიროდ, ეს ვარიანტი მნიშვნელოვნად არ აჩქარებს მშენებლობის პროცესს (რადგან ყველა ახალი ტეტრაედრის სისწორე ჯერ კიდევ უნდა შემოწმდეს), მაგრამ ის გამორიცხავს ტეტრაედრის ასაგებად ყველაზე შესაფერისი სახის ძებნის აუცილებლობას. თუმცა, ეს უფრო მინუსია, ვიდრე პლიუსი, რადგან ამ მახასიათებლის გამო, Pirzade-ის ვარიანტი ნაკლებად საიმედოა და გეომეტრიულად რთულ ადგილებში შეიძლება ჩავარდეს. ამავდროულად, ის კარგ შედეგებს აჩვენებს შედარებით მარტივ სფეროებში.

ამოწურვის მეთოდებით აგებულ ბადეებს, როგორც წესი, აქვთ კარგი ხარისხი, ხოლო კვანძების პოზიციის შემდგომი ოპტიმიზაცია იძლევა ხარისხის დამატებით ზრდას. შეჯამებით, ჩვენ აღვნიშნავთ, რომ ამოწურვის მეთოდები ყველაზე ეფექტურია, თუ თავდაპირველად დაყენებულია ფართობის საზღვრის სამკუთხედი. ეს არის მათი მთავარი განსხვავება დელონეს კრიტერიუმზე დაფუძნებული მეთოდებისგან, რომელთათვისაც სიტუაცია პირდაპირ საპირისპიროა.

ბიბლიოგრაფია

1. შაიდუროვი ვ.ვ. მულტიქსელის სასრულ ელემენტების მეთოდები. - მ., ნაუკა, 1989. - 288წ.

2. სკვორცოვი A.V. დელონეს სამკუთხედის აგების ალგორითმების მიმოხილვა // , 2002, №3, გ. 14-39.

3. სკვორცოვი A.V. სამკუთხედის აგების ალგორითმები შეზღუდვებით // გამოთვლითი მეთოდები და პროგრამირება, 2002, №3, გ. 82-92 წწ.

4. ი.ბაბუშკა, W.C. რაინბოლდტი. A-posteriori შეცდომის შეფასება სასრულ ელემენტების მეთოდისთვის // ინტ. ჯ ნუმერი. მეთ. ინჟ., ტ. 12, გვ. 1597-1615, 1978 წ.

5. თ.ჯ. ბეიკერი. ქსელის ავტომატური გენერაცია რთული სამგანზომილებიანი რეგიონებისთვის შეზღუდული დელონეს სამკუთხედის გამოყენებით // ინჟინერია კომპიუტერებით, Springer-Verlag, No5, გვ. 161-175, 1989 წ.

6. მ.ბერნი, დ.ეპშტეინი. ბადის გენერაცია და ოპტიმალური სამკუთხედი // გამოთვლა ევკლიდეს გეომეტრიაში, World Scientific Publishing Co., გვ. 23-90, 1995 წ.

7. დ.კ. ბლანფორდი, გ.ბლელოხი, დ.კარდოზე, კ.კადოუ. მარტივი ბადეების კომპაქტური წარმოდგენები ორ და სამ განზომილებაში // მე-12 საერთაშორისო მეშინგ მრგვალი მაგიდის მასალები, Sandia National Laboratories, p.p.135-146, Sept. 2003 წ.

8. ჰ.ბორუჩაკი, ს.ჰ. აჰა. სწრაფი დელონეს სამგანზომილებიანი სამკუთხედი // კომპიუტერული მეთოდები გამოყენებითი მექანიკისა და ინჟინერიაში, Elsevier, ტ. 128, გვ. 153-167, 1995 წ.

9. ე.კ. ბურატინსკი. სამგანზომილებიანი არასტრუქტურირებული ბადის გენერატორი თვითნებური შიდა საზღვრებისთვის // რიცხვითი ბადის გენერაცია გამოთვლითი სითხის მექანიკაში, Pineridge Press, გვ. 621-631, 1988 წ.

10. პ.რ. კავალკანტი, U.T. მელო. სამგანზომილებიანი შეზღუდული დელონეს სამკუთხედი: მინიმალისტური მიდგომა // მე-8 საერთაშორისო მეშინგ მრგვალი მაგიდის მასალები, გვ. 119-129, 1999 წ.

11. დეი, კ.ტამალი, კ. სუგიჰარა, კ.ლ. ბაჟაჟი. Delaunay Triangulations სამ განზომილებაში სასრული ზუსტი არითმეტიკით // კომპიუტერული გეომეტრიული დიზაინი, ჩრდილოეთ ჰოლანდია, No 9, გვ. 457-470, 1992 წ.

12. ჰ.ნ. ჯიჯევი. იძულებით მიმართული მეთოდები არასტრუქტურირებული სამკუთხა და ოთხკუთხა ბადეების გლუვისთვის // მე-9 საერთაშორისო მეშინგ მრგვალი მაგიდის მასალები, Sandia National Laboratories, გვ. 395-406, 2000 წლის ოქტომბერი.

13. ლ დურბეკი. აორთქლება: ბადის ხარისხის ვიზუალიზაციის ტექნიკა // მე-8 საერთაშორისო ქსელური მრგვალი მაგიდის მასალები, სამხრეთ ტბა ტაჰო, კალიფორნია, აშშ, გვ. 259-265, 1999 წლის ოქტომბერი.

14. დ.ა. ველი. ლაპლასიური დამარბილებელი და დელონის სამკუთხედები // , ტ. 4, გვ. 709-712, 1988 წ.

15. პ.ჯ. ფრეი, ჰ.ბორუჩაკი, პ.-ლ. გიორგი. Delaunay Tetrahedralization Using Advancing-Front Approach // მე-5 საერთაშორისო მეშინგ მრგვალი მაგიდის მასალები, Sandia National Laboratories, გვ. 31-46, 1996 წლის ოქტომბერი.

16. ლ.ა. ფრეიტაგი, C. Olivier-Gooch. ტეტრაჰედრული ბადის გაუმჯობესების ტექნიკის შედარება // მე-5 საერთაშორისო მეშინგ მრგვალი მაგიდის მასალები, Sandia National Laboratories, გვ. 87-106, 1996 წლის ოქტომბერი.

17. ლ.ა. Freitag, C. Olivier-Gooch. Tetrahedral Mesh Improvement Using Swapping and Smoothing // , ტ. 40, გვ. 3979-4002, 1995 წ.

18. ლ.ა. ფრეიტაგი, C. Olivier-Gooch. ქსელის ხარისხის გავლენა ხსნარის ეფექტურობაზე // მე-6 საერთაშორისო ქსელური მრგვალი მაგიდის მასალები, Sandia National Laboratories, გვ.249, 1997 წლის ოქტომბერი.

19. პ.ლ. გიორგი. TET MESHING: მშენებლობა, ოპტიმიზაცია და ადაპტაცია // მე-8-ის შრომებისაერთაშორისო ქსელის მრგვალი მაგიდა, გვ.133-141, 1999 წ.

20. ნ.ა. გოლიასი, თ.დ. ციბუკისი. მიდგომა სამგანზომილებიანი ტეტრაედრული ბადეების დახვეწისკენ, დელონეს ტრანსფორმაციების საფუძველზე // , ჯონ უილი, No 37, გვ.793-812, 1994 წ.

21. C. Hazlewood. შეზღუდული ტეტრაჰედრალიზაციების მიახლოება // კომპიუტერული გეომეტრიული დიზაინი, ტ. 10, გვ. 67–87, 1993 წ.

22. ბ.ჯო. დელონეს სამკუთხა ბადეები ამოზნექილ მრავალკუთხედებში, SIAM J Sci. სტატისტიკა გამოთვლა., ტ. 7, გვ. 514-539, 1986 წ.

23. ბ.ჯო. სამგანზომილებიანი დელონეს სამკუთხედების აგება ლოკალური ტრანსფორმაციების გამოყენებით // კომპიუტერული გეომეტრიული დიზაინი, ტ. 8, გვ. 123-142, 1991 წ.

24. ბ.ჯო. სამგანზომილებიანი გაუმჯობესებული ხარისხის სამკუთხედების აგება ლოკალური ტრანსფორმაციების გამოყენებით // Siam J. Sc. გამოთვლა., ტ. 16, გვ. 1292-1307, 1995 წ.

25. რ.ვ. ლუისი, იაო ჟენგი, დ.ტ. გეთინი. სამგანზომილებიანი არასტრუქტურირებული ბადის გენერაცია: ნაწილი 3. მოცულობითი ბადეები // კომპიუტერული მეთოდები გამოყენებითი მექანიკისა და ინჟინერიაში Elsevier, Vol 134, გვ. 285-310, 1996 წ.

26. ა.ლიუ, ბ.ჯო. ტეტრაჰედრის ფორმის შესახებ ბისექციისგან // გამოთვლების მათემატიკა, ტ. 63, No207, 141–154, 1994 წ.

27. ს.ჰ. აჰა. მოცულობის დისკრეტიზაცია ტეტრაჰედრა-I-ში. სასაზღვრო ზედაპირების შემოწმება და ორიენტაცია // კომპიუტერები და სტრუქტურები, პერგამონის პრესა, ტ. 39, No5, გვ. 493-500, 1991 წ.

28. ს.ჰ. აჰა. მოცულობის დისკრეტიზაცია ტეტრაედრად - II. 3D ტრიანგულაცია წინა მიდგომით // კომპიუტერები და სტრუქტურები, პერგამონი, ტ. 39, No5, გვ. 501-511, 1991 წ.

29. რ.ლოჰნერი. სამგანზომილებიანი არასტრუქტურირებული ბადეების გენერაცია მოწინავე წინა მეთოდით // AIAA აეროკოსმოსური მეცნიერებების 26-ე შეხვედრის მასალები, რენო, ნევადა, 1988 წ.

30. ს.ჯ. ოუენი. არასტრუქტურირებული ბადის წარმოქმნის ტექნოლოგიის კვლევა // მე-7 საერთაშორისო მეშინგ მრგვალი მაგიდის მასალები, გვ. 239-269, დირბორნი, MI, 1998 წ.

31. ვ.ნ. პართასარათი, ც.მ. გრეიხენი, ა.ფ. ჰეთევეი. ტეტრაედრის ხარისხის საზომების შედარება // სასრული ელემენტები ანალიზსა და დიზაინში, ელზევიე, არა. 15, გვ. 255-261, 1993 წ.

32. ს.პირზადე. არასტრუქტურირებული ბლანტი ბადის გენერაცია მოწინავე-ფენების მეთოდით // AIAA-93-3453-CP, AIAA, გვ. 420-434, 1993 წ.

33. ვ.ტ. რაჯან. Delaunay Triangulation-ის ოპტიმალურობა // პროკ. მე-7 ACM სიმპტომი. კომპ. გეომეტრია, გვ. 357-363, 1991 წ.

34. ა.რასინე. ტეტრაჰედრული ბადეების გენერაცია და ოპტიმიზაცია წინა ტექნიკის წინსვლის გზით // International Journal for Numerical Methods in Engineering, უილი, ტ. 41, გვ. 651-674, 1998 წ.

35. ს.რებეი. ეფექტური არასტრუქტურირებული ბადის გენერაცია Delaunay Triangulation და Bowyer-Watson ალგორითმის საშუალებით // გამოთვლითი ფიზიკის ჟურნალი, ტ. 106, გვ. 125-138, 1993 წ.

36. M.-C. რივარა. შერჩევითი დახვეწა/დაზუსტების ალგორითმები ჩადგმული სამკუთხედების მიმდევრებისთვის // International Journal for Numerical Methods in Engineering, No28, გვ. 2889-2906, 1998 წ.

37. M.-C. რივარა, სი ლევინი. 3D დახვეწის ალგორითმი, რომელიც შესაფერისია ადაპტაციური და მულტიქსელური ტექნიკისთვის // კომუნიკაციები გამოყენებითი რიცხვითი მეთოდებით, No8, გვ. 281-290, 1998 წ.

38. ჯ.რუპერტი. Delaunay-ის დახვეწის ალგორითმი ხარისხიანი 2-განზომილებიანი ქსელის წარმოებისთვის // ჟურნალი ალგორითმები, No18, გვ. 548-585, 1995 წ.

39. ᲥᲐᲚᲑᲐᲢᲝᲜᲘ. მწყემსი, მ.კ. ჟორჟი. სამგანზომილებიანი ბადის გენერაცია სასრული ოქტრის ტექნიკით // International Journal for Numerical Methods in Engineering, ტ. 32, გვ. 709-749, 1991 წ.

40. ᲥᲐᲚᲑᲐᲢᲝᲜᲘ. შეფარდი, ფ. გუერიონი, ჯ.ე. ფლაჰერტი, რ.ა. ლუდვიგი, პ.ლ. ბაჰმანი. სასრული octree mesh გენერაცია ავტომატური ადაპტური 3D ნაკადის ანალიზისთვის // რიცხვითი ბადის გენერაცია გამოთვლითი სითხის მექანიკაშიმაიამი, 1988 წელი

41. კ.შიმადა, დ. გოსარდი. Bubble Mesh: ავტომატური სამკუთხა ქსელი არა მრავალმხრივი გეომეტრიის სფეროს შეფუთვით // საქმის წარმოება მე-3 სიმპოზიუმი მყარი მოდელირებისა და აპლიკაციების შესახებ , გვ. 409-419, 1995 წ.

42. K. Shimada, A. Yamada, T. Itoh. პარამეტრული ზედაპირების ანიზოტროპული სამკუთხა ბადე ელიფსოიდური ბუშტების მჭიდრო შეფუთვის საშუალებით // მე-6 საერთაშორისო ქსელური მრგვალი მაგიდის მასალები, გვ. 375-390, 1997 წ.

43. დ.ფ. უოტსონი. Delaunay Tessellation-ის გამოთვლა ვორონოის პოლიტოპებზე გამოყენებით // კომპიუტერული ჟურნალი, ტ. 24(2), გვ. 167-172, 1981 წ.

44. მ.ა. იერი, მ.ს. მწყემსი. სამგანზომილებიანი ბადის გენერაცია მოდიფიცირებული Octree ტექნიკით // International Journal for Numerical Methods in Engineering, ტ. 20, გვ. 1965-1990 წწ., 1984 წ.

45. გალანინი მ.პ., შჩეგლოვი ი.ა. რთული სივრცითი რეგიონების სამგანზომილებიანი სამკუთხედის ალგორითმების შემუშავება და განხორციელება: პირდაპირი მეთოდები. IPM წინასწარ ბეჭდვა im. მ.ვ. Keldysh RAN, 2006, პრესაში. ქულები, ე.ი. შტაინერის კვანძები - დამატებითი კვანძები, რომლებიც არ იყო თავდაპირველ კომპლექტში

შეიძლება ჩანდეს, რომ მე-2 პირობა გამომდინარეობს მე-3 პირობიდან, მაგრამ სინამდვილეში ეს ასე არ არის. მაგალითად, არსებული ტეტრაედონი შეიძლება იყოს მთლიანად შიგნითგამოცდილი ტეტრაედონი.