Seznam témat kombinatorické výpočetní geometrie - List of combinatorial computational geometry topics

Seznam témat kombinatorické výpočetní geometrie vyjmenovává témata výpočetní geometrie který uvádí problémy z hlediska geometrických objektů jako oddělený entity a tedy metody jejich řešení jsou většinou teorie a algoritmy z kombinační charakter.

Vidět Seznam témat numerické výpočetní geometrie pro další příchuť výpočetní geometrie, která se zabývá geometrickými objekty jako spojitými entitami a aplikuje na ně metody a algoritmy přírodní charakteristiky numerická analýza.

Konstrukce / reprezentace

• Booleovské operace s polygony
• Konvexní obal
• Uspořádání hyperplánu
• Polygonový rozklad
  • Polygon triangulace
    • Minimální konvexní rozklad
    • Minimální konvexní kryt problém (NP-tvrdé )
    • Minimální obdélníkový rozklad
  • Mozaikování problémy
• Tvarová disekce problémy
• Rovná kostra
• Problém s bodnou čárou
• Triangulace
  • Delaunayova triangulace
  • Bodová triangulace
  • Polygon triangulace
• Voronoiho diagram

Extrémní tvary

• Minimální ohraničující rámeček (Nejmenší uzavírací krabička, Nejmenší ohraničující rámeček )
  • 2-D pouzdro: Nejmenší ohraničující obdélník (Nejmenší uzavírací obdélník )
  • Existují dvě běžné varianty tohoto problému.
    • V mnoha oblastech počítačové grafiky ohraničující rámeček (často zkráceně na bbox) se rozumí nejmenší rámeček ohraničený stranami rovnoběžnými s koordinačními osami, které uzavírají dotyčné objekty.
    • V jiných aplikacích, jako je obal, problém je najít nejmenší rámeček, do kterého se objekt (nebo objekty) vejde („zabalený“). Zde může rámeček zaujmout libovolnou orientaci vzhledem k „zabaleným“ objektům.
• Nejmenší ohraničující koule (Nejmenší obklopující koule)
  • 2-D pouzdro: Nejmenší ohraničující kruh
• Největší prázdný obdélník (Maximální prázdný obdélník )
• Největší prázdná koule
  • 2-D pouzdro: Maximální prázdný kruh (největší prázdný kruh )

Interakce / vyhledávání

• Detekce kolize
• Průsečík úsečky
• Umístění bodu
  • Bod v mnohoúhelníku
• Křižovatka mnohoúhelníků
• Hledání rozsahu
  • Hledání ortogonálního rozsahu
  • Simplexní vyhledávání rozsahu
• Ray casting (nezaměňovat s sledování paprsku počítačové grafiky)

Problémy s blízkostí

• Nejbližší pár bodů
• Problém nejbližšího bodu
• Průměr množiny bodů
• Delaunayova triangulace
• Voronoiho diagram

Viditelnost

• Viditelnost (geometrie)
• Problém s uměleckou galerií (Problém muzea )
• Graf viditelnosti
• Problém s hlídačem
• Aplikace počítačové grafiky:
  • Skryté stanovení povrchu
  • Odstranění skryté linky
• Ray casting (nezaměňovat s sledování paprsku počítačové grafiky)

jiný

• Šťastný konec problému
• Šunkový sendvičový problém
• tvarová sestava problémy
• shoda tvaru problémy
• Kleeův problém s měřením
• Problémy na izotetické polygony a izotetická mnohostěna
  • Ortogonální konvexní trup
• Plánování cesty
  • Cesty mezi překážkami
  • Nejkratší cesta v mnohoúhelníku
• Omezení polygonů
• Robustní geometrický výpočet řeší dva hlavní problémy: vyjádření pevné přesnosti reálná čísla v počítačích a možné geometrické degenerace (matematika) vstupních údajů