CGAL Ersatz für iOS

Question

Ich habe eine Reihe von Knoten, die Straßen definieren. Jeder Knoten hat Breiten- und Längengrad. Außerdem habe ich Benutzerstandort mit Längen- und Breitengrad. Meine Absicht ist es, ein Voronoi-Diagramm für Segmente zu erstellen, die von jedem Knotenpaar definiert werden, und dann herauszufinden, welcher Knoten dem Benutzerstandort am nächsten ist.

Sieht aus wie diese Aufgabe mit CGAL-Bibliothek durchgeführt werden kann. Während ich gerade dabei bin, es für die iOS-Umgebung zu kompilieren, werden euch wahrscheinlich Links zu Libs geben, die bereits für iOS kompiliert sind oder von Anfang an in Objective-C-Umgebung verwendet werden sollten ...

Weil ich befürchte, dass, selbst wenn CGAL für mich kompiliert, ich in Schwierigkeiten geraten könnte, wenn ich es benutze. Vielen Dank!

P. S. Auch wahrscheinlich haben Sie eine bessere Lösung im Hinterkopf. Fühlen Sie sich frei, es hier zu buchstabieren.

Answer 1

Ich habe noch nie CGAL verwendet, daher kann ich nicht sagen, ob meine Lösung besser ist oder nicht.

Aber ich habe die spatialite Bibliothek verwendet, um etwas ähnliches zu tun. Spatialite läuft auf Sqlite. Wenn Sie es verwenden, ist es besser, die sqlite-Bibliothek, die mit dem iPhone geliefert wird, nicht zu verwenden, sondern einfach alles von Grund auf neu zu kompilieren mit eingeschlossenem spatialite. Sobald Sie die Daten in der Datenbank haben, können Sie einfach Funktionen wie ST_Distance verwenden, um die geschlossenen Segmente zu finden.

Spatialite verwendet R * -Tree für die räumliche Indizierung. Lookups sind sehr schnell.

Answer 2

CGAL ist ein Durcheinander (Ausschußentwurf und C++, immer gefährlich), IMHO. Es ist schwer zu durchdringen.

Aber, müssen Sie das Voronoi-Diagramm auf dem Gerät berechnen? Wenn es sich bei Ihrem Datensatz um Straßendaten handelt, ändert sich möglicherweise nicht so viel und Sie können das Gerät außerhalb des Geräts vorkonfigurieren.

Schließlich ist das Voronoi-Diagramm ein mächtiges Konstrukt, kann aber hier übertrieben sein. Wenn Sie eine große Bibliothek vermeiden möchten, kann eine einfache Heuristik ausreichen: Platzieren Sie Punkte entlang Ihrer Straßensegmente. Wenn Sie den Standort eines Benutzers angeben, finden Sie die nächstgelegenen Straßenpunkte (z. B. mit einem kd-Baum - einfach zu implementieren, schnell, viele Implementierungen verfügbar). Verwenden Sie diese, um eine Kandidatenmenge von Segmenten zu testen, um die nächste zu finden.