Polygon-Zerlegung

Version 12 biete die neue Funktion PolygonDecomposition, um Polygone in eine Vereinigung einfacherer Polygone – wie Dreiecke, einfache und konvexe Polygone – zu zerlegen. Anwendungsgebiete sind beispielsweise Computergeometrie, Mustererkennung, Bildverarbeitung und Computergrafik.

Lösen Sie das Problem der Museumswächter: Bewachen Sie eine Kunstgalerie mit der minimalen Anzahl von Wachen, die zusammen die gesamte Galerie beobachten können. Erstellen Sie zunächst ein einfaches Polygon aus dem Galeriegrundriss.

Zerlegen Sie den Grundriss in Dreiecke.

Erstellen Sie einen Sichtbarkeitsgraphen aus der Polygonzerlegung.

Ermitteln Sie die dominierende Menge des Graphen.

Wählen Sie die Wachmänner der Farbe, die am seltensten vorkommt, aus und zeigen Sie deren Positionen an.