Oddiy ko'pburchak - Simple polygon

Ba'zi oddiy ko'pburchaklar.

Yilda geometriya, a oddiy ko'pburchak /ˈpɒlɪɡɒn/ a ko'pburchak bunday emas kesishmoq o'zi va teshiklari yo'q. Ya'ni, bu to'g'ri, kesishmasidan iborat bo'lgan tekis shakl chiziq segmentlari yoki juftlikni birlashtirgan "yon tomonlar" yopiq yo'l. Agar tomonlar kesishgan bo'lsa, ko'pburchak oddiy emas. "Oddiy" saralashi tez-tez chiqarib tashlanadi, yuqoridagi ta'rifdan keyin umuman ko'pburchakni aniqlash tushuniladi.

Yuqorida keltirilgan ta'rif quyidagi xususiyatlarni ta'minlaydi:

  • Ko'pburchak har doim o'lchovga ega bo'lgan hududni (uning ichki qismi deb ataladi) qamrab oladi maydon.
  • Ko'pburchakni tashkil etuvchi chiziq segmentlari (qirralar yoki qirralar deb ataladi) faqat tepaliklar (singular: vertex) yoki kamroq rasmiy ravishda "burchaklar" deb nomlangan so'nggi nuqtalarida uchrashadilar.
  • To'liq ikkita qirralarning har bir tepasida uchrashadi.
  • Qirralarning soni har doim tepalar soniga teng.

Odatda burchak hosil qilish uchun burchakda yig'ilish kerak burchak bu to'g'ri emas (180 °); aks holda kollinear chiziq segmentlari bitta tomonning qismlari hisoblanadi.

Matematiklar odatda "ko'pburchak" dan faqat chiziq segmentlari tomonidan shaklga murojaat qilishadi, lekin yopiq mintaqani emas, ba'zilari "ko'pburchak" dan samolyot shakl Bu to'g'ri chiziq segmentlarining cheklangan ketma-ketligidan iborat bo'lgan yopiq yo'l bilan chegaralangan (ya'ni a yopiq ko'pburchak zanjir ). Amaldagi ta'rifga ko'ra, bu chegara ko'pburchakning o'zi tarkibiga kirishi yoki bo'lmasligi mumkin.[1]

Oddiy ko'pburchaklar ham deyiladi Iordaniya ko'pburchagi, chunki Iordaniya egri chizig'i teoremasi yordamida bunday ko'pburchak tekislikni ikki mintaqaga, uning ichidagi mintaqaga va uning tashqarisidagi mintaqaga ajratishini isbotlash uchun ishlatilishi mumkin. Tekislikdagi ko'pburchak oddiy va agar shunday bo'lsa topologik jihatdan teng a doira. Uning ichki qismi topologik jihatdan a ga teng disk.

Zaif oddiy ko'pburchak

Zaif oddiy polygon.svg

Agar kesib o'tmaydigan chiziq segmentlari to'plami topologik jihatdan diskka teng bo'lgan tekislik mintaqasining chegarasini tashkil etsa, u holda bu chegara a kuchsiz oddiy ko'pburchak.[2]Chapdagi rasmda ABCDEFGHJKLM bu ta'rifga ko'ra kuchsiz sodda ko'pburchak bo'lib, ko'k rang uning chegarasi bo'lgan hududni belgilaydi va zaif grafik ko'pburchakning bu turi kompyuter grafikalarida paydo bo'lishi mumkin va SAPR teshiklari bo'lgan ko'pburchak mintaqalarni kompyuterda namoyish etish sifatida: har bir teshik uchun uni tashqi chegaraga ulash uchun "kesma" hosil bo'ladi. Yuqoridagi rasmga murojaat qilgan holda, ABCM FGHJ teshigi bo'lgan planar mintaqaning tashqi chegarasidir. Kesilgan ED teshikni tashqi bilan bog'laydi va natijada zaif oddiy ko'pburchak tasvirida ikki marta o'tadi.

Zaif sodda ko'pburchaklarning muqobil va umumiyroq ta'rifida ular bir xil kombinatorial tipdagi oddiy ko'pburchaklarning ketma-ketlik chegaralari bo'lib, ularning ostida yaqinlashish mavjud. Frechet masofasi.[3] Bu shunday ko'pburchak segmentlarga teginish imkonini beradi, lekin kesib o'tmaydi. Biroq, zaif oddiy ko'pburchakning bu turiga mintaqaning chegarasi shakllanishi shart emas, chunki uning "ichki qismi" bo'sh bo'lishi mumkin. Masalan, yuqoridagi rasmga murojaat qilib, ABCBA ko'pburchakli zanjiri ushbu ta'rifga ko'ra kuchsiz sodda ko'pburchak hisoblanadi: uni ABCFGHA ko'pburchagining "siqish" chegarasi sifatida qarash mumkin.

Hisoblash muammolari

Yilda hisoblash geometriyasi, bir nechta muhim hisoblash vazifalari oddiy ko'pburchak shaklidagi yozuvlarni o'z ichiga oladi; ushbu muammolarning har birida muammoni aniqlashda ichki va tashqi ko'rinish o'rtasidagi farq juda muhimdir.[4]

  • Ko'pburchakda nuqta test oddiy ko'pburchak uchun aniqlashni o'z ichiga oladi P va so'rov nuqtasi q, yo'qmi q ichki makon yotadi P.[5]
  • Oddiy formulalar hisoblash uchun ma'lum ko'pburchak maydoni; ya'ni ko'pburchak ichki qismining maydoni.[6]
  • Ko'pburchak bo'limi ibtidoiy birliklar to'plami (masalan, kvadratlar), ular bir-biriga to'g'ri kelmaydi va ularning birlashishi ko'pburchakka teng. Ko'pburchakli bo'linish muammosi - bu ma'lum ma'noda minimal bo'linmani topish muammosi, masalan: eng kichik birliklar bo'linmasi yoki eng kichik umumiy uzunlikdagi birliklar.[7]
    • Ko'pburchak bo'linishning alohida holati Ko'pburchak uchburchagi: oddiy ko'pburchakni uchburchaklarga bo'lish. Qavariq ko'pburchaklarni uchburchak bilan ajratish oson bo'lsa-da, umumiy oddiy ko'pburchakni uchburchakka solish ancha mushkulroq, chunki ko'pburchak tashqarisidan o'tuvchi qirralarning qo'shilishidan qochishimiz kerak. Shunga qaramay, Bernard Shazelle 1991 yilda har qanday oddiy ko'pburchak ekanligini ko'rsatdi n tepaliklar uchburchak shaklida bo'lishi mumkin Θ (n) maqbul bo'lgan vaqt. Xuddi shu algoritmdan yopiq ko'pburchak zanjir oddiy ko'pburchakni tashkil etadimi yoki yo'qligini aniqlash uchun ham foydalanish mumkin.
    • Boshqa bir alohida holat badiiy galereya muammosi, bu teng ravishda minimal songa bo'linish sifatida qayta tuzilishi mumkin yulduz shaklidagi ko'pburchaklar.[7]
  • Ko'pburchaklar ustida mantiqiy amallar: Ko'pburchakli mintaqalar tomonidan belgilangan nuqtalar to'plamidagi turli xil mantiqiy amallar.
  • The qavariq korpus oddiy ko'pburchakni boshqa turdagi kirishlarning qavariq qobig'idan, masalan, nuqta to'plamining qavariq tanasidan ko'ra samaraliroq hisoblash mumkin.
  • Voronoi diagrammasi oddiy ko'pburchakning
  • Medial o'qi /topologik skelet /to'g'ri skelet oddiy ko'pburchakning
  • Ofset egri chizig'i oddiy ko'pburchakning
  • Minkovskiy summasi oddiy ko'pburchaklar uchun

Adabiyotlar

  1. ^ Grünbaum, B .; Qavariq politoplar 2nd Ed, Springer, 2003 yil
  2. ^ Dumitresku, Adrian; Tóth, Csaba D. (2007). "Doimiy geometrik kengayish bilan nurli ortogonal tarmoqlar". Tomasda, Volfgang; Vayl, Paskal (tahr.). STACS 2007: Axborot texnologiyalarining nazariy jihatlari bo'yicha 24-yillik simpozium, Axen, Germaniya, 2007 yil 22-24 fevral, Ish yuritish. (tasvirlangan tahrir). Springer. p. 177. ISBN  978-3540709176.
  3. ^ Syen-Chix Chang; Jeff Erikson; Chao Xu (2015). Yigirma oltinchi yillik ACM-SIAM diskret algoritmlari bo'yicha simpoziumi materiallari (SODA'15). 1655–1670-betlar.
  4. ^ The comp.graphics.algorithms FAQ, 2D va 3D ko'pburchaklari bilan matematik muammolarni hal qilish ro'yxati.
  5. ^ Xayns, Erik (1994). "Ko'pburchak strategiyalaridagi nuqta". Xekbertda Pol S. (tahrir). Grafika toshlari IV. San-Diego, Kaliforniya, AQSh: Academic Press Professional, Inc. pp.24–46. ISBN  0-12-336155-9.
  6. ^ Bart Breden (1986). "Surveyer maydonining formulasi" (PDF). Kollej matematikasi jurnali. 17 (4): 326–337. doi:10.2307/2686282. JSTOR  2686282. Arxivlandi asl nusxasi (PDF) 2012-11-07 kunlari.
  7. ^ a b Li, D. T. (1998). "19-bob: Hisoblash geometriyasi I". Atallohda Mixail J. (tahrir). Algoritmlar va hisoblash nazariyasi qo'llanmasi. Chapman & Hall / CRC Amaliy algoritmlar va ma'lumotlar tuzilmalari seriyasi. CRC Press. ISBN  9781420049503. Qarang "Boshqa parchalanishlar", p. 19-25.

Tashqi havolalar