Yksinkertainen monikulmio

Yksinkertainen monikulmio  on kuvio, joka koostuu ei-leikkautuvista segmenteistä ("sivuista"), jotka on yhdistetty pareittain muodostamaan suljetun polun. Jos sivut leikkaavat, monikulmio ei ole yksinkertainen. Usein sana "yksinkertainen" jätetään pois yllä olevasta määritelmästä.

Yllä oleva määritelmä tarjoaa seuraavat muodon ominaisuudet:

• Monikulmio ympäröi aluetta (kutsutaan sisäpuolelle), jolla on aina mitattava alue.
• Monikulmion muodostavat janat (kutsutaan sivuiksi, harvemmin reunoiksi) leikkaavat vain päätepisteistään, joita kutsutaan pisteiksi (tai vähemmän muodollisesti "nurkiksi").
• Täsmälleen kaksi sivua kohtaavat kussakin kärjessä.
• Sivujen lukumäärä on aina yhtä suuri kuin pisteiden lukumäärä.

Yleensä vaaditaan, että kaksi kärjessä kohtaavaa sivua eivät muodosta suoraa (180°) kulmaa. Muussa tapauksessa samalla suoralla linjalla olevat sivut katsotaan osaksi samaa sivua.

Matemaatikot käyttävät yleensä termiä "polygoni" vain viivaosien muodostamista kuvioista, ei sisällä sisäosia. Jotkut kuitenkin käyttävät termiä "polygoni" viittaamaan tasaiseen kuvioon , jota rajoittaa rajallisesta segmenttien sarjasta koostuva suljettu polku (eli suljettu polyline ). Riippuen käytetystä määritelmästä, reunus voi olla osa monikulmiota [1] .

Yksinkertaisia ​​polygoneja kutsutaan myös Jordanin polygoneiksi , koska Jordanin lauseella voidaan todistaa, että tällaiset polygonit jakavat tason kahteen alueeseen, sisä- ja ulkopuolelle. Tasossa oleva monikulmio on yksinkertainen silloin ja vain, jos se vastaa topologisesti ympyrää . Sen sisäpuoli vastaa topologisesti ympyrää .

Heikosti yksinkertainen monikulmio

Jos joukko ei-leikkautuvia segmenttejä muodostaa tasossa alueen rajan, joka on topologisesti yhtä suuri kuin ympyrä, niin tätä rajaa kutsutaan heikosti yksinkertaiseksi monikulmioksi [2] . Vasemmalla olevassa kuvassa ABCDEFGHJKLM on määritelmänsä mukaan heikosti yksinkertainen monikulmio. Sininen edustaa aluetta, jonka rajana on heikosti yksinkertainen monikulmio. Tämän tyyppisiä heikosti yksinkertaisia ​​polygoneja voi esiintyä tietokonegrafiikassa ja CAD -järjestelmissä monikulmioalueiden tietokoneesityksenä onteloineen - jokaiselle ontelolle luodaan "leikkaus", joka yhdistää ulkorajaan. Kuvan mukaan ABCM on tasaisen alueen ulkoraja FGHJ-ontelon kanssa. Leikattu ED yhdistää onkalon ulkoääriviivaan ja kulkee kahdesti heikosti yksinkertaisessa monikulmiossa.

Vaihtoehtoinen ja yleisempi määritelmä heikkoille yksinkertaisille polygoneille on Fréchet'n etäisyydellä konvergoivien, samaa kombinatorista tyyppiä olevien yksinkertaisten monikulmioiden sarjan raja [3] . Tämä muotoilee ajatuksen, että monikulmion elementit saavat koskettaa, mutta eivät ristiin. Tämän tyyppinen heikosti yksinkertainen monikulmio ei kuitenkaan välttämättä muodosta alueen rajaa, koska "sisäpuoli" voi olla tyhjä. Esimerkiksi ketjukuvassa ABCBA on heikosti yksinkertainen monikulmio - sitä voidaan pitää polygonin ABCFGHA ”puristamisrajana”.

Tietokoneongelmat

Laskennallisessa geometriassa jotkin tärkeät laskentaongelmat käyttävät yksinkertaista monikulmiosyöttöä. Jokaisessa näistä tehtävistä sisä- ja ulkopuolen ero on avainasemassa [4]

• Ongelma, kuuluuko piste monikulmioon , vaatii sen määrittämisen, onko piste q monikulmion P sisällä .
• Monikulmion pinta-alan eli sisäpinta-alan laskemiseen tunnetaan yksinkertaisia ​​kaavoja .
• Monikulmion osio on joukko perusyksiköitä (esimerkiksi neliöitä), jotka eivät leikkaa ja joiden liitto muodostaa monikulmion. Monikulmion osioinnin tehtävänä on löytää osio, joka on jossain mielessä minimaalinen. Esimerkiksi väliseinä, jossa on vähimmäismäärä yksiköitä tai sivujen vähimmäispituus.
  • Erityinen monikulmion jakamistapaus on polygonin kolmiomittausongelma, joka on yksinkertaisen monikulmion jakaminen kolmioihin. Vaikka kuperat monikulmiot on helppo kolmioida, yleisten yksinkertaisten monikulmioiden kolmio on vaikeampaa, koska sinun on vältettävä lisäämästä reunoja, jotka leikkaavat monikulmion ulkopuolella. Kuitenkin Bernhard Chazelle vuonna 1991 osoitti, että mikä tahansa yksinkertainen monikulmio, jossa on n kärkeä, voidaan kolmioida optimaalisessa ajassa Θ ( n ). Samaa algoritmia voidaan käyttää määrittämään, muodostaako suljettu katkoviiva yksinkertaisen monikulmion.
• Boolen operaatiot polygoneille — erilaisia ​​Boolen operaatioita monikulmioiden sisäalueiden määrittämille pisteille.
• Yksinkertaisen monikulmion kupera runko voidaan laskea tehokkaammin kuin kupera runko muuntyyppisille syötteille, kuten pistejoukolle.
• Voronoin kaavio yksinkertaisesta polygonista
• Mediaaniakseli / topologinen luuranko / yksinkertaisen monikulmion suoraviivainen luuranko
• Yksinkertaisen monikulmion rinnakkaiskäyrä
• Minkowskin summa yksinkertaisille polygoneille

Katso myös

• tähtialue

Muistiinpanot

1. ↑ Grünbaum, 2003 .
2. ↑ Dumitrescu, Toth, 2007 , s. 177.
3. ↑ Chang, Erickson, Xu, 2015 , s. 1655-1670
4. ↑ comp.graphics.algorithms FAQ Arkistoitu 13. helmikuuta 2011 Wayback Machinessa , jossa on luettelo ratkaisuista 2D- ja 3D-polygonien matemaattisiin ongelmiin.

Kirjallisuus

• Branko Grünbaum . Kuperat polytoopit / Volker Kaibel, Victor Klee, Günter M. Ziegler. – 2. - New York, Lontoo: Springer-Verlag , 2003. - ISBN 0-387-00424-6 .
• Adrian Dumitrescu, Csaba D. Toth. STACS 2007: 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Saksa, 22.–24. helmikuuta 2007, Proceedings / Wolfgang Thomas, Pascal Weil. - kuvitettu. - Springer, 2007. - ISBN 3540709177 .
• Hsien-Chih Chang, Jeff Erickson, Chao Xu. Proceedings of Twenty S6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'15). – 2015.

Linkit

• Weisstein, Eric W. Yksinkertainen polygoni  Wolfram MathWorldissä .