20. elokuuta 2012 klo 22.41

Algoritmin optimointi Delaunayn ehdon tarkistamiseksi rajatun ympyrän yhtälön ja sen soveltamisen kautta

• Kuvankäsittely ,
• Ohjelmointi

Kerron sinulle salaisuuden kuinka nopeasti tarkistaa Delaunayn ehto kahdelle kolmiolle.
Itse asiassa itse optimointia kuvataan hieman alempana (katso "Algoritmin optimointi Delaunayn ehdon tarkistamiseksi rajatun ympyrän yhtälön kautta"), mutta kerron sinulle kaikesta järjestyksessä.

Minun tapauksessani triangulaatiota käytetään kuvan jäljityksessä tason jakamiseksi primitiivisiksi sektoreiksi (kolmioiksi). Kuten tiedät, se on myös jaettu useisiin vaiheisiin: säätö, rajojen havaitseminen, rajojen ohittaminen, ääriviivojen lakaisu. Tämä on yleisimmällä tavalla. Luulen, että haluaisin lopettaa vaikeimpaan vaiheeseen: koneen lakaisemiseen.

Sisäänkäynnillä

Tunnistettuani ja ohitettuani rajat lähdössä, sain paljon ulkoisia ääriviivoja. Jokaisella koskettavalla ääriviivalla on eri väri. Jokainen tällainen ääriviiva sisältää myös tunnetun määrän sisäisiä ääriviivoja.
Siten "tason pyyhkäisyn" kannalta, jos tarkastellaan ulkoääriviivoja erikseen, meillä on joukko pisteitä, joista jokaisella on yksi naapuri oikealla ja vasemmalla. Nuo. kaikki pisteet ovat suljettuja ketjussa, siinä ei ole yhtä "riippuvaa" pistettä ja jokaisessa ketjussa on vähintään 3 pistettä (kuva 1).

Kuva 1

Mitä pitää tehdä

Kuva on lakaistava kolmioilla.

Hae

Kirjan luettuani en löytänyt yhtään (ainakaan yhtä) tapaa rakentaa Delaunayn kolmiomittausta, joka olisi ainakin jossain määrin sopiva minun tapaukseeni. En etsinyt muita kirjoja. Kyllä, ja tämä riitti, hän järjesti pääni ajatukset. Tämän seurauksena hän keksi oman "polkupyöränsä".

Algoritmi

1) Oletetaan aluksi, että tarkasteltavassa kuvassa on vain yksi sekvenssi. Sitten kaikki laskeutuu kolmioiden peräkkäiseen ottamiseen. Otamme minkä tahansa pisteen ja yritämme rakentaa kolmion naapuripisteistä. Jos kolmiota ei voitu rakentaa (näitä kahta pistettä yhdistävä viiva leikkaa jo rakennettujen kanssa tai suora kulkee poissulkemisvyöhykkeellä (kuva 2), siirrytään naapuripisteeseen, sanotaan oikealle. Kun seuraava Kolmio löytyy, lisäämme sen luetteloon (kuva 3), ja piste, josta se rakennettiin, poistetaan (kuva 4).

Kuva 2

Kuva 3

Kuva 4

Vielä yksi asia: kun tallennetaan seuraavaa kolmiota, on tarpeen tallentaa kärjet myötäpäivään ohituksella (oikeassa koordinaattijärjestelmässä). Tästä on hyötyä tulevaisuudessa laskentaresurssien vähentämisessä.

2) Toista vaihe 1, kunnes lakaisemme koko tason.

3) Jos sarjoja on useita, esim. yksi, ja sen sisällä on yksi tai useampi sisäinen ääriviiva (kuva 1). Tässä on tarpeen tarkastella jokaista sekvenssiä erikseen. Otetaan toinen sisäinen ääriviiva. Yhdestä ulkoisesta ja yhdestä sisäisestä teemme kaksi yksittäistä ääriviivaa. Tätä varten sinun on löydettävä kaksi "porttia" yhdestä piiristä toiseen. "Porttien" ehto: ne eivät saa leikata toisiaan (ne eivät saa koskettaa edes päitä), ne eivät saa leikata ääriviivojen kanssa (kuva 5).

Kuva 5

Kuva 6
4) Seuraavaksi sinun tulee syöttää vuorotellen kaikki sisäiset sekvenssit jo muodostettuihin, toisistaan ​​erotettuihin (kohta 3) sekvensseihin. Sinun on yhdistettävä siihen, joka sisältää uuden. Määritelmän mukaan mikään sisäinen sekvenssi ei kosketa tai leikkaa muita (joko yksi ulkoinen tai kaikki mahdolliset sisäiset osat), joten kaikki menee sujuvasti.
Kun portit on löydetty (kuva 6), on helppo rakentaa uusia sekvenssejä ja ohittaa ne nykyisen algoritmin pisteillä 1 ja 2 (kuva 7).

Kuva 7

5) Neljännen vaiheen jälkeen meillä on luettelo kolmioista (kuva 8). Ikään kuin olisimme jo selviytyneet tehtävästä, mutta kuvasta on vielä tehtävä kaunis: tarkista Delaunayn ehdon täyttyminen (kuva 9).

Kuva 8

Kuva 9

6) Tulevaisuudessa kerron sinulle kuudennesta kohdasta. Se koostuu peräkkäisestä ajosta vastaanotettujen kolmioiden luettelon läpi pisteen nro 5 mukaan. Ensin merkitsemme kaikki kolmiot "likaisiksi". Jokaisessa syklissä tarkistamme Delaunayn ehdon jokaiselle kolmiolle. Jos ehto ei täyty, rakennamme uudelleen ja merkitsemme naapurit ja nykyisen kolmion "likaiseksi". Jos ehto täyttyy, merkitse se puhtaaksi. Algoritmin toteutuksessani jokaisella kolmiolla on linkki naapureihinsa. Tässä tapauksessa 6. piste toimii nopeimmin.

Lisää viidennestä vaiheesta

Nyt tietääkseni on kaksi mahdollista tapaa määrittää, täyttävätkö kolmiot Delaunayn ehdon vai eivät: 1) Tarkista vastakkaisten kulmien summa. Sen on oltava pienempi kuin 180. 2) Laske rajatun ympyrän keskipiste ja laske etäisyys 4. pisteeseen. Kaikki tietävät, että Delaunayn ehto täyttyy, jos piste on rajatun ympyrän ulkopuolella.

Laskentateho #1: 10 kerto-/jakooperaatiota ja 13 yhteen-/vähennysoperaatiota.
Laskentateho #2: 29 kerto-/jako- ja 24 yhteen-/vähennyslaskua.

Esimerkiksi kirjassa lasketun laskentatehon kannalta vaihtoehto numero 1 on kannattavampi. Ja hän tajusi sen, jos ei... (Kuva 10). Kuten kävi ilmi, tämän menetelmän "kuljettimelle" asettamisen jälkeen oli epävarmuutta. Tämä on vaihtoehto, kun itse kulma A on suurempi kuin 180 astetta. Sitä käsitellään kirjassa yhtenä erillisistä yksityisistä menetelmistä. Ja tämän myötä kaikki sen eleganssi, läpinäkyvyys ja suorituskyky katoavat. Ja myös myöhemmin kävi ilmi, että menetelmää nro 2 voidaan optimoida erittäin merkittävästi.

Kuva 10

Algoritmin optimointi Delaunayn ehdon tarkistamiseksi rajatun ympyrän yhtälön kautta

Seuraava on puhdasta matematiikkaa.

Meillä on siis:
Pisteen M(X, Y) ehdon tarkistaminen pisteiden A(x1, y1), B(x2, y2), C(x3, y3) läpi kulkevan ympyrän yhtälöllä voidaan kirjoittaa seuraavasti:

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ merkki a ≥ 0

Yksityiskohdat löytyvät erinomaisesta kirjasta. (Ei, en ole kirjoittaja)
Eli merkki a on kulkusuunnan merkki, alusta asti rakensin kolmioita myötäpäivään, jotta se voidaan jättää pois (se on yhtä suuri kuin yksi).

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

D >= 0

Kuva 11

Eikö vain ole?

Kirjan mukaan taas

(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

Meillä on: 15 kerto-/jakooperaatiota ja 14 yhteen-/vähennysoperaatiota.

Kiitos huomiostasi. Odotan kritiikkiä.

Bibliografia

1. Skvortsov A.V. Delaunay-triangulaatio ja sen sovellus. - Tomsk: Publishing House Voi. un-ta, 2002. - 128 s. ISBN 5-7511-1501-5 20. elokuuta 2012 klo 22.41

Algoritmin optimointi Delaunayn ehdon tarkistamiseksi rajatun ympyrän yhtälön ja sen soveltamisen kautta

Kerron sinulle salaisuuden kuinka nopeasti tarkistaa Delaunayn ehto kahdelle kolmiolle.
Itse asiassa itse optimointia kuvataan hieman alempana (katso "Algoritmin optimointi Delaunayn ehdon tarkistamiseksi rajatun ympyrän yhtälön kautta"), mutta kerron sinulle kaikesta järjestyksessä.

Minun tapauksessani triangulaatiota käytetään kuvan jäljityksessä tason jakamiseksi primitiivisiksi sektoreiksi (kolmioiksi). Kuten tiedät, se on myös jaettu useisiin vaiheisiin: säätö, rajojen havaitseminen, rajojen ohittaminen, ääriviivojen lakaisu. Tämä on yleisimmällä tavalla. Luulen, että haluaisin lopettaa vaikeimpaan vaiheeseen: koneen lakaisemiseen.

Sisäänkäynnillä

Tunnistettuani ja ohitettuani rajat lähdössä, sain paljon ulkoisia ääriviivoja. Jokaisella koskettavalla ääriviivalla on eri väri. Jokainen tällainen ääriviiva sisältää myös tunnetun määrän sisäisiä ääriviivoja.
Siten "tason pyyhkäisyn" kannalta, jos tarkastellaan ulkoääriviivoja erikseen, meillä on joukko pisteitä, joista jokaisella on yksi naapuri oikealla ja vasemmalla. Nuo. kaikki pisteet ovat suljettuja ketjussa, siinä ei ole yhtä "riippuvaa" pistettä ja jokaisessa ketjussa on vähintään 3 pistettä (kuva 1).

Kuva 1

Mitä pitää tehdä

Kuva on lakaistava kolmioilla.

Hae

Kirjan luettuani en löytänyt yhtään (ainakaan yhtä) tapaa rakentaa Delaunayn kolmiomittausta, joka olisi ainakin jossain määrin sopiva minun tapaukseeni. En etsinyt muita kirjoja. Kyllä, ja tämä riitti, hän järjesti pääni ajatukset. Tämän seurauksena hän keksi oman "polkupyöränsä".

Algoritmi

1) Oletetaan aluksi, että tarkasteltavassa kuvassa on vain yksi sekvenssi. Sitten kaikki laskeutuu kolmioiden peräkkäiseen ottamiseen. Otamme minkä tahansa pisteen ja yritämme rakentaa kolmion naapuripisteistä. Jos kolmiota ei voitu rakentaa (näitä kahta pistettä yhdistävä viiva leikkaa jo rakennettujen kanssa tai suora kulkee poissulkemisvyöhykkeellä (kuva 2), siirrytään naapuripisteeseen, sanotaan oikealle. Kun seuraava Kolmio löytyy, lisäämme sen luetteloon (kuva 3), ja piste, josta se rakennettiin, poistetaan (kuva 4).

Kuva 2

Kuva 3

Kuva 4

Vielä yksi asia: kun tallennetaan seuraavaa kolmiota, on tarpeen tallentaa kärjet myötäpäivään ohituksella (oikeassa koordinaattijärjestelmässä). Tästä on hyötyä tulevaisuudessa laskentaresurssien vähentämisessä.

2) Toista vaihe 1, kunnes lakaisemme koko tason.

3) Jos sarjoja on useita, esim. yksi, ja sen sisällä on yksi tai useampi sisäinen ääriviiva (kuva 1). Tässä on tarpeen tarkastella jokaista sekvenssiä erikseen. Otetaan toinen sisäinen ääriviiva. Yhdestä ulkoisesta ja yhdestä sisäisestä teemme kaksi yksittäistä ääriviivaa. Tätä varten sinun on löydettävä kaksi "porttia" yhdestä piiristä toiseen. "Porttien" ehto: ne eivät saa leikata toisiaan (ne eivät saa koskettaa edes päitä), ne eivät saa leikata ääriviivojen kanssa (kuva 5).

Kuva 5

Kuva 6
4) Seuraavaksi sinun tulee syöttää vuorotellen kaikki sisäiset sekvenssit jo muodostettuihin, toisistaan ​​erotettuihin (kohta 3) sekvensseihin. Sinun on yhdistettävä siihen, joka sisältää uuden. Määritelmän mukaan mikään sisäinen sekvenssi ei kosketa tai leikkaa muita (joko yksi ulkoinen tai kaikki mahdolliset sisäiset osat), joten kaikki menee sujuvasti.
Kun portit on löydetty (kuva 6), on helppo rakentaa uusia sekvenssejä ja ohittaa ne nykyisen algoritmin pisteillä 1 ja 2 (kuva 7).

Kuva 7

5) Neljännen vaiheen jälkeen meillä on luettelo kolmioista (kuva 8). Ikään kuin olisimme jo selviytyneet tehtävästä, mutta kuvasta on vielä tehtävä kaunis: tarkista Delaunayn ehdon täyttyminen (kuva 9).

Kuva 8

Kuva 9

6) Tulevaisuudessa kerron sinulle kuudennesta kohdasta. Se koostuu peräkkäisestä ajosta vastaanotettujen kolmioiden luettelon läpi pisteen nro 5 mukaan. Ensin merkitsemme kaikki kolmiot "likaisiksi". Jokaisessa syklissä tarkistamme Delaunayn ehdon jokaiselle kolmiolle. Jos ehto ei täyty, rakennamme uudelleen ja merkitsemme naapurit ja nykyisen kolmion "likaiseksi". Jos ehto täyttyy, merkitse se puhtaaksi. Algoritmin toteutuksessani jokaisella kolmiolla on linkki naapureihinsa. Tässä tapauksessa 6. piste toimii nopeimmin.

Lisää viidennestä vaiheesta

Nyt tietääkseni on kaksi mahdollista tapaa määrittää, täyttävätkö kolmiot Delaunayn ehdon vai eivät: 1) Tarkista vastakkaisten kulmien summa. Sen on oltava pienempi kuin 180. 2) Laske rajatun ympyrän keskipiste ja laske etäisyys 4. pisteeseen. Kaikki tietävät, että Delaunayn ehto täyttyy, jos piste on rajatun ympyrän ulkopuolella.

Laskentateho #1: 10 kerto-/jakooperaatiota ja 13 yhteen-/vähennysoperaatiota.
Laskentateho #2: 29 kerto-/jako- ja 24 yhteen-/vähennyslaskua.

Esimerkiksi kirjassa lasketun laskentatehon kannalta vaihtoehto numero 1 on kannattavampi. Ja hän tajusi sen, jos ei... (Kuva 10). Kuten kävi ilmi, tämän menetelmän "kuljettimelle" asettamisen jälkeen oli epävarmuutta. Tämä on vaihtoehto, kun itse kulma A on suurempi kuin 180 astetta. Sitä käsitellään kirjassa yhtenä erillisistä yksityisistä menetelmistä. Ja tämän myötä kaikki sen eleganssi, läpinäkyvyys ja suorituskyky katoavat. Ja myös myöhemmin kävi ilmi, että menetelmää nro 2 voidaan optimoida erittäin merkittävästi.

Kuva 10

Algoritmin optimointi Delaunayn ehdon tarkistamiseksi rajatun ympyrän yhtälön kautta

Seuraava on puhdasta matematiikkaa.

Meillä on siis:
Pisteen M(X, Y) ehdon tarkistaminen pisteiden A(x1, y1), B(x2, y2), C(x3, y3) läpi kulkevan ympyrän yhtälöllä voidaan kirjoittaa seuraavasti:

(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ merkki a ≥ 0

Yksityiskohdat löytyvät erinomaisesta kirjasta. (Ei, en ole kirjoittaja)
Eli merkki a on kulkusuunnan merkki, alusta asti rakensin kolmioita myötäpäivään, jotta se voidaan jättää pois (se on yhtä suuri kuin yksi).

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

D >= 0

Kuva 11

Eikö vain ole?

Kirjan mukaan taas

(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

Meillä on: 15 kerto-/jakooperaatiota ja 14 yhteen-/vähennysoperaatiota.

Kiitos huomiostasi. Odotan kritiikkiä.

Bibliografia

1. Skvortsov A.V. Delaunay-triangulaatio ja sen sovellus. - Tomsk: Publishing House Voi. un-ta, 2002. - 128 s. ISBN 5-7511-1501-5

Konstruoidun kolmion laadun kvantifioimiseksi määrittelemme kahdenlaisia ​​kriteerejä, topologiset ja geometriset.

Topologinen kriteeri perustuu joukon pisteen lähimpiin naapureihin. Ihannetapauksessa pisteellä on 6 naapuria 2D-alueelle ja 12 naapuria 3D-alueelle. Saamme topologisen arvion käyttämällä kaavaa (1), jossa on pisteiden kokonaismäärä alueella, on sisäiseen pisteeseen liittyvien naapuripisteiden aste tai lukumäärä.

Geometrinen kriteeri perustuu lasketun kolmioelementin ympärillä olevien piirrettyjen ja rajattujen ympyröiden väliseen eroon. Saamme geometrisen arvion käyttämällä kaavaa (2), jossa on kolmioiden lukumäärä, on piirretyn ympyrän säde, on rajatun ympyrän säde.

Algoritmit kolmioiden muodostamiseen

Kolmioiden muodostamiseen on olemassa suuri määrä algoritmeja. Ne eroavat toisistaan ​​työllisyyden, tietokoneella toteutuksen monimutkaisuuden ja rakentamisen lähestymistapojen suhteen. Voit oppia lisää algoritmeista kirjasta A.V. Skvortsova. Tarkastellaanpa joitain algoritmeja.

Yksi ensimmäisistä ehdotuksista ahne algoritmi kolmion rakentaminen. Delaunayn kolmiota kutsutaan ahneeksi, jos se on rakennettu ahneella algoritmilla. Ahneen algoritmin monimutkaisuus joidenkin sen parannusten kanssa on . Käytännössä niin suuren monimutkaisuuden vuoksi sitä ei käytetä melkein koskaan. Harkitse algoritmia askel askeleelta:

Vaihe 1. Luettelo kaikista mahdollisista lähdepisteiden pareja yhdistävistä viivasegmenteistä luodaan ja lajitellaan segmenttien pituuden mukaan.

Vaihe 2 Lyhyimmästä alkaen segmentit lisätään peräkkäin kolmioon. Jos segmentti ei leikkaa muiden aiemmin lisättyjen segmenttien kanssa, se lisätään, muuten se hylätään.

Huomaa, että jos kaikki mahdolliset segmentit ovat eripituisia, niin tämän algoritmin tulos on yksiselitteinen, muuten se riippuu samanpituisten segmenttien lisäysjärjestyksestä.

Iteratiivinen algoritmi perustuvat hyvin yksinkertaiseen ajatukseen pisteiden lisäämisestä peräkkäin osittain rakennettuun Delaunayn kolmioon. Tämän algoritmin monimutkaisuus koostuu kolmion löytämisen monimutkaisuudesta, johon seuraavassa vaiheessa lisätään piste, uusien kolmioiden rakentamisen monimutkaisuudesta sekä vastaavan kolmiorakenteen uudelleenrakentamisen monimutkaisuudesta epätyydyttävän tuloksena. tuloksena olevan kolmion vierekkäisten kolmioiden parien tarkistukset Delaunayn ehdolle. Harkitse algoritmia askel askeleelta:

Vaihe 1. Kolmelle ensimmäiselle aloituspisteelle rakennamme yhden kolmion.

Vaihe 2 Suorita kaikkien muiden kohtien silmukassa vaiheet 3-5.

Vaihe 3 Seuraava piste lisätään jo rakennettuun kolmiorakenteeseen seuraavasti. Ensinnäkin piste lokalisoidaan, ts. on olemassa (aiemmin rakennettu) kolmio, johon seuraava piste putoaa. Tai jos piste ei ole kolmion sisällä, kolmion reunalla on kolmio, joka on lähinnä seuraavaa pistettä.

Vaihe 4 Jos piste osuu aiemmin lisättyyn kolmiosolmuun, tällainen piste yleensä hylätään, muuten piste lisätään kolmioon uutena solmuna. Lisäksi, jos piste osuu johonkin reunaan, se jaetaan kahdeksi uudeksi, ja molemmat reunan vieressä olevat kolmiot jaetaan myös kahteen pienempään. Jos piste on tiukasti minkä tahansa kolmion sisällä, se jaetaan kolmeen uuteen. Jos piste on kolmion ulkopuolella, muodostetaan yksi tai useampi kolmio.

Vaihe 5 Hiljattain hankittujen kolmioiden Delaunayn ehdon mukaisuus tarkistetaan paikallisesti ja tarvittavat uudelleenjärjestelyt suoritetaan.

Uusia kolmioita rakennettaessa on mahdollista kaksi tilannetta, kun lisätty piste putoaa joko kolmion sisälle tai sen ulkopuolelle. Ensimmäisessä tapauksessa muodostetaan uudet kolmiot ja algoritmin suorittamien toimien määrä on kiinteä. Toisessa on tarpeen rakentaa ylimääräisiä kolmioita nykyisen kolmion ulkopuolelle, ja niiden lukumäärä voi olla pahimmassa tapauksessa yhtä suuri? 3. Algoritmin kaikille vaiheille ei kuitenkaan lisätä enempää kuin kolmioita, missä on alkupisteiden kokonaismäärä. Siksi molemmissa tapauksissa kolmioiden rakentamiseen käytetty kokonaisaika on.

Ketju algoritmi Yksi ensimmäisistä tehokkaista kolmiomittausalgoritmeista perustuu tasomaisen graafin regularisointimenettelyyn ja monotoniseen polygonikolmioon. Tämän algoritmin monimutkaisuus on, missä on alkusegmenttien lukumäärä. Harkitse algoritmia askel askeleelta:

Vaihe 1. Alkuperäisten rakenteellisten segmenttien joukosta muodostetaan yhdistetty tasograafi (kuva 4, a).

Vaihe 2 Kaavio on regularisoitu, ts. lisätään uusia reunoja, jotka eivät leikkaa muita niin, että jokainen graafin kärkipiste tulee vierekkäin vähintään yhden kärjen kanssa sen yläpuolella ja yhden sen alapuolella. Tasoitus tehdään kahdessa kierrossa pystysuoralla tasaisella pyyhkäisyllä. Ensimmäisessä ajossa alhaalta ylös löydämme peräkkäin kaikki kärjet, joista ei ole yhtään ylöspäin johtavaa reunaa. Esimerkiksi (Kuva 4, b) tämä on kärki B. Piirretään vaakaviiva, löydämme sen ylittämien AD- ja EF-graafien lähimmät reunat vasemmalta ja oikealta. Sitten etsitään DEHG-neliikulmion alin kärki ja vedetään siihen reuna B:stä. Vastaavasti toinen syöttö suoritetaan ylhäältä alas (Kuva 4, c). Tämän vaiheen seurauksena tasograafin jokaisesta alueesta tulee yksitoinen monikulmio.

Vaihe 3 Kukin kaavion alue on jaettava kolmioihin. Voit tehdä tämän käyttämällä kahden kolmion ei-kupera yhdistämisalgoritmia (kuva 4, d).

Kuva 4. Kolmiomittausketjualgoritmin toimintakaavio: a) - alkusegmentit; b - kulku alhaalta ylös graafin laillistamisen; c) - kulku ylhäältä alas; d) - monotonisten polygonien kolmiomittaus

Ketjualgoritmin toteuttamiseksi on parasta käyttää tietorakenteita, joissa reunat on esitetty eksplisiittisesti, kuten "Kaksoisreunat" tai "Solmut, reunat ja kolmiot".

Ketjualgoritmin haittana on, että mitään ei voida sanoa etukäteen tuloksena olevan kolmion muodosta. Tämä ei ole optimaalinen kolmio, ei ahne eikä rajoitettu Delaunayn kolmio. Ketjualgoritmi voi tuottaa hyvin pitkiä pitkänomaisia ​​kolmioita.

Tuloksena olevan kolmion laadun parantamiseksi voidaan tarkastaa kaikkien vierekkäisten kolmioiden parien, joita ei ole erotettu rakenteellisella reunalla, Delaunayn ehdon täyttyminen ja tarvittaessa rakentaa uudelleen. Tuloksena saadaan Delaunay-kolmio rajoituksin.

GRID-mallit ovat malleja tavallisista soluista.

Olkoon koordinaattijärjestelmä
ja ja
. Käyttäjäsarjat
ja näytteenottovaiheet
.

,

- pisteen fyysiset koordinaatit.

Laskea
ja
,
- bittiverkko.

- kvantisoidut arvot. Todellinen:

- algoritmiparametri - pisteiden määrä, - paino. Mitä lähempänä piste, sitä suurempi paino.

- etäisyysaste (1 tai 2).

Normalisointikerroin:

Miten lähempänä 1:tä, painotetut pisteet otetaan huomioon.

Tämä on IDW-menetelmä - pitkä, jokaiselle t:lle on löydettävä naapureita. Joukko naapureita löytyy tehokkaasti - lähin. Jokainen piste tuottaa tietyn korkeuden "tapin". Paljon riippuu pisteen asettelun epäsäännöllisyydestä, tämän he pitävät
tai
nuo. jakaa sektoreihin ja rakentaa pisteen läheisyyteen.

Etu– yksinkertaisuus

Virhe:

------Lippu 14. Tina-malli. Delaunayn kolmiomittausalgoritmit ------

1) Kolmio (tina).

Triangulaatio– funktion rakentaminen paloittain lineaarisen funktion joukon muodossa

Triangulaatio– interpolointi kuperan alueen sisällä.

Triangulaatio on tasograafi, jonka kaikki sisäreunat ovat kolmioita; tapa esittää tilaa kolmioiden muodossa, jotka ovat vierekkäin ilman päällekkäisyyttä. Kolmiomittaus rakentuu pistejoukolle useilla tavoilla.

Tarvitsemme algoritmin rakentaaksemme optimaalisen kolmion.

Kone, joka kulkee 3 pisteen läpi.

1) Etsi kolmio, joka
;

2)
- Rakennamme tason yhtälön.

Tarkistaaksesi, ovatko pisteet kolmion sisällä vai eivät, sinun on korvattava arvo viivojen yhtälöllä - kolmion reunat. Jos kaikki 3 yhtälöä > 0, niin sisällä.

Näytä rakenne:

Jokainen kolmio sisältää saman määrän kolmioita.

, missä on sisäisten pisteiden määrä,
- pisteiden määrä.

Ahne kolmio.

Yhdistämme kaikki pisteet reunoilla, valitsemme minimin, lisäämme kolmioon. Seuraavaksi otamme seuraavan minimin, joka ei leikkaa edellisiä, ja niin edelleen. Tuloksena on ahne kolmio.

Delaunayn kolmio.

Muiden kolmioiden pisteet eivät putoa minkään kolmion ympärille rajatun ympyrän sisään. Rakennettu yhdellä tavalla.

Flip on reunojen kääntö. Sen avulla voit vaihtaa perinteisestä kolmiomittauksesta Delaunay-triangulaatioon. Jos haluat tarkistaa, kuuluuko piste ympyrään: korvaa jos< R, то внутри.

Delaunay kunto.

Kolmen pisteen läpi kulkevan ympyrän yhtälö:

Jos pienempi kuin nolla, niin ulkoinen, muuten - sisäinen.

on Delaunayn tila.

Algoritmi Delaunayn kolmioiden muodostamiseksi:

1) Tutkittavana lisäpisteiden lisääminen on yksinkertainen iteratiivinen algoritmi:

On setti
Lisää kolmioon, rakentaminen suoritetaan
kolmion osio
jälleenrakentaminen. Nollavaiheessa lisäämme 3-4 kuvitteellista pistettä, jotka ilmeisesti peittävät kirjekuoremme, kaikki pisteet ovat sisällä. Kun olemme heittäneet pisteen, katso, mihin kolmioon se osui, jaa se kolmeen, tarkistamme jokaisen kolmion Delaunayn ehdon ja käännät reunat. Keskimäärin uusintoja on kolme.

Teoreettinen monimutkaisuus

2) Kiihdytysmenetelmät. Perustuu tilastollisesti riippuviin pisteisiin. Siemenkolmio on kolmio, johon edellinen piste putosi. Sitten yhdistämme kaksi pistettä - edellinen ja uusi.

Siirrymme ensimmäisestä pisteestä toiseen.

(Algoritmien kehittäminen ja käyttöönotto rajoitetun tilavuuden kolmiomittauksille: iteratiiviset algoritmit
Preprint, Inst. Appl. Math., Venäjän tiedeakatemia)

Galanin M.P., Shcheglov I.A.
(M.P.Galanin, I.A.Sheglov)

IPM niitä. M.V. Keldysh RAS

Moskova, 2006
Tätä työtä tuki Venäjän perustutkimussäätiö (projekti nro 06-01-00421)

huomautus

Tarkastellaan iteratiivisia menetelmiä tilaalueiden kolmiulotteiseen diskretisoimiseen (tetraedrisilmien rakentamiseen): rajakorjausmenetelmät, Delaunayn kriteeriin perustuvat menetelmät ja tyhjennysmenetelmät. Jokaiselle näistä menetelmistä on annettu algoritmien muunnelmia. Käsitellään monimutkaisten alueiden verkkojen rakentamisen ominaisuuksia.

Abstrakti

Kuvataan kolme pääperhettä iteratiivisia algoritmeja vapaalle ja rajoitetulle yksinkertaiselle tilavuuskolmioinnille: rajakorjaus (mukaan lukien "oktreen" algoritmi), Delaunay-pohjaiset menetelmät ja etenevä etulähestymistapa. Jokaiselle menetelmätyypille annetaan esimerkkialgoritmi.

1. Johdanto 3

2. Rajakorjausmenetelmät4

2.1 Primääriverkon rakentaminen4

2.2 Ensisijaisen ruudukon korjaus6

3. Delaunayn kriteeriin perustuvat menetelmät9

3.1 Delaunayn kolmiomittauksen rakentaminen tietylle pistejoukolle 12

3.2. Delaunayn kolmio rajoituksin17

3.3 Algoritmien teknisen toteutuksen ominaisuudet perustuvat
Delaunayn kriteeri 22

4. Tyhjennysmenetelmät23

4.1 Esimerkki sammutusalgoritmista26

Referenssit 3 0

1. Esittely

Kolmiomittausmenetelmien kahdesta luokasta - suorasta ja iteratiivisesta - jälkimmäiset ovat riittävän yleismaailmallisia, ja siksi, toisin kuin suorat, niitä voidaan käyttää melko mielivaltaisen muodon alueiden kolmioimiseen. Tämän monipuolisuuden kustannuksella on huomattavasti suurempi resurssien kulutus ja menetelmän työvoimavaltaisempi toteutus tietyssä algoritmissa.

Tällä hetkellä on kehitetty suuri määrä ohjelmistopaketteja, jotka perustuvat johonkin iteratiiviseen menetelmään, joka toteuttaa grid-rakentamisen (osittain tai kokonaan) automaattitilassa. Pohjimmiltaan nämä paketit ovat kaupallisia, mikä on varsin perusteltua, kun otetaan huomioon niiden luomiseen käytetty vaiva, koska kolmiulotteisessa tilassa on useita epämiellyttäviä ominaisuuksia, jotka vaikeuttavat merkittävästi kehittäjän elämää.

Iteratiivisilla menetelmillä rakennetut verkot ovat yleensä rakenteettomia ja epähomogeenisia. Strukturoimattomuus johtuu siitä, että ruudukon topologia muodostuu rakentamisen yhteydessä, ja siksi se voi luonnollisesti vaihdella jopa saman alialueen sisällä. Samasta syystä homogeenisuus, jos se voi syntyä, on vain sattumaa.

Koska sen tulevasta rakenteesta ei voida sanoa mitään ennen verkon rakentamista, ei myöskään sen laatua voida taata. Usein rakennettua verkkoa voidaan parantaa merkittävästi käyttämällä yhtä monista optimointitekniikoista. Tätä mahdollisuutta ei yleensä laiminlyödä, koska optimointiin käytetty aika on yleensä huomattavasti vähemmän kuin rakentamiseen käytetty aika.

Tämän työn tarkoituksena on tarkastella ja luokitella olemassa olevia menetelmiä tetraedrisilmien rakentamiseksi kolmiulotteisissa domeeneissa. Huomattavan tietomäärän vuoksi jäljempänä tarkastellaan vain niin kutsuttuja "iteratiivisia menetelmiä". Suorat menetelmät kuvataan kohdassa .

Tätä työtä tuki osittain Venäjän perustutkimussäätiö (projekti nro 06-01-00421).

Riisi. 11. Dodekaedrin ja ikosaedrin liittoa edustavan alueen kolmio (Delaunay-triangulaatio rajoituksin)

Tällä menetelmällä konstruoitujen verkkojen laatu on keskitasoa (rajojen lähellä olevat tetraedrit voivat olla erittäin huonon muotoisia), joten johonkin optimointimenetelmistä yleensä turvaudutaan lisäksi.

B. Joen teoksissa on ehdotettu muita algoritmin muunnelmia, jotka eivät käytä lisäpisteitä ja perustuvat täysin paikallisiin muunnoksiin, jotka ovat samankaltaisia ​​kuin "kauppa".

4) tetraedrin tilavuus ei ole suurempi kuin suurin sallittu ().

Kaikista tetraedreistä () valitaan laadultaan paras tetraedri ja siirrytään vaiheeseen 5; jos ei ole tetraedreita, jotka täyttävät osoitetut olosuhteet, siirrytään vaiheeseen 4.

4. Vielä ehtymättömän alueen sisällä on sellainen kohta, että:

1) tetraedri () täyttää kaikki 3 kohdan ehdot;

2) pallossa ei ole etäpistettäF(tämä estää solmun sijoittamisenp liian lähellä olemassa olevien tetraedrien kasvoja ja pisteitä).

Solmun hakualgoritmin muunnelmapkäsitellään alla.

5. Poista kaikki kärjetF, putoaa muodostuneen tetraedrin sisään (ja rajojen päälle). Sitten etuosa päivitetään seuraavan kaavion mukaisesti: muodostetun tetraedrin jokainen pinta otetaan huomioon ja

1) jos kasvot ovat etupuoli, se poistetaan edestä;

2) jos kasvot EIVÄT ole etupuoli, se lisätään etupuolelle.

6. Jos poistamattomia pisteitä on vielä jäljelläFtai (joka vastaa) etuosa ei ole tyhjä (eli alue ei ole vielä täysin käytetty), siirtyminen vaiheeseen 1 suoritetaan, muuten prosessi on ohi.

Joten joukkoFkäytetään useaan tarkoitukseen kerralla: avaruuskulman arvon arvioimiseen, rakenteen oikeellisuuden valvontaan ja uusien solmujen sijoittelun ohjaamiseen. Myös joukkoFhyödyllinen edistymisen osoittamisessa. Algoritmin toiminnan aikana poistettujen pisteiden lukumäärän suhdeFolemassa olevien pisteiden alkuperäiseen määräänFitse asiassa näyttää kuinka suuri osa alueesta on jo loppuun käytetty.

Palataan kysymykseen uuden solmun koordinaattien löytämisestä tetraedrin rakentamista varten (kuvatun algoritmin kohta 4). Olkoon kolme solmua - annettu.

1. Ensimmäisessä vaiheessa löydämme - kolmion massakeskipisteen (sen solmujen koordinaattien aritmeettisena keskiarvona) ja kasvon tasoon nähden normaalin yksikön (normalisoidun vektoritulon kautta).

2. Seuraavaksi määritetään ensimmäinen approksimaatio etäisyydelle haluttuun pisteeseenp (H), tetraedrin enimmäistilavuuden perusteella: . Huomaa, että kasvojen alueStosiasiallisesti löydetty edellisessä vaiheessa (kahden reunan ristitulon tulos on kaksinkertainen kasvojen pinta-alaan), ja suurin tilavuus määräytyy ohjausfunktion arvon mukaan.

3. Kohta tarkistetaan. Jos tetraedri () täyttää kaikki vaatimukset, siirry vaiheeseen 6, muussa tapauksessa siirry vaiheeseen 4.

4. Kohta tarkistetaan. Jos tetraedri () täyttää kaikki vaatimukset, siirry vaiheeseen 6, muussa tapauksessa siirry vaiheeseen 5.

5. Usko ja siirry vaiheeseen 3.

6. Haluttu solmu löytyy.

Huomaa, että 99 %:ssa tapauksista haluttu piste sijaitsee 1 tai 2 tämän algoritmin iteraatiossa.

Yllä kuvatussa tyhjennysalgoritmissa yksi tetraedri poistetaan alueelta kussakin vaiheessa. NASAn työntekijä Sh. Pirzade ( Shahyar Pirzadeh ) ehdotti algoritmista toista versiota, jossa alueelta poistetaan kerralla kokonainen kerros tetraedria (eli jokaisessa iteraatiossa tetraedrit rakennetaan välittömästi nykyisen rintaman kaikille pinnoille) . Vastoin odotuksia tämä variantti ei merkittävästi nopeutta rakennusprosessia (koska kaikkien uusien tetraedrien oikeellisuus on vielä tarkistettava), mutta se eliminoi tarpeen etsiä sopivinta pintaa tetraedrin rakentamiseen. Tämä on kuitenkin pikemminkin miinus kuin plussa, koska tämän ominaisuuden ansiosta Pirzade-versio on vähemmän luotettava ja voi epäonnistua geometrisesti monimutkaisilla alueilla. Samalla se näyttää hyviä tuloksia suhteellisen yksinkertaisilla alueilla.

Ummetusmenetelmillä rakennetuilla verkoilla on pääsääntöisesti hyvä laatu, ja myöhempi solmujen sijainnin optimointi lisää laatua. Yhteenvetona voidaan todeta, että tyhjennysmenetelmät ovat tehokkaimpia, jos alueen rajan kolmio asetetaan alun perin. Tämä on niiden tärkein ero Delaunayn kriteeriin perustuviin menetelmiin, joiden kohdalla tilanne on suoraan päinvastainen.

Bibliografia

1. Shaydurov V.V. Multigrid Finite Element Methods. - M., Nauka, 1989. - 288s.

2. Skvortsov A.V. Yleiskatsaus Delaunayn kolmiomittauksen muodostamisalgoritmeihin // , 2002, №3, c. 14-39.

3. Skvortsov A.V. Algoritmit kolmioiden muodostamiseen rajoituksin // Laskennalliset menetelmät ja ohjelmointi, 2002, №3, c. 82-92.

4. I.Babushka, W.C. Rheinboldt. A-posteriori -virhearviot äärelliselementtimenetelmälle // Int. J. Numer. Meth. Eng., Voi. 12, s. p. 1597-1615, 1978.

5. T.J. Leipuri. Automaattinen verkon luominen monimutkaisille kolmiulotteisille alueille, joissa käytetään rajoitettua Delaunayn kolmiota // Suunnittelu tietokoneiden kanssa, Springer-Verlag, nro 5, s. s. 161-175, 1989.

6. M. Bern, D. Eppstein. Verkkojen luominen ja optimaalinen kolmio // Laskenta euklidisessa geometriassa, World Scientific Publishing Co., p.s. 23-90, 1995.

7. D.K. Blandford, G. Blelloch, D. Cardoze, C. Kadow. Kompaktit esitykset yksinkertaisista verkoista kahdessa ja kolmessa ulottuvuudessa // 12. kansainvälisen meshing-pyöreän pöydän julkaisut, Sandia National Laboratories, s. 135-146, syyskuu. 2003.

8. H. Borouchaki, S.H. Lo. Nopea Delaunayn kolmio kolmiulotteinen // Tietokonemenetelmät sovelletussa mekaniikassa ja tekniikassa, Elsevier, Voi. 128, s. s. 153-167, 1995.

9. E.K. Buratynski. Kolmiulotteinen rakenteeton verkkogeneraattori mielivaltaisia ​​sisäisiä rajoja varten // Numeerisen ruudukon luominen laskennallisessa virtausmekaniikassa, Pineridge Press, p.p. 621-631, 1988.

10. PR. Cavalcanti, U.T. Mello. Kolmiulotteinen rajoitettu Delaunay-kolmio: minimalistinen lähestymistapa // 8. kansainvälisen meshing-pyöreän pöydän julkaisut, p.p. 119-129, 1999.

11. Dey, K. Tamal, K. Sugihara, C.L. Bajaj. Delaunayn kolmiomittaukset kolmessa ulottuvuudessa äärellisellä tarkkuudella // Tietokoneavusteinen geometrinen suunnittelu, North-Holland, nro 9, s. s. 457-470, 1992.

12. H N. Djidjev. Voimaohjatut menetelmät rakenteellisten kolmio- ja tetraedriverkkojen tasoittamiseksi // 9. kansainvälisen meshing-pyöreän pöydän julkaisut, Sandia National Laboratories, p.p. 395-406, lokakuu 2000.

13. L. Durbeck. Haihdutus: tekniikka verkon laadun visualisoimiseksi // 8. kansainvälisen meshing-pyöreän pöydän julkaisut, South Lake Tahoe, CA, U.S.A., p.p. 259-265, lokakuu 1999.

14. D.A. ala. Laplacian tasoitus ja Delaunayn kolmiot // , voi. 4, p.p. 709-712, 1988.

15. P.J. Frey, H. Borouchaki, P.-L. George. Delaunayn tetrahedraalisointi etenevällä lähestymistavalla // Proceedings 5th International Meshing Roundtable, Sandia National Laboratories, p.p. 31-46, lokakuuta 1996.

16. LA. Freitag, C. Ollivier-Gooch. Tetrahedral Mesh -parannustekniikoiden vertailu // Proceedings 5th International Meshing Roundtable, Sandia National Laboratories, p.p. 87-106, lokakuu 1996.

17. LA. Freitag, C. Ollivier-Gooch. Tetrahedral Mesh Improvement using Swapping and Smoothing // , voi. 40, s. s. 3979-4002, 1995.

18. LA. Freitag, C. Ollivier-Gooch. Verkon laadun vaikutus ratkaisun tehokkuuteen // 6. kansainvälisen meshing-pyöreän pöydän julkaisut, Sandia National Laboratories, s. 249, lokakuu 1997.

19. P.L. George. TET MESHING: Rakentaminen, optimointi ja mukauttaminen // Käsittely 8Kansainvälinen mesh pyöreä pöytä s. 133-141, 1999.

20. N.A. Golias, T.D. Tsiboukis. Lähestymistapa kolmiulotteisten tetraedrisilmien jalostukseen Delaunayn muunnoksiin // , John Wiley, nro 37, s. 793-812, 1994.

21. C. Hazlewood. Rajoitettujen tetrahedraalisaatioiden arvioiminen // Tietokoneavusteinen geometrinen suunnittelu, voi. 10, s. p. 67–87, 1993.

22. B. Joe. Delaunayn kolmiomaiset verkot kuperissa polygoneissa, SIAM J Sei. stat. Comput., Voi. 7, p.p. 514-539, 1986.

23. B. Joe. Kolmiulotteisten Delaunay-kolmioiden rakentaminen paikallisten muunnosten avulla // Tietokoneavusteinen geometrinen suunnittelu, Voi. 8, s. p. 123-142, 1991.

24. B. Joe. Kolmiulotteisten, paranneltujen kolmioiden rakentaminen paikallisia muunnoksia käyttämällä // Siam J. Sc. Comput., voi. 16, s. p. 1292-1307, 1995.

25. R.W. Lewis, Yao Zheng, D.T. Gethin. Kolmiulotteisen rakenteettoman verkon luominen: Osa 3. Tilavuusverkot // Tietokonemenetelmät sovelletussa mekaniikassa ja tekniikassa, Elsevier, osa 134, s. 285-310, 1996.

26. A. Liu, B. Joe. Tetrahedran muodosta puolittamisesta // Laskennan matematiikka, voi. 63, nro 207, 141–154, 1994.

27. S.H. Lo. Volyymin diskretisointi Tetrahedra-I:ksi. Rajapintojen tarkastus ja suuntaus // Tietokoneet ja rakenteet, Pergamon Press, voi. 39, nro 5, s. s. 493-500, 1991.

28. S.H. Lo. Volyymin diskretisointi tetrahedraksi - II. 3D-kolmiointi etenevällä lähestymistavalla // Tietokoneet ja rakenteet, Pergamon, Voi. 39, nro 5, s. s. 501-511, 1991.

29. R. Lohner. Kolmiulotteisten rakenteellisten verkkojen luominen etenevällä rintamalla // AIAA:n 26. ilmailu- ja avaruustieteen kokouksen aineisto, Reno, Nevada, 1988.

30. S.J. Owen. Survey of Unstructured Mesh Generation Technology // 7. kansainvälisen meshing-pyöreän pöydän julkaisut, p.p. 239-269, Dearborn, MI, 1998.

31. V.N. Parthasarathy, C.M. Graichen, A.F. Hathaway. Tetrahedronin laatumittausten vertailu // Äärelliset elementit analyysissä ja suunnittelussa, Elsevier, ei. 15, s. p. 255-261, 1993.

32. S. Pirzadeh. Strukturoimattoman viskoosin ruudukon luominen etenevien kerrosten menetelmällä // AIAA-93-3453-CP, AIAA, p.p. 420-434, 1993.

33. V.T. Rajan. Delaunayn kolmion optimaalisuus // Proc. 7. ACM Symp. Comp. geometria, p.p. 357-363, 1991.

34. A. Rassineux. Tetrahedraalisten verkkojen luominen ja optimointi etureunatekniikalla // International Journal for Numerical Methods in Engineering, Wiley, voi. 41, s. s. 651-674, 1998.

35. S. Rebay. Tehokas rakenteettoman verkon luominen Delaunayn kolmiomittauksen ja Bowyer-Watson-algoritmin avulla // Journal of Computational Physics, voi. 106, s. s. 125-138, 1993.

36. M.-C. Rivara. Selektiiviset tarkennus-/tarkennusalgoritmit sisäkkäisten kolmioiden sekvensseille // International Journal for Numerical Methods in Engineering, nro 28, s. s. 2889-2906, 1998.

37. M.-C. Rivara, C. Levin. 3D-jalostusalgoritmi, joka sopii mukautuviin ja moniverkkotekniikoihin // Viestintä sovelletuissa numeerisissa menetelmissä, nro 8, s. s. 281-290, 1998.

38. J. Ruppert. Delaunayn tarkennusalgoritmi laadukkaaseen 2-ulotteisen verkon luomiseen // Journal of Algorithms, nro 18, s. s. 548-585, 1995.

39. NEITI. Shepherd, M.K. Georges. Kolmiulotteisen verkon luominen Finite Octree -tekniikalla // International Journal for Numerical Methods in Engineering, voi. 32, s. s. 709-749, 1991.

40. NEITI. Shephard, F. Guerinoni, J.E. Flaherty, R.A. Ludwig, P.L. Baehmann. Rajallisen oktreen verkon luominen automatisoituun adaptiiviseen 3D-virtausanalyysiin // Numeerisen ruudukon generointi laskennallisessa nestemekaniikassa Miami, 1988

41. K. Shimada, D.C. Gossard. Bubble Mesh: automatisoitu kolmiomaisen ei-jakogeometrian yhdistäminen pallopakkauksella // Asian käsittely Kolmas symposium kiinteiden mallintamisesta ja sovelluksista , p.p. 409-419, 1995.

42. K. Shimada, A. Yamada, T. Itoh. Parametristen pintojen anisotrooppinen kolmiomainen sidos ellipsoidisten kuplien tiiviin pakkauksen kautta // 6. kansainvälisen meshing-pyöreän pöydän julkaisut, p.p. 375-390, 1997.

43. D.F. Watson. Delaunayn tessellaation laskeminen Voronoin polytooppeihin sovellettaessa // Tietokonepäiväkirja, Voi. 24(2), s. s. 167-172, 1981.

44. M.A. Yerry, M.S. Paimen. Kolmiulotteisen verkon luominen modifioidulla Octree-tekniikalla // International Journal for Numerical Methods in Engineering, Voi. 20, s. p. 1965-1990, 1984.

45. Galanin M.P., Shcheglov I.A. Algoritmien kehittäminen ja toteutus monimutkaisten spatiaalisten alueiden kolmiulotteiseen kolmiomittaukseen: suorat menetelmät. IPM preprint im. M.V. Keldysh RAN, 2006, painossa. pisteet, ts. Steiner-solmut - lisäsolmuja, jotka eivät sisältyneet alkuperäiseen sarjaan

Saattaa vaikuttaa siltä, ​​että ehto 2 seuraa ehdosta 3, mutta todellisuudessa se ei ole. Esimerkiksi olemassa oleva tetraedri voi olla kokonaan sisällätestattu tetraedri.