Hood als Polygon
|
Hood
|
Hoods geografisch und nach sozialen Gruppen zu bilden hat viele Vorteile und ist eine gute Alternative zur bisherigen Methode. Der Vorschlag Hood als Polygon entstand aus dem Vorschlag Hood nach Gemeinden und ist dazu eine Alternative.
Historie
Bisher werden die Hoods für KeyXchange v1 und v2 nach dem Voronoi-Algorithmus gebildet und als Voronoi-Diagramm auf der Monitoring-Karte dargestellt. Diese eher technische Einteilung führt aber immer wieder zu Konflikten, da sie soziale, geografische und gewachsene Gegebenheiten nur ungenügend abbildet.
Alternative: Hood als Polygon
Hoods nach Gemeinden bzw. nach selbst definierten Hood-Grenzen zu bilden, hat mehrere Vorteile.
- Vorteile
- Gemeinden sind per se soziale Gebilde
- sie bilden Siedlungsstrukturen ab
- geografisch orientieren sie sich an Flusstälern, Ebenen, Verkehrswegen
- Aber
- Funktechnik richtet sich nicht nach Gemeindegrenzen
- Communities richten sich nicht nach Gemeindegrenzen
- regionale Freifunk-Communities wissen am besten,
- mit wem sie zusammenarbeiten wollen
- wie sich die Funkwellen ausbreiten
- wie sie nachbarschaftliche Grenzen definieren
Lösung "Polygon"
<syntaxhighlight lang="JavaScript"> { "type": "Polygon",
"coordinates": [
[[30, 10], [40, 40], [20, 40], [10, 20], [30, 10]]
]
} </syntaxhighlight>
Jede neue Hood wird als Polygon definiert. Also eine Fläche, definiert mit Grenzpunkten und Geraden dazwischen. Die einfachste Hood ist also ein Dreieck. Die Hood kann sein: Rechteck, gleichseitiges Vieleck, Stern, oder ein Polygon mit beliebig vielen Ecken und Kanten.
Beschrieben wird das Polygon durch die Koordinaten der Eckpunkte, in der Reihenfoge der aneinander gezeichneten Kanten. Diese Koordinaten werden in einer GeoJSON-Datei gespeichert, und können von dort zur Anzeige auf der Monitoring-Karte und natürlich in allen Programmen verwendet werden.
Damit kann die ganze Welt abgebildet werden:
Alles was nicht als Polygon definiert ist, also das "Drumherum" oder das "Dazwischen", wird als Rest definiert und bekommt solange eine eigene Hood, bis die Ganze Welt in Polygone aufgeteilt ist.
So gehts
- Zeichne ein Polygon um Dein Gebiet (kann später beliebig verfeinert werden)
Regeln
Nachdem wir "gegen den Uhrzeigersinn" als Zeichenrichtung definiert haben, gelten folgende Regeln:
- Linien dürfen sich nicht schneiden (weder im eigenen Polygon, noch mit Nachbarn)
- idealerweise einigst Du dich mit den Nachbarn auf gemeinsame Grenzen
Lücken zwischen Grenzen sind aber erlaubt - Polygone können (in Absprache mit betroffenen Nachbarn) beliebig verändert werden
- Polygone können geteilt oder zusammengefügt werden
Teilen
Jedes Polygon kann durch Einfügen einer Trennlinie in zwei neue Polygone aufgeteilt werden. Dabei ist zu beachten, dass sich keine Linien kreuzen. Anschliessend muss das Ergebnis neu in der GeoJSON gespeichert werden.
Zusammenfügen
Zusammengefügt werden können Polygone mit gemeinsamen Grenzen. Dazu sind Teie der gemeinsamen Grenze zu entfernen. Anschliessend muss das Ergebnis neu in der GeoJSON gespeichert werden.
Darstellung auf der Karte
Auf der Monitoring-Karte können die Polygone als Layer dargestellt werden.
Bisher wird dafür Leaflet eingesetzt.
Eine Alternative wäre OpenLayers.
Nutzung in Programmen
PostgreSQL und PostGIS
"Hood mit Polygon" und alles was dazu erforderlich ist lässt sich simpel realisieren mt PostgreSQL und der Erweiterung PostGIS. Als Datenbasis dient eime GeoJSON für die Hood-Polgone und eine Liste der Router-Koordinaten.
von MySQL zu PostgreSQL
Zur Portierung der Daten aus unserer bisherigen MySQL-DB zu PostgreSQL gibt es mehrere freie Tools. Gut geeignet für unseren Zweck ist beispielsweise ...
Is-in Abfrage
PostGIS "weiss" in welchem Polygon eine Koordinate liegt.
Die Abfrage, in welcher Hood sich ein Router befindet, ist in einer PostgreSQL/PostGIS-DB ganz simpel und performant. In PostGIS gibt es dafür die [ Funktion "is-in"], die die Abfrage direkt in der DB prüft. Es ist also kein weiterer Programmieraufwand erforderlich.
Der Router schickt wie bisher seinen Standort als Koordinate, und "is-in" liefert blitzschnell die Hood als Ergebnis. Damit ist wie bisher das zuständige Gateway definiert.
Falls der Umstieg auf PostgreSQL/PostGIS nicht erwünscht ist, müsste man die Funktion selber programmieren.
Hood-Polygon und Voronoi
Christian schlägt vor:
Das neue System der Hood-Polygone liegt über dem bisherigen Voronoi-System.
Erst wird geprüft ob die Koordinaten irgendwo in einer GeoJSON Hood liegen,
ist das der Fall wird diese genommen.
Ist das nicht der Fall und wir finden im GeoJSOn System keine
gültige Hood,
dann machen wir mit Voronoi weiter.
So könnte das theoretisch aussehen (kein reales Beispiel):
Router A liegt in keiner GeoJSON Hood, er gehört zur Voronoi Hood B
Router B liegt in keiner GeoJSON Hood, er gehört zur Voronoi Hood A
Router C liegt in einer GeoJSON Hood, er gehört zur Geojson Hood C
Router D liegt in einer GeoJSON Hood, er gehört zur Geojson Hood D
Router E liegt in einer GeoJSON Hood, er gehört zur Geojson Hood D
Router F liegt in keiner GeoJSON Hood, er gehört zur Voronoi Hood B
Alternative mit MySQL
Wenn es für MySQL keine "is-in" Funktion gibt, müsste man das selber programmieren.
Idee Statisch (Markus)
Wenn man "is-in" nicht direkt in der DB in "Echtzeit" prüfen will (z.B. mit PostGIS),
könnte man:
- einmal von allen Routern die Koordinate auslesen,
- für jede Koordinate prüfen, in welcher Hood der Router liegt,
- und die Zuordnung in eine Tabelle schreiben.
Dann bräuchte man bei Anfragen nur in der Tabelle nachschauen.
Das bedeutet, dass man:
- bei jedem neuen Router (bzw. bei jeder Koordinaten-Änderung)
auch die Hood neu bestimmen
und in der Tabelle ergänzen müsste.
Dann wäre die Tabelle immer bis auf wenige Minuten aktuell.
Idee mit Cache (Michael)
Man könnte die Anfragen auch einfach cachen, weil sie immer wieder gleich kommen und sich nur geringfügig ändern.
Idee mit Cache (Christian)
(vermutlich das gleiche wie Michael weiter oben nur tiefergehend ausgeführt)
Wir legen im keyxchange eine weitere Tabelle an, wo wir die GeoDaten zu jeder Polygon-Hood abspeichern. Jeder GeoDatensatz verweist dann zu einer HoodID die wir ganz normal in die bereits vorhandene Hood Tabelle speichern. Die Hoodtabelle braucht dann noch ein Flag PolygonHood oder voronoiHood so das bei der voronoi Berechnung die PolygonHood nicht getestet wird.
Das hat auch den Vorteil, das mehrere Polygone auf eine Hood verweisen können (Schnaittach, Simmelsdorf und noch irgendwas verweist alles auf die Hood Schnaittach)
Im Cache würde ich dann "nur" noch lat, lon und HoodID abspeichern, der Cache muss gar nicht wissen ob es eine voronoi oder PolygonHood ist, die HoodID reicht.
Sobald man 1x irgendwas an irgendeiner Hood ändern, muss der Cache natürlich komplett geleert werden und wieder frisch aufgebaut werden. Das kann man wunderbar vor, bzw nach den ganzen Berechnung machen. Bevor man mit den Berechnen anfängt, fragt man die lat/lon die der Router gesendet hat im Cache ab, gibt es die hat man direkt die HoodID und kann die Hood den Router geben. Gibt es die nicht, führt man die komplette Berechnung durch und speichert am Ende in den Cache lat, lon und HoodID ab damit sie für den nächsten durchlauf zur Verfügung stehen.
Ja es ist ein zusätzlicher Fehler aber ich seh das nicht als kritisch an, wenn man den Cache leert falls man eine Hood anlegt oder ändert sollte eigentlich nichts passieren. Aktualisieren oder so muss man nie was, auch ist es egal zu welchen System der Cache gehört, nur eben den Cache komplett leeren (man könnte natürlich auch nur den Bereich leeren um den es sich handelt aber da wäre mir das Fehlerrisiko zu hoch, 1x den Cache komplett neu aufbauen geht schon) wenn man was an den Hoods ändert.
Idee mit Punkt (Christian)
Ich definieren einen Punkt der so ganz grob irgendwo in der Mitte des Polygons liegt (muss nicht exakt sein, theoretisch geht auch ein Punkt am Rand, besser wirds je nähe man zur Mitte kommt). Dann schau ich wie groß der Abstand von meinen zuivor definierten Punkt zum Rand am weitesten entfernen Punkt ist und speichere diesen Abstand.
Danach prüfe ich erstmal, ist die gesendete Koordinate vom Router weiter weg vom "ganz groben Mittelpunkt" als der Maximalabstand den ich zuvor ermittelt habe, wenn ja kann ich mir schon sicher sein das er nicht in diesen Polygon liegt und brauch die ganze Berechnung nicht durchlaufen. Erst wenn er näher dran ist, muss ich noch die ganze Berechnung machen damit ich genau weiß ob er drinnen liegt oder nicht.
Idee mit PHP (Christian)
Ich bin dabei auf diese Funktion gestolpert.
Man muss jetzt aus der GeoJson natürlich ein Array erstellen, dies hab ich erstmal händisch gemacht (das in ne Schönform zu bringen sollte technisch kein Problem sein). Ergebnis mit dem Bereich Simmelsdorf.
Danach hab ich noch 3 Koordinaten reingeklopft gegen die ich testen will (später würde der Router hier seine Koordinaten hinschicken und der keyxchange schaut in welchen MultiPolygon das liegt).
Idee Höchstgrösse (Adrian)
Man könnte für die Gemeinde-Hoods eine Höchstgröße festlegen (= ± Winkelbruchteile).
Bevor man dann das Polygon hernimmt, könnte man für jede Hood sehr billig prüfen, ob die Koordinaten in den Bereich plus/minus der Höchstabweichung liegen. Wenn außerhalb, dann einfach weiter. Selbst wenn man die Größe sehr hoch wählt, sollte so ein beachtlicher Geschwindigkeitsgewinn zu holen sein.
