Computergeometrie: Erforschung geometrischer Erkenntnisse für Computer Vision

Von Fouad Sabry

Was ist Computergeometrie

Computergeometrie ist ein Zweig der Informatik, der sich der Untersuchung von Algorithmen widmet, die in Form von Geometrie ausgedrückt werden können. Einige rein geometrische Probleme ergeben sich aus der Untersuchung rechnerischer geometrischer Algorithmen, und solche Probleme werden auch als Teil der rechnerischen Geometrie betrachtet. Während die moderne Computergeometrie eine junge Entwicklung ist, ist sie eines der ältesten Gebiete der Informatik mit einer Geschichte, die bis in die Antike zurückreicht.

Wie Sie davon profitieren werden

(I) Erkenntnisse und Validierungen zu den folgenden Themen:

Kapitel 1: Computergeometrie

Kapitel 2: Delaunay-Triangulation

Kapitel 3: Konvexe Hülle

Kapitel 4: Voronoi-Diagramm

Kapitel 5: Diskrete Geometrie

Kapitel 6: Polygontriangulation

Kapitel 7: Euklidischer minimaler Spannbaum

Kapitel 8: Einfaches Polygon

Kapitel 9: Punktmengen-Triangulation

Kapitel 10: Triangulation (Geometrie)

(II) Antworten Die häufigsten Fragen der Öffentlichkeit zur Computergeometrie.

(III) Beispiele aus der Praxis für die Verwendung der Computergeometrie in vielen Bereichen.

Für wen dieses Buch gedacht ist

Profis, Studenten und Doktoranden, Enthusiasten, Hobbyisten und diejenigen, die über Grundkenntnisse oder Informationen für jede Art von Computergeometrie hinausgehen möchten.

 

 

• Sprache: Deutsch
• Herausgeber: Eine Milliarde Sachkundig [German]
• Erscheinungsdatum: 4. Mai 2024

Buchvorschau

Kapitel 1: Numerische Geometrie

Computergeometrie ist ein Bereich der Informatik, der sich der Untersuchung von Algorithmen widmet, die in geometrischen Begriffen ausgedrückt werden können. Diese Probleme werden auch als Teil der Computergeometrie angesehen. Trotz der Tatsache, dass die moderne Computergeometrie ein relativ junges Phänomen ist, ist sie eines der ältesten Themen der Informatik, dessen Geschichte bis in die Antike zurückreicht.

Zentral für die Computergeometrie ist die Rechenkomplexität, wenn Methoden auf sehr große Datensätze angewendet werden, die Dutzende oder Hunderte von Millionen Punkten enthalten, hat dies einen enormen praktischen Wert.

In solchen Fällen kann die Differenz zwischen O(n2) und O(n log n) die Differenz zwischen Tagen und Sekunden der Berechnung sein.

Fortschritte in der Computergrafik und der computergestützten Konstruktion und Fertigung (CAD/CAM) lieferten die Hauptmotivation für die Entwicklung der Computergeometrie als Fach, jedoch sind viele Probleme in der Computergeometrie klassischer Natur und können ihren Ursprung in der mathematischen Visualisierung haben.

Robotik (Bewegungsplanung und Sichtbarkeitsprobleme), Geographische Informationssysteme (GIS) (geometrische Lokalisierung und Suche, Routenplanung), integrierter Schaltungsentwurf (IC-Geometrieentwurf und -verifizierung), Computer-Aided Engineering (CAE) (Netzgenerierung) und Computer Vision sind weitere wichtige Anwendungen der Computergeometrie (3D-Rekonstruktion).

Zu den wichtigsten Zweigen der Computergeometrie gehören:

Die kombinatorische Computergeometrie, oft auch als algorithmische Geometrie bezeichnet, befasst sich mit diskreten geometrischen Objekten. Der Begriff computergestützte Geometrie wurde erstmals 1975 in diesem Sinne verwendet, wie aus einem bahnbrechenden Buch von Preparata und Shamos zu diesem Thema hervorgeht.

Die numerische Computergeometrie, auch bekannt als Maschinengeometrie, Computer-Aided Geometric Design (CAGD) oder geometrische Modellierung, befasst sich weitgehend mit der Darstellung realer Objekte in CAD/CAM-Systemen. Dieser Zweig kann als Fortsetzung der deskriptiven Geometrie angesehen werden und wird häufig als Teilgebiet der Computergrafik oder des CAD kategorisiert. Seit 1971 wird in diesem Sinne der Begriff Computational Geometry verwendet.)

Das primäre Ziel der kombinatorischen computergestützten Geometrieforschung ist die Entwicklung effizienter Algorithmen und Datenstrukturen zur Lösung von Problemen, die in Form grundlegender geometrischer Objekte wie Punkte, Liniensegmente, Polygone und Polyeder ausgedrückt werden.

Bis zum Aufkommen von Computern wurden einige dieser Probleme überhaupt nicht als Probleme angesehen, da sie so einfach zu sein scheinen. Betrachten wir als Beispiel das Problem des engsten Paares:

Finde die beiden Punkte in der Ebene mit dem kürzesten Abstand zueinander, wenn n Punkte in der Ebene gegeben sind.

Man könnte die Abstände zwischen jedem Punktpaar bestimmen, welche Anzahl es n(n-1)/2 gibt, und dann das Paar mit dem kürzesten Abstand wählen.

Dieser Brute-Force-Algorithmus benötigt O(n2) Zeit, d.h.

Die Ausführungszeit ist proportional zur Anzahl der Punkte zum Quadrat.

Ein grundlegendes Ergebnis der Computergeometrie war die Entwicklung eines Algorithmus, der O (n log n) benötigt.

Randomisierte Algorithmen mit einer erwarteten Laufzeit von O(n) wurden zusätzlich entdeckt.

Die grundlegenden Probleme der Computergeometrie lassen sich anhand mehrerer Kriterien unterschiedlich kategorisieren. Folgende große Kategorien können unterschieden werden:.

In dieser Kategorie von Problemen wird ein Input bereitgestellt, und der entsprechende Output muss erstellt oder bestimmt werden. Zu den grundlegenden Problemen dieser Art gehören:

Konvexe Hülle: Suchen Sie anhand einer Reihe von Punkten das kleinste konvexe Polyeder/Polygon, das alle Punkte enthält.

Schnittpunkt von Liniensegmenten: Bestimmen Sie die Schnittpunkte zwischen einer bestimmten Sammlung von Liniensegmenten.

Delaunay-Triangulation

Wenn Sie eine Reihe von Punkten angegeben haben, teilen Sie den Raum nach den Punkten auf, die den angegebenen Punkten am nächsten sind, indem Sie das Voronoi-Diagramm verwenden.

Lineare Programmierung

Ermitteln Sie anhand einer Sammlung von Punkten das Paar, das den geringsten Abstand zwischen ihnen hat.

Entferntestes Punktpaar

Finde bei einer gegebenen Menge von Punkten den größten Kreis, dessen Mittelpunkt innerhalb ihrer konvexen Hülle liegt und keinen von ihnen umschließt.

Verbinde zwei Punkte in einem euklidischen Raum (mit polyedrischen Hindernissen) auf dem kürzesten Weg.

Wenn ein Polygon gegeben ist, triangulieren Sie sein Inneres, indem Sie es in Dreiecke unterteilen.

Generierung von Netzen

Boolesche Operationen, die auf Polygone angewendet werden

Die Rechenkomplexität dieser Klasse von Problemen wird basierend auf der Zeit und dem Raum (Computerspeicher) bewertet, die zur Lösung einer bestimmten Instanz des Problems erforderlich sind.

Bei geometrischen Abfrageproblemen, die auch als geometrische Suchprobleme bezeichnet werden, besteht die Eingabe aus zwei Komponenten: der Suchraumkomponente und der variablen Abfragekomponente. In der Regel muss der Suchraum vorverarbeitet werden, damit viele Abfragen effizient bearbeitet werden können.

Eine Reihe grundlegender geometrischer Fragestellungen sind:

Verarbeiten Sie eine Gruppe von Punkten vorab, um die Anzahl der Punkte innerhalb eines Abfragebereichs schnell zu zählen.

Erstellen Sie eine Datenstruktur, die die Zelle, in der sich ein Abfragepunkt befindet, effizient identifiziert, wenn der Bereich zellenbasiert partitioniert wird.

Nächster Nachbar: Verarbeiten Sie eine Reihe von Punkten vorab, um schnell den Punkt zu bestimmen, der einem Abfragepunkt am nächsten liegt.

Raytracing: Generieren Sie bei einer Reihe von Elementen im Raum eine Datenstruktur, die das erste Objekt, mit dem sich ein Abfragestrahl überschneidet, effizient identifiziert.

Wenn der Suchraum fest ist, wird die Rechenkomplexität dieser Klasse von Problemen häufig anhand folgender Werte bewertet:

Die Menge an Zeit und Speicherplatz, die erforderlich sind, um die zu durchsuchende Datenstruktur zu erstellen.

Zeit (und gelegentlich zusätzlicher Platz), um Fragen zu beantworten.

Beziehen Sie sich auf Dynamische Probleme, wenn der Suchraum schwanken darf.

Eine weitere wichtige Klasse sind die dynamischen Probleme, für die es darum geht, eine effektive Technik zu entwickeln, mit der nach jeder Aktualisierung der Eingabedaten (Hinzufügen oder Löschen von geometrischen Eingabeelementen) wiederholt eine Lösung gefunden werden kann. In der