Pag-optimize ng algorithm para sa pagsuri sa kondisyon ng Delaunay sa pamamagitan ng equation ng circumscribed na bilog at ang aplikasyon nito
- Pagproseso ng imahe,
- Programming
Sasabihin ko sa iyo ang sikreto kung paano mabilis na suriin ang kondisyon ng Delaunay para sa dalawang tatsulok.
Sa totoo lang, ang pag-optimize mismo ay inilarawan nang mas mababa ng kaunti (tingnan ang "Pag-optimize ng algorithm para sa pagsuri sa kondisyon ng Delaunay sa pamamagitan ng equation ng circumscribed circle"), ngunit sasabihin ko sa iyo ang tungkol sa lahat ng bagay sa pagkakasunud-sunod.
Sa aking kaso, ginagamit ang triangulation sa pagsubaybay sa imahe upang hatiin ang eroplano sa mga primitive na sektor (mga tatsulok). Tulad ng alam mo, nahahati din ito sa ilang mga yugto: pagsasaayos, pagtuklas ng mga hangganan, pag-bypass ng mga hangganan, pagwawalis ng mga contour. Ito ay sa pinaka-pangkalahatang paraan. Gusto kong huminto, sa palagay ko, sa pinakamahirap na yugto: pagwawalis ng eroplano.
Sa pasukan
Pagkatapos ng pag-detect at pag-bypass sa mga hangganan sa output, nakakuha ako ng maraming mga panlabas na contour. Ang bawat nakakaantig na tabas ay may iba't ibang kulay. Ang bawat naturang contour ay naglalaman din ng isang kilalang bilang ng mga panloob na contour.Kaya, mula sa punto ng view ng "pagwawalis ng eroplano", kung isasaalang-alang namin ang mga panlabas na contour nang hiwalay, mayroon kaming isang hanay ng mga punto, bawat isa ay may isang kapitbahay sa kanan at kaliwa. Yung. ang lahat ng mga punto ay sarado sa kadena, walang isang "nakabitin" na punto, at ang bawat isa sa mga kadena ay naglalaman ng hindi bababa sa 3 puntos (Larawan 1).
Larawan 1
Ano ang kailangang gawin
Kinakailangan na walisin ang figure na may mga tatsulok.Maghanap
Matapos basahin ang libro, wala akong nakitang isang (kahit isa) na paraan ng pagbuo ng Delaunay triangulation na medyo angkop para sa aking kaso. Hindi na ako naghanap ng ibang libro. Oo, at ito ay sapat na, inayos niya ang mga iniisip ng aking ulo. Dahil dito, naimbento niya ang sarili niyang "bisikleta".Algorithm
1) Ipagpalagay, bilang panimula, na mayroon lamang isang sequence sa figure na isinasaalang-alang. Pagkatapos ang lahat ay bumaba sa sunud-sunod na pagkuha ng mga tatsulok. Kumuha kami ng anumang punto at subukang bumuo ng isang tatsulok na may mga kalapit na punto. Kung hindi posible na bumuo ng isang tatsulok (ang linya na nagkokonekta sa dalawang puntong ito ay bumalandra sa mga naitayo na o ang linya ay pumasa sa exclusion zone (Figure 2), lumipat tayo sa kalapit na punto, sabihin natin sa kanan. Kapag ang susunod Ang tatsulok ay natagpuan, idinagdag namin ito sa listahan (Larawan 3), at ang punto kung saan ito itinayo ay tinanggal (Larawan 4).
Figure 2
Larawan 3
Larawan 4
Isa pang bagay: kapag nagse-save ng susunod na tatsulok, kinakailangang i-record ang mga vertex sa isang clockwise bypass (sa tamang coordinate system). Magiging kapaki-pakinabang ito sa hinaharap upang mabawasan ang mga mapagkukunan ng computing.
2) Ulitin ang hakbang 1 hanggang sa walisin natin ang buong eroplano.
3) Kung mayroong ilang mga sequence, i.e. isa, at sa loob nito ay isa o higit pang mga panloob na contour (Figure 1). Narito ito ay kinakailangan upang isaalang-alang ang bawat pagkakasunod-sunod nang hiwalay. Kumuha tayo ng isa pang panloob na tabas. Mula sa isang panlabas at isang panloob ay gagawa kami ng dalawang solong contour. Upang gawin ito, kailangan mong makahanap ng dalawang "ports" mula sa isang circuit patungo sa isa pa. Ang kondisyon para sa "mga port": hindi sila dapat mag-intersect sa isa't isa (hindi nila dapat hawakan kahit na ang mga dulo), hindi sila dapat mag-intersect sa mga linya ng contour (Larawan 5).
Larawan 5
Larawan 6
4)
Susunod, dapat mong ipasok ang lahat ng mga panloob na pagkakasunud-sunod sa nabuo na, na hiwalay sa bawat isa (punto 3) na mga pagkakasunud-sunod. Kailangan mong pagsamahin ang isa na naglalaman ng bago. Sa pamamagitan ng kahulugan, walang panloob na pagkakasunud-sunod ang dumadampi o nagsa-intersect sa iba (maaaring isang panlabas o lahat ng posibleng panloob), kaya magiging maayos ang lahat.
Ang pagkakaroon ng natagpuan ang mga port (Larawan 6), madaling bumuo ng mga bagong pagkakasunud-sunod at i-bypass ang mga ito gamit ang mga puntos 1 at 2 ng kasalukuyang algorithm (Larawan 7). 
Larawan 7
5)
Pagkatapos ng ika-4 na yugto, mayroon kaming isang listahan ng mga tatsulok (Larawan 8). Na parang nakayanan na natin ang gawain, ngunit nananatili itong gawing maganda ang larawan: suriin ang katuparan ng kondisyon ng Delaunay (Larawan 9). 
Larawan 8
Larawan 9
6) Sa hinaharap, sasabihin ko sa iyo ang tungkol sa ikaanim na punto. Binubuo ito sa isang sunud-sunod na pagtakbo sa listahan ng mga natanggap na tatsulok ayon sa punto No. 5. Una, minarkahan namin ang lahat ng mga tatsulok bilang "marumi". Sa bawat cycle, sinusuri namin ang kondisyon ng Delaunay para sa bawat tatsulok. Kung ang kundisyon ay hindi natutugunan, pagkatapos ay itatayo namin at markahan ang mga kapitbahay at ang kasalukuyang tatsulok bilang "marumi". Kung ang kundisyon ay natugunan, pagkatapos ay markahan itong malinis. Sa aking pagpapatupad ng algorithm, ang bawat tatsulok ay may link sa mga kapitbahay nito. Sa kasong ito, ang ika-6 na punto ay gumagana ang pinakamabilis.
Higit pa tungkol sa ikalimang yugto
Ngayon, sa pagkakaalam ko, may dalawang posibleng paraan upang matukoy kung ang mga tatsulok ay nakakatugon sa kondisyon ng Delaunay o hindi: 1) Suriin ang kabuuan ng magkasalungat na mga anggulo. Ito ay dapat na mas mababa sa 180. 2) Kalkulahin ang gitna ng circumscribed na bilog at kalkulahin ang distansya sa ika-4 na punto. Alam ng lahat na ang kondisyon ng Delaunay ay nasiyahan kung ang punto ay nasa labas ng circumscribed circle.Computing power #1: 10 multiplication/dividing operations at 13 karagdagan/subtraction operations.
Computing power #2: 29 multiplications/divisions at 24 additions/subtractions.
Mula sa punto ng view ng computing power, na kung saan ay kinakalkula, halimbawa, sa libro, ang opsyon na numero 1 ay mas kumikita. At napagtanto niya ito, kung hindi para sa ... (Figure 10). Tulad ng nangyari, pagkatapos ilagay ang pamamaraang ito sa "conveyor", nagkaroon ng kawalan ng katiyakan. Isa itong opsyon kapag ang angle A mismo ay mas malaki sa 180 degrees. Ito ay itinuturing sa aklat bilang isa sa mga hiwalay na pribadong pamamaraan. At kasama nito, nawawala ang lahat ng kagandahan, transparency at performance nito. At sa kalaunan ay napag-alaman na ang paraan No. 2 ay maaaring lubos na ma-optimize.
Larawan 10
Pag-optimize ng algorithm para sa pagsuri sa kondisyon ng Delaunay sa pamamagitan ng equation ng circumscribed na bilog
Ang sumusunod ay purong matematika.Kaya mayroon kaming:
Ang pagsuri sa kondisyon para sa puntong M(X, Y) sa pamamagitan ng equation ng isang bilog na dumadaan sa mga puntos na A(x1, y1), B(x2, y2), C(x3, y3) ay maaaring isulat bilang:
(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ lagdaan ang ≥ 0
Ang mga detalye ay matatagpuan sa mahusay na aklat. (Hindi, hindi ako ang may-akda)
Kaya, ang sign a ay ang tanda ng direksyon ng traversal, sa simula pa lang ay nagtayo ako ng mga triangles clockwise, upang ito ay maalis (ito ay katumbas ng isa).
A(x1 - X, y1 - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);
D >= 0 
Larawan 11
Di ba?
Ayon sa libro, muli,
(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
Mayroon kaming: 15 multiplication/division operations at 14 addition/subtraction operations.
Salamat sa iyong atensyon. Naghihintay ako ng kritisismo.
Bibliograpiya
1. Skvortsov A.V. Delaunay triangulation at ang aplikasyon nito. - Tomsk: Publishing House Vol. un-ta, 2002. - 128 p. ISBN 5-7511-1501-5 Agosto 20, 2012 sa 10:41 pmPag-optimize ng algorithm para sa pagsuri sa kondisyon ng Delaunay sa pamamagitan ng equation ng circumscribed na bilog at ang aplikasyon nito
Sasabihin ko sa iyo ang sikreto kung paano mabilis na suriin ang kondisyon ng Delaunay para sa dalawang tatsulok.
Sa totoo lang, ang pag-optimize mismo ay inilarawan nang mas mababa ng kaunti (tingnan ang "Pag-optimize ng algorithm para sa pagsuri sa kondisyon ng Delaunay sa pamamagitan ng equation ng circumscribed circle"), ngunit sasabihin ko sa iyo ang tungkol sa lahat ng bagay sa pagkakasunud-sunod.
Sa aking kaso, ginagamit ang triangulation sa pagsubaybay sa imahe upang hatiin ang eroplano sa mga primitive na sektor (mga tatsulok). Tulad ng alam mo, nahahati din ito sa ilang mga yugto: pagsasaayos, pagtuklas ng mga hangganan, pag-bypass ng mga hangganan, pagwawalis ng mga contour. Ito ay sa pinaka-pangkalahatang paraan. Gusto kong huminto, sa palagay ko, sa pinakamahirap na yugto: pagwawalis ng eroplano.
Sa pasukan
Pagkatapos ng pag-detect at pag-bypass sa mga hangganan sa output, nakakuha ako ng maraming mga panlabas na contour. Ang bawat nakakaantig na tabas ay may iba't ibang kulay. Ang bawat naturang contour ay naglalaman din ng isang kilalang bilang ng mga panloob na contour.Kaya, mula sa punto ng view ng "pagwawalis ng eroplano", kung isasaalang-alang namin ang mga panlabas na contour nang hiwalay, mayroon kaming isang hanay ng mga punto, bawat isa ay may isang kapitbahay sa kanan at kaliwa. Yung. ang lahat ng mga punto ay sarado sa kadena, walang isang "nakabitin" na punto, at ang bawat isa sa mga kadena ay naglalaman ng hindi bababa sa 3 puntos (Larawan 1).
Larawan 1
Ano ang kailangang gawin
Kinakailangan na walisin ang figure na may mga tatsulok.Maghanap
Matapos basahin ang libro, wala akong nakitang isang (kahit isa) na paraan ng pagbuo ng Delaunay triangulation na medyo angkop para sa aking kaso. Hindi na ako naghanap ng ibang libro. Oo, at ito ay sapat na, inayos niya ang mga iniisip ng aking ulo. Dahil dito, naimbento niya ang sarili niyang "bisikleta".Algorithm
1) Ipagpalagay, bilang panimula, na mayroon lamang isang sequence sa figure na isinasaalang-alang. Pagkatapos ang lahat ay bumaba sa sunud-sunod na pagkuha ng mga tatsulok. Kumuha kami ng anumang punto at subukang bumuo ng isang tatsulok na may mga kalapit na punto. Kung hindi posible na bumuo ng isang tatsulok (ang linya na nagkokonekta sa dalawang puntong ito ay bumalandra sa mga naitayo na o ang linya ay pumasa sa exclusion zone (Figure 2), lumipat tayo sa kalapit na punto, sabihin natin sa kanan. Kapag ang susunod Ang tatsulok ay natagpuan, idinagdag namin ito sa listahan (Larawan 3), at ang punto kung saan ito itinayo ay tinanggal (Larawan 4).
Figure 2
Larawan 3
Larawan 4
Isa pang bagay: kapag nagse-save ng susunod na tatsulok, kinakailangang i-record ang mga vertex sa isang clockwise bypass (sa tamang coordinate system). Magiging kapaki-pakinabang ito sa hinaharap upang mabawasan ang mga mapagkukunan ng computing.
2) Ulitin ang hakbang 1 hanggang sa walisin natin ang buong eroplano.
3) Kung mayroong ilang mga sequence, i.e. isa, at sa loob nito ay isa o higit pang mga panloob na contour (Figure 1). Narito ito ay kinakailangan upang isaalang-alang ang bawat pagkakasunod-sunod nang hiwalay. Kumuha tayo ng isa pang panloob na tabas. Mula sa isang panlabas at isang panloob ay gagawa kami ng dalawang solong contour. Upang gawin ito, kailangan mong makahanap ng dalawang "ports" mula sa isang circuit patungo sa isa pa. Ang kondisyon para sa "mga port": hindi sila dapat mag-intersect sa isa't isa (hindi nila dapat hawakan kahit na ang mga dulo), hindi sila dapat mag-intersect sa mga linya ng contour (Larawan 5).
Larawan 5
Larawan 6
4)
Susunod, dapat mong ipasok ang lahat ng mga panloob na pagkakasunud-sunod sa nabuo na, na hiwalay sa bawat isa (punto 3) na mga pagkakasunud-sunod. Kailangan mong pagsamahin ang isa na naglalaman ng bago. Sa pamamagitan ng kahulugan, walang panloob na pagkakasunud-sunod ang dumadampi o nagsa-intersect sa iba (maaaring isang panlabas o lahat ng posibleng panloob), kaya magiging maayos ang lahat.
Ang pagkakaroon ng natagpuan ang mga port (Larawan 6), madaling bumuo ng mga bagong pagkakasunud-sunod at i-bypass ang mga ito gamit ang mga puntos 1 at 2 ng kasalukuyang algorithm (Larawan 7).
Larawan 7
5)
Pagkatapos ng ika-4 na yugto, mayroon kaming isang listahan ng mga tatsulok (Larawan 8). Na parang nakayanan na natin ang gawain, ngunit nananatili itong gawing maganda ang larawan: suriin ang katuparan ng kondisyon ng Delaunay (Larawan 9).
Larawan 8
Larawan 9
6) Sa hinaharap, sasabihin ko sa iyo ang tungkol sa ikaanim na punto. Binubuo ito sa isang sunud-sunod na pagtakbo sa listahan ng mga natanggap na tatsulok ayon sa punto No. 5. Una, minarkahan namin ang lahat ng mga tatsulok bilang "marumi". Sa bawat cycle, sinusuri namin ang kondisyon ng Delaunay para sa bawat tatsulok. Kung ang kundisyon ay hindi natutugunan, pagkatapos ay itatayo namin at markahan ang mga kapitbahay at ang kasalukuyang tatsulok bilang "marumi". Kung ang kundisyon ay natugunan, pagkatapos ay markahan itong malinis. Sa aking pagpapatupad ng algorithm, ang bawat tatsulok ay may link sa mga kapitbahay nito. Sa kasong ito, ang ika-6 na punto ay gumagana ang pinakamabilis.
Higit pa tungkol sa ikalimang yugto
Ngayon, sa pagkakaalam ko, may dalawang posibleng paraan upang matukoy kung ang mga tatsulok ay nakakatugon sa kondisyon ng Delaunay o hindi: 1) Suriin ang kabuuan ng magkasalungat na mga anggulo. Ito ay dapat na mas mababa sa 180. 2) Kalkulahin ang gitna ng circumscribed na bilog at kalkulahin ang distansya sa ika-4 na punto. Alam ng lahat na ang kondisyon ng Delaunay ay nasiyahan kung ang punto ay nasa labas ng circumscribed circle.Computing power #1: 10 multiplication/dividing operations at 13 karagdagan/subtraction operations.
Computing power #2: 29 multiplications/divisions at 24 additions/subtractions.
Mula sa punto ng view ng computing power, na kung saan ay kinakalkula, halimbawa, sa libro, ang opsyon na numero 1 ay mas kumikita. At napagtanto niya ito, kung hindi para sa ... (Figure 10). Tulad ng nangyari, pagkatapos ilagay ang pamamaraang ito sa "conveyor", nagkaroon ng kawalan ng katiyakan. Isa itong opsyon kapag ang angle A mismo ay mas malaki sa 180 degrees. Ito ay itinuturing sa aklat bilang isa sa mga hiwalay na pribadong pamamaraan. At kasama nito, nawawala ang lahat ng kagandahan, transparency at performance nito. At sa kalaunan ay napag-alaman na ang paraan No. 2 ay maaaring lubos na ma-optimize.
Larawan 10
Pag-optimize ng algorithm para sa pagsuri sa kondisyon ng Delaunay sa pamamagitan ng equation ng circumscribed na bilog
Ang sumusunod ay purong matematika.Kaya mayroon kaming:
Ang pagsuri sa kondisyon para sa puntong M(X, Y) sa pamamagitan ng equation ng isang bilog na dumadaan sa mga puntos na A(x1, y1), B(x2, y2), C(x3, y3) ay maaaring isulat bilang:
(a ⋅ (X^2 + Y^ 2) − b ⋅ X + c ⋅ Y − d) ⋅ lagdaan ang ≥ 0
Ang mga detalye ay matatagpuan sa mahusay na aklat. (Hindi, hindi ako ang may-akda)
Kaya, ang sign a ay ang tanda ng direksyon ng traversal, sa simula pa lang ay nagtayo ako ng mga triangles clockwise, upang ito ay maalis (ito ay katumbas ng isa).
A(x1 - X, y1 - Y), B(x2 - X, y2 - Y), B(x3 - X, y3 - Y);
D >= 0
Larawan 11
Di ba?
Ayon sa libro, muli,
(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
Mayroon kaming: 15 multiplication/division operations at 14 addition/subtraction operations.
Salamat sa iyong atensyon. Naghihintay ako ng kritisismo.
Bibliograpiya
1. Skvortsov A.V. Delaunay triangulation at ang aplikasyon nito. - Tomsk: Publishing House Vol. un-ta, 2002. - 128 p. ISBN 5-7511-1501-5Upang mabilang ang kalidad ng itinayong triangulation, tinukoy namin ang dalawang uri ng pamantayan, topological at geometric.
Ang topological criterion ay batay sa pinakamalapit na kapitbahay ng isang punto mula sa isang set. Sa isip, ang isang punto ay may 6 na kapitbahay para sa isang 2D na rehiyon at 12 na mga kapitbahay para sa isang 3D na rehiyon. Kumuha kami ng topological na pagtatantya gamit ang formula (1), kung saan ang kabuuang bilang ng mga puntos sa rehiyon, ay ang antas o bilang ng mga kalapit na puntos na konektado sa isang panloob na punto.
Ang geometric criterion ay batay sa pagkakaiba sa pagitan ng inscribed at circumscribed na bilog sa paligid ng kalkuladong triangular na elemento. Kumuha kami ng geometric na pagtatantya gamit ang formula (2), kung saan ang bilang ng mga tatsulok, ay ang radius ng inscribed na bilog, ay ang radius ng circumscribed na bilog.
Algorithm para sa pagbuo ng triangulation
Mayroong isang malaking bilang ng mga algorithm para sa pagbuo ng triangulation. Magkaiba sila sa bawat isa sa pagiging matrabaho, pagiging kumplikado ng pagpapatupad sa isang computer, at mga diskarte sa konstruksyon. Maaari kang matuto nang higit pa tungkol sa mga algorithm sa aklat ni A.V. Skvortsova. Isaalang-alang natin ang ilang mga algorithm.
Isa sa mga unang iminungkahi sakim na algorithm pagbuo ng triangulation. Ang Delaunay triangulation ay tinatawag na greedy kung ito ay binuo gamit ang greedy algorithm. Ang pagiging kumplikado ng matakaw na algorithm kasama ang ilan sa mga pagpapabuti nito ay . Dahil sa napakalaking kumplikado sa pagsasanay, halos hindi ito ginagamit. Isaalang-alang ang algorithm nang sunud-sunod:
Hakbang 1. Ang isang listahan ng lahat ng posibleng mga segment ng linya na nagkokonekta sa mga pares ng mga source point ay nabuo at pinagbubukod-bukod ayon sa haba ng mga segment.
Hakbang 2 Simula sa pinakamaikling isa, ang mga segment ay sunud-sunod na ipinapasok sa triangulation. Kung ang segment ay hindi bumalandra sa iba pang mga naunang ipinasok na mga segment, pagkatapos ito ay ipinasok, kung hindi, ito ay itatapon.
Tandaan na kung ang lahat ng posibleng mga segment ay may iba't ibang haba, kung gayon ang resulta ng algorithm na ito ay hindi malabo, kung hindi, depende ito sa pagkakasunud-sunod ng pagpapasok ng mga segment na may parehong haba.
Paulit-ulit na algorithm ay batay sa isang napakasimpleng ideya ng sunud-sunod na pagdaragdag ng mga puntos sa isang bahagyang nabuong Delaunay triangulation. Ang pagiging kumplikado ng algorithm na ito ay binubuo ng pagiging kumplikado ng paghahanap ng isang tatsulok, kung saan ang isang punto ay idinagdag sa susunod na hakbang, ang pagiging kumplikado ng pagbuo ng mga bagong tatsulok, pati na rin ang pagiging kumplikado ng kaukulang muling pagtatayo ng istraktura ng triangulation bilang isang resulta ng hindi kasiya-siya. mga pagsusuri ng mga pares ng kalapit na tatsulok ng nagresultang triangulation para sa kondisyon ng Delaunay. Isaalang-alang ang algorithm nang sunud-sunod:
Hakbang 1. Sa unang tatlong panimulang punto, bumuo kami ng isang tatsulok.
Hakbang 2 Sa loop para sa lahat ng iba pang mga punto, gawin ang mga hakbang 3-5.
Hakbang 3 Ang susunod na -th point ay idinagdag sa nabuo nang triangulation structure tulad ng sumusunod. Una, ang punto ay naisalokal, i.e. mayroong isang tatsulok (itinayo nang mas maaga), kung saan ang susunod na punto ay bumagsak. O, kung ang punto ay hindi nahuhulog sa loob ng triangulation, mayroong isang tatsulok sa hangganan ng triangulation na pinakamalapit sa susunod na punto.
Hakbang 4 Kung ang isang punto ay tumama sa isang naunang ipinasok na triangulation node, kung gayon ang gayong punto ay karaniwang itinatapon, kung hindi, ang punto ay ipinasok sa triangulation bilang isang bagong node. Bukod dito, kung ang punto ay tumama sa ilang gilid, pagkatapos ay nahahati ito sa dalawang bago, at ang parehong mga tatsulok na katabi ng gilid ay nahahati din sa dalawang mas maliit. Kung ang punto ay mahigpit na nasa loob ng anumang tatsulok, ito ay nahahati sa tatlong bago. Kung ang punto ay nasa labas ng triangulation, kung gayon ang isa o higit pang mga tatsulok ay binuo.
Hakbang 5 Ang mga lokal na pagsusuri sa mga bagong nakuhang tatsulok para sa pagsunod sa kondisyon ng Delaunay ay isinasagawa at ang mga kinakailangang muling pagsasaayos ay isinasagawa.
Kapag gumagawa ng mga bagong tatsulok, dalawang sitwasyon ang posible kapag ang idinagdag na punto ay nasa loob ng triangulation o sa labas nito. Sa unang kaso, ang mga bagong tatsulok ay itinayo at ang bilang ng mga aksyon na isinagawa ng algorithm ay naayos. Sa pangalawa, kinakailangan na bumuo ng mga karagdagang tatsulok na panlabas sa kasalukuyang triangulation, at ang kanilang bilang ay maaaring pantay sa pinakamasamang kaso? 3. Gayunpaman, hindi hihigit sa mga tatsulok ang idaragdag para sa lahat ng mga hakbang ng algorithm, kung saan ang kabuuang bilang ng mga unang puntos. Samakatuwid, sa parehong mga kaso, ang kabuuang oras na ginugol sa pagbuo ng mga tatsulok ay.
Algoritmo ng chain isa sa mga unang mahusay na triangulation construction algorithm ay batay sa isang planar graph regularization procedure at monotone polygon triangulation. Ang pagiging kumplikado ng algorithm na ito ay, kung saan ang bilang ng mga paunang segment. Isaalang-alang ang algorithm nang sunud-sunod:
Hakbang 1. Mula sa hanay ng mga paunang segment ng istruktura, bumubuo kami ng isang konektadong planar graph (Larawan 4, a).
Hakbang 2 Ang graph ay regularized, i.e. ang mga bagong gilid ay idinagdag na hindi nagsasalubong sa iba, upang ang bawat taluktok ng graph ay maging katabi ng hindi bababa sa isang taluktok sa itaas nito at isa sa ibaba nito. Ginagawa ang regularization sa dalawang pass gamit ang vertical flat sweep. Sa unang pass mula sa ibaba hanggang sa itaas, sunud-sunod naming mahanap ang lahat ng mga vertice kung saan walang mga gilid na humahantong pataas. Halimbawa, sa (Figure 4, b) ito ang vertex B. Pagguhit ng pahalang na linya, makikita natin ang pinakamalapit na mga gilid ng AD at EF graph na tinawid nito sa kaliwa at kanan. Pagkatapos ay nakita namin ang pinakamababang vertex sa DEHG quadrilateral at gumuhit ng isang gilid mula sa B papunta dito. Katulad nito, ang pangalawang pass ay ginagawa mula sa itaas hanggang sa ibaba (Figure 4, c). Bilang resulta ng hakbang na ito, ang bawat lugar ng planar graph ay nagiging monotone polygon.
Hakbang 3 Ang bawat lugar ng graph ay dapat nahahati sa mga tatsulok. Upang gawin ito, maaari mong gamitin ang algorithm ng non-convex merging ng dalawang triangulations (Figure 4, d).
Figure 4. Scheme ng pagpapatakbo ng triangulation chain algorithm: a) - mga paunang segment; b - pagpasa mula sa ibaba hanggang sa itaas ng regularisasyon ng graph; c) - daanan mula sa itaas hanggang sa ibaba; d) - triangulation ng monotone polygons
Upang ipatupad ang chain algorithm, pinakamahusay na gumamit ng mga istruktura ng data kung saan ang mga gilid ay tahasang kinakatawan, gaya ng "Double edges" o "Knots, edges at triangles".
Ang kawalan ng algorithm ng chain ay walang masasabi nang maaga tungkol sa anyo ng nagresultang triangulation. Ito ay hindi isang pinakamainam na triangulation, hindi isang sakim, at hindi isang napipilitang Delaunay triangulation. Ang chain algorithm ay maaaring makagawa ng napakahabang pahabang tatsulok.
Upang mapabuti ang kalidad ng resultang triangulation, ang lahat ng mga pares ng katabing tatsulok na hindi pinaghihiwalay ng isang structural edge ay maaaring suriin para sa katuparan ng kondisyon ng Delaunay at, kung kinakailangan, muling itayo. Bilang resulta, magkakaroon ng Delaunay triangulation na may mga paghihigpit.
Ang mga modelo ng GRID ay mga modelo ng mga regular na cell.
Hayaan ang coordinate system 
at 
at 
. Mga set ng user 
at mga hakbang sa sampling 
.
,
- mga pisikal na coordinate ng punto.
Kalkulahin 
at 
,
- bit na grid.
- mga quantized na halaga. totoo:
- parameter ng algorithm - ang bilang ng mga puntos, 
- ang bigat. Ang mas malapit sa punto, mas malaki ang timbang.
- antas ng distansya (1 o 2).
Salik ng normalisasyon: 
Paano 
mas malapit sa 1, ang mas maraming timbang na puntos ay isinasaalang-alang.
Ito ang paraan ng IDW - mahaba, para sa bawat t ito ay kinakailangan upang makahanap ng mga kapitbahay. Ang isang hanay ng mga kapitbahay ay mahusay na mahahanap - pinakamalapit. Ang bawat isa sa mga puntos ay gumagawa ng isang "peg" ng isang tiyak na taas. Malaki ang nakasalalay sa iregularidad ng pagtatakda ng punto, para dito ang kinukuha nila 
o 
mga. hatiin sa mga sektor at magtayo sa paligid ng punto.
Advantage– pagiging simple
kapintasan:
------Ticket 14. Tin-model. Delaunay triangulation algorithms ------
1) Triangulation (lata).
Triangulation– pagbuo ng isang function sa anyo ng isang set ng piecewise linear function
Triangulation– interpolation sa loob ng convex region.
Triangulation ay isang planar graph na ang lahat ng mga panloob na gilid ay mga tatsulok; isang paraan ng pagkatawan ng espasyo sa anyo ng mga tatsulok na magkadugtong sa isa't isa nang hindi nagsasapawan. Ang triangulation ay binuo sa isang hanay ng mga punto sa maraming paraan.
Kailangan namin ng algorithm para makabuo ng pinakamainam na triangulation.
Isang eroplanong dumadaan sa 3 puntos.
1) Maghanap ng isang tatsulok na 
;
2)
- binubuo namin ang equation ng eroplano.
Upang suriin kung ang mga punto ay nasa loob ng tatsulok o hindi, kailangan mong palitan ang halaga sa equation ng mga linya - ang mga gilid ng tatsulok. Kung ang lahat ng 3 equation > 0, pagkatapos ay sa loob.
Tingnan ang istraktura:
Ang bawat triangulation ay naglalaman ng parehong bilang ng mga tatsulok.
, saan 
ay ang bilang ng mga panloob na puntos, 
- dami ng puntos.
Matakaw triangulation.
Ikinonekta namin ang lahat ng mga punto na may mga gilid, piliin ang minimum, idagdag sa triangulation. Susunod, kinukuha namin ang susunod na minimum na hindi bumalandra sa mga nauna, at iba pa. Ang resulta ay isang matakaw na triangulation.
Delaunay triangulation.
Ang mga punto ng iba pang mga tatsulok ay hindi nahuhulog sa loob ng isang bilog na nakapaligid sa anumang tatsulok. Itinayo sa isang paraan.
Ang isang pitik ay isang pitik ng mga gilid. Pinapayagan ka nitong lumipat mula sa kumbensyonal na triangulation patungo sa Delaunay triangulation. Upang suriin kung ang isang punto ay kabilang sa isang bilog: palitan kung< R, то внутри.
Delaunay kondisyon.
Equation ng isang bilog na dumadaan sa tatlong puntos:
Kung mas mababa sa zero, pagkatapos ay panlabas, kung hindi man - panloob.
ay ang kondisyon ng Delaunay.
Ang algorithm para sa pagbuo ng Delaunay triangulation:
1) Sa ilalim ng pagsisiyasat sa pagdaragdag ng mga puntos ay isang simpleng umuulit na algorithm:
May isang set 
idagdag sa tatsulok, ang konstruksiyon ay isinasagawa 
pagkahati ng isang tatsulok 
muling pagtatayo. Sa zero stage, nagdadagdag kami ng 3-4 fictitious points na halatang sumasakop sa envelope namin, nasa loob lahat ng points. Pagkatapos naming maghagis ng isang punto, tingnan kung aling tatsulok ang tumama, hatiin ito sa 3, para sa bawat tatsulok ay sinusuri namin ang kondisyon ng Delaunay at i-flip ang mga gilid. Ang average na bilang ng mga muling pagtatayo ay tatlo.
Teoretikal na pagiging kumplikado 
2) Mga paraan ng pagpabilis. Batay sa mga puntos na umaasa sa istatistika. Ang tatsulok ng binhi ay ang tatsulok kung saan nahulog ang nakaraang punto. Pagkatapos ay ikinonekta namin ang dalawang punto - ang nauna at ang bago.
Lumipat kami mula sa unang punto patungo sa isa pa.
(Pagbuo at Pagpapatupad ng mga Algorithms para sa Constrained Volume Triangulations: Iterative Algorithm
Preprint, Inst. Appl. Math., ang Russian Academy of Science)
Galanin M.P., Shcheglov I.A.
(M.P.Galanin, I.A.Sheglov)
IPM sila. M.V. Keldysh RAS
Moscow, 2006
Ang gawaing ito ay sinusuportahan ng Russian Foundation for Basic Research (Project No. 06-01-00421)
anotasyon
Isinasaalang-alang ang mga iterative na pamamaraan para sa tatlong-dimensional na discretization ng mga spatial domain (pagbuo ng mga tetrahedral meshes): mga paraan ng pagwawasto ng hangganan, mga pamamaraan batay sa pamantayan ng Delaunay, at mga paraan ng pagkaubos. Ang mga variant ng mga algorithm para sa bawat isa sa mga pamamaraang ito ay ibinigay. Ang mga tampok ng pagbuo ng mga grids sa mga kumplikadong domain ay tinalakay.
Abstract
Tatlong pangunahing pamilya ng mga umuulit na algorithm para sa libre at limitadong simplicial volume triangulation ay inilalarawan: boundary correction (kabilang ang "octree" algorithm), Delaunay-based na mga pamamaraan at pagsulong ng front approach. Para sa bawat uri ng pamamaraan, ibinibigay ang isang halimbawang algorithm.
1. Panimula 3
2. Mga paraan ng pagwawasto ng hangganan4
2.1 Konstruksyon ng pangunahing grid4
2.2 Pagwawasto ng pangunahing grid6
3. Mga pamamaraan batay sa Delaunay criterion9
3.1 Pagbuo ng Delaunay triangulation sa isang naibigay na hanay ng mga puntos 12
3.2. Delaunay triangulation na may mga paghihigpit17
3.3 Mga tampok ng teknikal na pagpapatupad ng mga algorithm batay sa
Delaunay criterion
22
4. Mga paraan ng pagkahapo23
4.1 Halimbawa ng algorithm ng pagkaubos26
Sanggunian3 0
Kabilang sa dalawang klase ng mga pamamaraan ng triangulation - direkta at umuulit - ang huli ay may sapat na universality at samakatuwid, hindi tulad ng mga direktang, ay maaaring gamitin upang triangulate ang mga rehiyon ng isang medyo arbitrary na anyo. Ang kakayahang magamit na ito ay dumating sa halaga ng isang makabuluhang mas mataas na pagkonsumo ng mga mapagkukunan at isang mas labor-intensive na pagpapatupad ng pamamaraan sa isang partikular na algorithm.
Sa kasalukuyan, ang isang malaking bilang ng mga pakete ng software ay binuo batay sa isa o isa pang umuulit na pamamaraan na nagpapatupad ng pagbuo ng mga grids (bahagyang o ganap) sa awtomatikong mode. Karaniwan, ang mga pakete na ito ay komersyal, na medyo makatwiran dahil sa pagsisikap na ginugol sa kanilang paglikha, dahil ang tatlong-dimensional na espasyo ay may isang bilang ng mga hindi kasiya-siyang tampok na makabuluhang nagpapalubha sa buhay ng developer.
Ang mga mesh na ginawa sa pamamagitan ng mga umuulit na pamamaraan ay karaniwang hindi nakaayos at hindi magkakatulad. Unstructuredness ay dahil sa ang katunayan na ang topology ng grid ay nabuo sa proseso ng konstruksiyon, at samakatuwid maaari itong natural na mag-iba kahit na sa loob ng parehong subdomain. Para sa parehong dahilan, ang homogeneity, kung maaari itong lumitaw, ay nagkataon lamang.
Dahil walang masasabi tungkol sa istraktura nito sa hinaharap bago itayo ang mesh, hindi rin matitiyak ang kalidad nito. Kadalasan, ang itinayong mesh ay maaaring makabuluhang mapabuti gamit ang isa sa maraming mga diskarte sa pag-optimize. Ang posibilidad na ito ay karaniwang hindi napapabayaan, dahil ang oras na ginugol sa pag-optimize, bilang panuntunan, ay makabuluhang mas mababa kaysa sa oras na ginugol sa pagtatayo.
Ang layunin ng gawaing ito ay suriin at pag-uri-uriin ang mga umiiral na pamamaraan para sa pagbuo ng mga tetrahedral meshes sa mga three-dimensional na domain. Sa pagtingin sa malaking halaga ng impormasyon, tanging ang tinatawag na "mga pamamaraan ng umuulit" ang isinasaalang-alang sa ibaba. Ang mga direktang pamamaraan ay inilarawan sa .
Ang gawaing ito ay suportado sa bahagi ng Russian Foundation for Basic Research (Project No. 06-01-00421).
kanin. 11. Triangulation ng isang domain na kumakatawan sa unyon ng isang dodecahedron at isang icosahedron (Delaunay triangulation na may mga paghihigpit)
Ang kalidad ng mga mesh na ginawa ng pamamaraang ito ay nasa isang average na antas (ang tetrahedra malapit sa mga hangganan ay maaaring magkaroon ng napakahinang hugis), kaya ang isa sa mga paraan ng pag-optimize ay kadalasang ginagamit din.
Sa mga gawa ni B. Joe, ang iba pang mga variant ng algorithm ay iminungkahi na hindi gumagamit ng mga karagdagang puntos at ganap na nakabatay sa mga lokal na pagbabagong katulad ng "kalakalan".
4) ang dami ng tetrahedron ay hindi hihigit sa maximum na pinapayagan ().
Mula sa lahat ng tetrahedra () ang tetrahedron ng pinakamahusay na kalidad ay pinili at ang paglipat sa hakbang 5 ay ginawa; kung walang tetrahedra na nakakatugon sa ipinahiwatig na mga kondisyon, pagkatapos ay isinasagawa ang paglipat sa hakbang 4.
4. Mayroong isang punto sa loob ng hindi pa rin nauubos na rehiyon na:
1) natutugunan ng tetrahedron () ang lahat ng kundisyon ng talata 3;
2) sa isang bola walang remote pointF(pinipigilan nitong mailagay ang nodep masyadong malapit sa mga mukha at vertex ng umiiral na tetrahedra).
Isang variant ng algorithm ng paghahanap ng nodeptinalakay sa ibaba.
5. Alisin ang lahat ng vertexF, nahuhulog sa loob (at sa mga hangganan) ng nabuong tetrahedron. Pagkatapos ay na-update ang harap ayon sa sumusunod na pamamaraan: ang bawat mukha ng nabuong tetrahedron ay isinasaalang-alang at
1) kung ang mukha ay isang harap na mukha, pagkatapos ay aalisin ito sa harap;
2) kung ang mukha ay HINDI mukha sa harapan, ito ay idinaragdag sa harap.
6. Kung may mga undeleted points pa rinFo (na katumbas) ang harap ay hindi walang laman (iyon ay, ang rehiyon ay hindi pa ganap na naubos), ang paglipat sa hakbang 1 ay isinasagawa, kung hindi, ang proseso ay tapos na.
Kaya ang arrayFay ginagamit para sa ilang mga layunin nang sabay-sabay: upang tantyahin ang halaga ng solid anggulo, upang makontrol ang kawastuhan ng konstruksiyon, at upang makontrol ang paglalagay ng mga bagong node. Isang array dinFkapaki-pakinabang para sa pagpapakita ng pag-unlad. Ang ratio ng bilang ng mga puntos na inalis sa panahon ng pagpapatakbo ng algorithmFsa paunang bilang ng mga umiiral na puntosFaktwal na nagpapakita kung gaano karami ng lugar ang naubos na.
Bumalik tayo sa tanong ng paghahanap ng mga coordinate ng isang bagong node para sa pagbuo ng isang tetrahedron (item 4 ng inilarawan na algorithm). Hayaan ang tatlong node - ibigay.
1. Sa unang hakbang, nakita namin - ang sentro ng masa ng tatsulok (bilang ang ibig sabihin ng aritmetika ng mga coordinate ng mga node nito) at ang yunit na normal sa eroplano ng mukha (sa pamamagitan ng normalized na produkto ng vector).
2. Susunod, ang unang pagtatantya ay tinutukoy para sa distansya mula sa nais na puntop (H), batay sa maximum na volume ng tetrahedron: . Tandaan na ang lugar ng mukhaSaktwal na natagpuan sa nakaraang hakbang (ang resulta ng cross product ng dalawang gilid ay katumbas ng dalawang beses sa lugar ng mukha), at ang maximum na volume ay tinutukoy ng halaga ng control function.
3. Sinusuri ang punto. Kung natutugunan ng tetrahedron () ang lahat ng kinakailangan, pumunta sa hakbang 6, kung hindi ay pumunta sa hakbang 4.
4. Sinusuri ang punto. Kung natutugunan ng tetrahedron () ang lahat ng kinakailangan, pumunta sa hakbang 6, kung hindi ay pumunta sa hakbang 5.
5. Maniwala ka at pumunta sa hakbang 3.
6. Ang nais na node ay matatagpuan.
Tandaan na sa 99% ng mga kaso ang nais na punto ay matatagpuan sa 1 o 2 pag-ulit ng algorithm na ito.
Sa algorithm ng pagkaubos na inilarawan sa itaas, isang tetrahedron ang inaalis mula sa rehiyon sa bawat hakbang. empleyado ng NASA na si Sh. Pirzade ( Shahyar Pirzadeh ) nagmungkahi ng isa pang bersyon ng algorithm, kung saan ang isang buong layer ng tetrahedra ay tinanggal mula sa rehiyon nang sabay-sabay (iyon ay, sa bawat pag-ulit, ang tetrahedra ay binuo kaagad para sa lahat ng mga mukha ng kasalukuyang harap) . Taliwas sa mga inaasahan, ang variant na ito ay hindi gaanong nagpapabilis sa proseso ng pagtatayo (dahil ang lahat ng bagong tetrahedra ay kailangan pa ring suriin para sa kawastuhan), ngunit inaalis nito ang pangangailangan na hanapin ang pinaka-angkop na mukha para sa pagtatayo ng isang tetrahedron. Ito, gayunpaman, ay sa halip ay isang minus kaysa sa isang plus, dahil dahil sa tampok na ito, ang Pirzade variant ay hindi gaanong maaasahan at maaaring mabigo sa geometrically complex na mga lugar. Kasabay nito, nagpapakita ito ng magagandang resulta sa medyo simpleng mga lugar.
Ang mga meshes na itinayo ng mga pamamaraan ng pagkaubos, bilang panuntunan, ay may mahusay na kalidad, at ang kasunod na pag-optimize ng posisyon ng mga node ay nagbibigay ng karagdagang pagtaas sa kalidad. Summing up, tandaan namin na ang mga paraan ng pagkaubos ay pinaka-epektibo kung ang triangulation ng hangganan ng lugar ay unang nakatakda. Ito ang kanilang pangunahing pagkakaiba mula sa mga pamamaraan batay sa Delaunay criterion, kung saan ang sitwasyon ay direktang kabaligtaran.
Bibliograpiya
1. Shaydurov V.V. Multigrid Finite Element Methods. - M., Nauka, 1989. - 288s.
2. Skvortsov A.V. Pangkalahatang-ideya ng mga algorithm para sa pagbuo ng Delaunay triangulation // , 2002, №3, c. 14-39.
3. Skvortsov A.V. Algorithm para sa pagbuo ng isang triangulation na may mga paghihigpit // Mga pamamaraan at programming sa computational, 2002, №3, c. 82-92.
4. I.Babushka, W.C. Rheinboldt. A-posteriori Error Estimates para sa Finite Element Method // Int. J. Numero. Meth. Sinabi ni Eng., Vol. 12, p.p. 1597-1615, 1978.
5. T.J. Panadero. Awtomatikong Pagbuo ng Mesh para sa Mga Kumplikadong Tatlong Dimensyon na Rehiyon Gamit ang Pinilit na Delaunay Triangulation // Engineering Gamit ang mga Computer, Springer-Verlag, No. 5, p.p. 161-175, 1989.
6. M. Bern, D. Eppstein. Pagbuo ng Mesh at Pinakamainam na Triangulation // Pag-compute sa Euclidean Geometry, World Scientific Publishing Co., p.p. 23-90, 1995.
7. D.K. Blandford, G. Blelloch, D. Cardoze, C. Kadow. Mga Compact na Representasyon ng Simplicial Meshes Sa Dalawa at Tatlong Dimensyon // Mga Pamamaraan ng 12th International Meshing Roundtable, Sandia National Laboratories, p.p.135-146, Set. 2003.
8. H. Borouchaki, S.H. Lo. Mabilis na Delaunay Triangulation Sa Tatlong Dimensyon // Mga Paraan ng Computer Sa Applied Mechanics At Engineering, Elsevier, Vol. 128, p.p. 153-167, 1995.
9. E.K. Buratynski. Isang Three-Dimensional Unstructured Mesh Generator para sa Arbitrary Internal Boundaries // Numerical Grid Generation sa Computational Fluid Mechanics, Pineridge Press, p.p. 621-631, 1988.
10. P.R. Cavalcanti, U.T. Mello. Three-Dimensional Constrained Delaunay Triangulation: Isang Minimalist Approach // Mga Pamamaraan ng 8th International Meshing Roundtable, p.p. 119-129, 1999.
11. Dey, K. Tamal, K. Sugihara, C.L. Bajaj. Delaunay Triangulations Sa Tatlong Dimensyon na May Finite Precision Arithmetic // Computer Aided Geometric Design, North-Holland, No. 9, p.p. 457-470, 1992.
12. H.N. Djidjev. Force-Directed Methods Para sa Smoothing Unstructured Triangular At Tetrahedral Meshes // Mga Pamamaraan ng 9th International Meshing Roundtable, Sandia National Laboratories, p.p. 395-406, Oktubre 2000.
13. L. Durbeck. Pagsingaw: Isang Pamamaraan Para sa Pagpapakita ng Kalidad ng Mesh // Mga Pamamaraan ng 8th International Meshing Roundtable, South Lake Tahoe, CA, U.S.A., p.p. 259-265, Oktubre 1999.
14. D.A. patlang. Laplacian Smoothing At Delaunay Triangulations // , vol. 4, p.p. 709-712, 1988.
15. P.J. Frey, H. Borouchaki, P.-L. George. Delaunay Tetrahedralization Gamit ang Advancing-Front Approach // Mga Pamamaraan ng 5th International Meshing Roundtable, Sandia National Laboratories, p.p. 31-46, Oktubre 1996.
16. L.A. Freitag, C. Ollivier-Gooch. Isang Paghahambing ng Tetrahedral Mesh Improvement Techniques // Mga Pamamaraan ng 5th International Meshing Roundtable, Sandia National Laboratories, p.p. 87-106, Oktubre 1996.
17. L.A. Freitag, C. Ollivier-Gooch. Pagpapaganda ng Tetrahedral Mesh Gamit ang Pagpapalit at Pagpapakinis // , vol. 40, p.p. 3979-4002, 1995.
18. L.A. Freitag, C. Ollivier-Gooch. Ang Epekto ng Kalidad ng Mesh Sa Kahusayan ng Solusyon // Mga Pamamaraan ng 6th International Meshing Roundtable, Sandia National Laboratories, p.p.249, Oktubre 1997.
19. P.L. George. TET MESHING: Construction, Optimization at Adaptation // Mga pamamaraan ng ika-8International Mesh Roundtable, p.p.133-141, 1999.
20. N.A. Golias, T.D. Tsiboukis. Isang Diskarte sa Pagpipino ng Three-Dimensional Tetrahedral Meshes Batay sa Delaunay Transformations // , John Wiley, No. 37, p.p.793-812, 1994.
21. C. Hazlewood. Pagtatantya sa Mga Pinilit na Tetrahedralization // Computer Aided Geometric Design, vol. 10, p.p. 67–87, 1993.
22. B. Joe. Delaunay Triangular Meshes sa Convex polygons, SIAM J Sci. stat. Comput., Vol. 7, p.p. 514-539, 1986.
23. B. Joe. Pagbuo ng Three-Dimensional Delaunay Triangulations Gamit ang Lokal na Pagbabago // Computer Aided Geometric Design, Vol. 8, p.p. 123-142, 1991.
24. B. Joe. Pagbuo ng Three-Dimensional Improved-Quality Triangulations Gamit ang Local Transformations // Siam J. Sc. Comput., vol. 16, p.p. 1292-1307, 1995.
25. R.W. Lewis, Yao Zheng, D.T. Gethin. Three-Dimensional Unstructured Mesh Generation: Part 3. Volume Meshes // Mga Paraan ng Computer Sa Applied Mechanics At Engineering, Elsevier, Vol 134, p.p. 285-310, 1996.
26. A. Liu, B. Joe. Sa Hugis Ng Tetrahedra Mula sa Bisection // Matematika ng Pagtutuos, vol. 63, No. 207, 141–154, 1994.
27. S.H. Lo. Volume Discretization sa Tetrahedra-I. Pag-verify at Oryentasyon ng mga Hangganan ng Hangganan // Mga Kompyuter at Istruktura, Pergamon Press, Vol. 39, blg. 5, p.p. 493-500, 1991.
28. S.H. Lo. Volume Discretization sa Tetrahedra - II. 3D Triangulation sa pamamagitan ng Advancing Front Approach // Mga Kompyuter at Istruktura, Pergamon, Vol. 39, blg. 5, p.p. 501-511, 1991.
29. R. Lohner. Pagbuo ng Three-Dimensional Unstructured Grids Sa Pamamaraan ng Advancing Front // Mga Proceeding ng 26th AIAA Aerospace Sciences Meeting, Reno, Nevada, 1988.
30. S.J. Owen. Isang Survey ng Unstructured Mesh Generation Technology // Mga Pamamaraan ng 7th International Meshing Roundtable, p.p. 239-269, Dearborn, MI, 1998.
31. V.N. Parthasarathy, C.M. Graichen, A.F. Hathaway. Isang Paghahambing ng Mga Pagsukat sa Kalidad ng Tetrahedron // May hangganang Elemento sa Pagsusuri at Disenyo, Elsevier, hindi. 15, p.p. 255-261, 1993.
32. S. Pirzadeh. Unstructured Viscous Grid Generation sa pamamagitan ng Advancing-Layers Method // AIAA-93-3453-CP, AIAA, p.p. 420-434, 1993.
33. V.T. Rajan. Optimality ng Delaunay Triangulation sa // Proc. Ika-7 ACM Symp. Comp. geometry, p.p. 357-363, 1991.
34. A. Rassineux. Pagbuo at Pag-optimize ng Tetrahedral Meshes sa pamamagitan ng Advancing Front Technique // International Journal para sa Numerical Methods in Engineering, Wiley, Vol. 41, p.p. 651-674, 1998.
35. S. Rebay. Mahusay na Unstructured Mesh Generation sa pamamagitan ng Delaunay Triangulation at Bowyer-Watson Algorithm // Journal ng Computational Physics, vol. 106, p.p. 125-138, 1993.
36. M.-C. Rivara. Selective Refinement/Derefinement Algorithm Para sa Mga Sequence Ng Nested Triangulations // International Journal para sa Numerical Methods in Engineering, No. 28, p.p. 2889-2906, 1998.
37. M.-C. Rivara, C. Levin. Isang 3D Refinement Algorithm na Angkop Para sa Adaptive At Multigrid Techniques // Mga Komunikasyon sa Applied Numerical Methods, No. 8, p.p. 281-290, 1998.
38. J. Ruppert. Isang Delaunay refinement algorithm para sa de-kalidad na 2-dimensional mesh generation // Journal ng Algorithm, No. 18, p.p. 548-585, 1995.
39. MS. Pastol, M.K. Georges. Three-Dimensional Mesh Generation sa pamamagitan ng Finite Octree Technique // International Journal para sa Numerical Methods in Engineering, vol. 32, p.p. 709-749, 1991.
40. MS. Shephard, F. Guerinoni, J.E. Flaherty, R.A. Ludwig, P.L. Baehmann. Finite octree mesh generation para sa automated adaptive 3D Flow Analysis // Pagbuo ng numerical grid sa computational fluid mechanics Miami, 1988
41. K. Shimada, D.C. Gosard. Bubble Mesh: Automated Triangular Meshing ng Non-manifold Geometry sa pamamagitan ng Sphere Packing // Mga Pamamaraan ng 3rd Symposium sa Solid Modeling at Applications , p.p. 409-419, 1995.
42. K. Shimada, A. Yamada, T. Itoh. Anisotropic Triangular Meshing ng Parametric Surfaces sa pamamagitan ng Close Packing ng Ellipsoidal Bubbles // Mga Pamamaraan ng 6th International Meshing Roundtable, p.p. 375-390, 1997.
43. D.F. Watson. Pag-compute ng Delaunay Tessellation na may Application sa Voronoi Polytopes // Ang Computer Journal, Vol. 24(2), p.p. 167-172, 1981.
44. M.A. Yerry, M.S. Pastol. Three-Dimensional Mesh Generation sa pamamagitan ng Modified Octree Technique // International Journal para sa Numerical Methods in Engineering, Vol. 20, p.p. 1965-1990, 1984.
45. Galanin M.P., Shcheglov I.A. Pag-unlad at pagpapatupad ng mga algorithm para sa tatlong-dimensional na triangulation ng mga kumplikadong spatial na rehiyon: mga direktang pamamaraan. IPM preprint im. M.V. Keldysh RAN, 2006, sa press. puntos, ibig sabihin. Steiner knots - mga karagdagang knot na hindi kasama sa orihinal na set
Maaaring mukhang ang kundisyon 2 ay sumusunod sa kundisyon 3, ngunit sa katunayan ay hindi. Halimbawa, ang isang umiiral na tetrahedron ay maaaring ganap sa loobnasubok na tetrahedron.
