Hood als Polygon: Unterschied zwischen den Versionen

Aus Freifunk Franken
Wechseln zu:Navigation, Suche
KKeine Bearbeitungszusammenfassung
 
(32 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
[[File:Polygon vertices.JPG|mini|300px|Hood als Polygon]]
[[File:Polygon vertices.JPG|mini|300px|Hood als Polygon]]


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 bessere Alternative.
== Historie ==
Bisher werden die [[Hood|Hoods]] für [[KeyXchange|KeyXchange v1 und v2]] nach dem [[wikipedia:de:Voronoi-Interpolation|Voronoi-Algorithmus]] gebildet und als [[wikipedia:de:Voronoi-Diagramm|Voronoi-Diagramm]] auf der [https://monitoring.freifunk-franken.de/map Monitoring-Karte] dargestellt. Mit dem Voronoi-Algorithmus ist es aber nicht möglich, ein Gebiet exakt abzubilden. Daher wurde der keyxchange um die Polygon-Hood erweitert welcher "über" den Voronoi-Hoods liegt.


== Historie ==
== Hood als Polygon ==
Bisher werden die [[Hood|Hoods]] für [[KeyXchange|KeyXchange v1 und v2]] nach dem [[wikipedia:de:Voronoi-Interpolation|Voronoi-Algorithmus]] gebildet und als [[wikipedia:de:Voronoi-Diagramm|Voronoi-Diagramm]] auf der [https://monitoring.freifunk-franken.de/map 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.
[https://monitoring.freifunk-franken.de/map?mapcenter=49.46260,10.99418,14&source=1&layers=1,1,1,0,0,1,0 Beispiel: Fürth]


== Alternative: Hood als Polygon ==
Hoods nach nach selbst definierten Hood-Grenzen zu bilden, hat mehrere Vorteile.
Hoods nach [[wikipedia:de:Gemeinde_(Deutschland)|Gemeinden]] bzw. nach selbst definierten Hood-Grenzen zu bilden, hat mehrere Vorteile.


; Vorteile
; Vorteile
* Gemeinden sind per se soziale Gebilde
* Es können beliebig genaue Gebiete abgesteckt werden
* sie bilden Siedlungsstrukturen ab
* Es können beliebig kleine bis grosse Gebiete abgesteckt werden
* geografisch orientieren sie sich an Flusstälern, Ebenen, Verkehrswegen


; Aber
; Aber
* Funktechnik richtet sich nicht nach Gemeindegrenzen
* Meshen über Hoods hinweg ist weiterhin unmöglich <br> Bessere Alternative: [https://wiki.freifunk-franken.de/w/Dezentrale_Hood Dezentrale Hood]
* 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" ==
== Was ist ein Polygon? ==
[[Datei:Hood Schnaittachtal Polygon 11-2018.jpg|miniatur|Polygon "Schnaittachtal"]]
[[Datei:Hood Schnaittachtal Polygon 11-2018.jpg|miniatur|Polygon "Schnaittachtal"]]


<syntaxhighlight lang="JavaScript">
Jede neue Hood wird als Polygon definiert. Also eine Fläche mit Grenzpunkten und Geraden dazwischen. Die einfachste Hood ist ein Dreieck. Die Hood kann sein: Rechteck, gleichseitiges Vieleck, Stern, oder ein Polygon mit beliebig vielen Ecken und Kanten.
{ "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 [[wikipedia:de:World Geodetic System 1984|Koordinaten der Eckpunkte]], in der Reihenfoge der aneinander gezeichneten Kanten. Diese Koordinaten werden im keyxchange gespeichert, der die Berechnung übernimmt und ein API z.b. für das Monitoring bereit stellt.


Beschrieben wird das Polygon durch die [[wikipedia:de:World Geodetic System 1984|Koordinaten der Eckpunkte]], in der Reihenfoge der aneinander gezeichneten Kanten. Diese Koordinaten werden in einer [[wikipedia:de:GeoJSON|GeoJSON]]-Datei gespeichert, und können von dort zur Anzeige auf der Monitoring-Karte und natürlich in allen Programmen verwendet werden.
Damit kann theoretisch die ganze Welt abgebildet werden: <br> Alles was nicht als Polygon definiert ist, also das "Drumherum" oder das "Dazwischen", landet in der daunterliegenden Voronoi-Hood.
 
Damit kann die ganze Welt abgebildet werden: <br> 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 ==
== So gehts ==
* Zeichne ein Polygon um Dein Gebiet (kann später beliebig verfeinert werden)
* Zeichne ein Polygon um Dein Gebiet


=== Regeln ===
=== Regeln ===
[[File:Counterclockwise Arrow.svg|right|50px]]


Es gelten folgende Regeln:
Es gelten folgende Regeln:
# Linien dürfen sich nicht schneiden (weder im eigenen Polygon, noch mit Nachbarn)
# Zeichenrichtung ist egal
# erster und letzter Punkt darf nicht identisch sein, sie werden im keyxchange automatisch verbunden (weniger fehleranfällig)
# Alles was in keinen Polygon liegt, fällt in die darüber liegende voronoi Map
# Alles was in keinen Polygon liegt, fällt in die darüber liegende voronoi Map
# Polygon darf vorerst aus maximal 10 Ecken bestehen (Absprache unter keyxchange Admins, keine technische Einschränkung sondern erst mal zum Erfahrung sammeln
# Polygon darf vorerst aus maximal 10 Ecken bestehen (Absprache unter keyxchange Admins, keine technische Einschränkung sondern erst mal zum Erfahrung sammeln eine Absprache, kann später u.U. erhöht werden)
# Polygone dürfen sich nicht überschneiden
# verschiedene Polygone dürfen sich nicht überschneiden oder ein Polygon im anderen Polygon liegen. Abhängigkeiten zu voronoi bestehen nicht (voronoi dürfen überschnitten werden, es dürfen mehrere Polygone in einem voronoi liegen o.ä.)
# Polygone dürfen sich nicht in sich selbst schneiden
# Polygone dürfen sich nicht in sich selbst schneiden
=== 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 Teile der gemeinsamen Grenze zu entfernen. Anschliessend muss das Ergebnis neu in der GeoJSON gespeichert werden.


== Polygon Zeichen-Tool ==
== Polygon Zeichen-Tool ==
Zeile 80: Zeile 60:
# Speichere das Polygon über '''Menü "Datei > Speichern unter"''' als GeoJSON. <br> Gib der Datei den Namen der Hood, und wähle als '''Dateityp "GeoJSON Dateien"'''.
# Speichere das Polygon über '''Menü "Datei > Speichern unter"''' als GeoJSON. <br> Gib der Datei den Namen der Hood, und wähle als '''Dateityp "GeoJSON Dateien"'''.


== Darstellung auf der Karte ==
== Keyxchange ==
Auf der Monitoring-Karte können die Polygone als Layer dargestellt werden.
Neuer Ablauf im keychange:
 
Bisher wird dafür [[wikipedia:de:Leaflet|Leaflet]] eingesetzt.
<br> Eine Alternative wäre [[wikipedia:de:OpenLayers|OpenLayers]].
 
== Nutzung in Programmen ==
* [[#Is-in Abfrage|Is-in Abfrage (PostGIS)]]
* [[#Alternative mit MySQL|Is-in Abfrage (selbst programmiert)]]
* ...
 
== PostgreSQL und PostGIS ==
"Hood mit Polygon" und alles was dazu erforderlich ist lässt sich simpel realisieren mit [[wikipedia:de:PostgreSQL|PostgreSQL]] <br> und der Erweiterung [[wikipedia:de:PostGIS|PostGIS]] ([https://wiki.postgresql.org/images/7/7d/2011-11-11_pg.conf.de_darf_ich_vorstellen_postgis_aemde.pdf Doku de], [http://postgis.org/documentation/ Doku en], [http://trac.osgeo.org/postgis/wiki/UsersWikiMain Wiki en]).
 
Als Datenbasis dient eine Tabelle mit GeoJSON für die Hood-Polygone, und eine Tabelle der Router-Koordinaten.
 
=== von MySQL zu PostgreSQL ===
Zur Portierung der Daten aus unserer bisherigen [https://wiki.postgresql.org/wiki/Converting_from_other_Databases_to_PostgreSQL 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.
 
[https://postgis.net/docs/Topology.html Weitere PostGIS-Funktionen] erledigen fast beliebige Aufgaben im gesamten Bereich Geo-Informatik.
 
Falls der Umstieg auf PostgreSQL/PostGIS nicht erwünscht ist, müsste man die [[#Alternative mit MySQL|Funktion selber programmieren]].
 
== Hood-Polygon und Voronoi ==
[[Datei:Hood Polygon vs. Voronoi.jpg|mini|Hood-Polygon über 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,
<br> ist das der Fall wird diese genommen.
<br> Ist das nicht der Fall und wir finden im GeoJSOn System keine
gültige Hood,
<br> 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
<br> Router B liegt in keiner GeoJSON Hood, er gehört zur Voronoi Hood A
<br> Router C liegt in einer GeoJSON Hood, er gehört zur Geojson Hood C
<br> Router D liegt in einer GeoJSON Hood, er gehört zur Geojson Hood D
<br> Router E liegt in einer GeoJSON Hood, er gehört zur Geojson Hood D
<br> 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 Abfrage|"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), <br> 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) <br> auch die Hood neu bestimmen <br> 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
=== alt ===
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
# Router sendet Koordinaten an den keyxchange
weg vom "ganz groben Mittelpunkt" als der Maximalabstand den ich zuvor
# Keyxchange prüft über voronoi welche Koordinaten am nächsten liegen und gibt dazu die Hoodfile aus
ermittelt habe, wenn ja kann ich mir schon sicher sein das er nicht in
# Router konfiguriert sich nach der Hoodfile
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) ===
=== neu ===
Ich bin dabei auf [http://assemblysys.com/php-point-in-polygon-algorithm/ diese Funktion] gestolpert.


Man muss jetzt aus der GeoJson natürlich ein Array erstellen, dies hab
# Router sendet Koordinaten an den keyxchange
ich erstmal händisch gemacht (das in ne Schönform zu bringen sollte
# keyxchange prüft der Reihe nach durch in welchen Polygon der Router liegt, wenn er eins trifft gibt er direkt von dem Polygon die Hoodfile aus und wir gehen direkt zu Punkt 4), trifft kein gespeichertes Polygon in der Datenbank zu geht es weiter mit...
technisch kein Problem sein). [http://fff-jupiter.fff.community/poly/array.txt Ergebnis mit dem Bereich Simmelsdorf].
# ...Keyxchange prüft über voronoi welche Koordinaten am nähesten liegen und gibt dazu die Hoodfile aus
# Router konfiguriert sich nach der Hoodfile


Danach hab ich noch 3 Koordinaten reingeklopft gegen die ich testen will
=== Cache ===
(später würde der Router hier seine Koordinaten hinschicken und der
keyxchange schaut in welchen MultiPolygon das liegt).


=== Idee Höchstgrösse (Adrian) ===
Ein Cache, siehe [[Hood_als_Polygon/Ideen#Idee_mit_Cache_(Michael)|Hood_als_Polygon/Ideen#Idee_mit_Cache]], wurde zum aktuellen Zeitpunkt nicht implementiert. Wir wollen erstmal Erfahrung sammeln wie sich das ganze verhält und wie das System angenommen wird.
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.
[[Kategorie:Hood]]
[[Kategorie:Polygon]]

Aktuelle Version vom 26. Juli 2019, 10:27 Uhr

Hood
Hood grafisch
Dezentrale Hood
Hood V1 (alt)
[[..|Hood V2]]
- V2 Testkarte
- V2 Hood file

Hood nach Gemeinden
Hood als Polygon

Hood als Polygon

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. Mit dem Voronoi-Algorithmus ist es aber nicht möglich, ein Gebiet exakt abzubilden. Daher wurde der keyxchange um die Polygon-Hood erweitert welcher "über" den Voronoi-Hoods liegt.

Hood als Polygon

Beispiel: Fürth

Hoods nach nach selbst definierten Hood-Grenzen zu bilden, hat mehrere Vorteile.

Vorteile
  • Es können beliebig genaue Gebiete abgesteckt werden
  • Es können beliebig kleine bis grosse Gebiete abgesteckt werden
Aber
  • Meshen über Hoods hinweg ist weiterhin unmöglich
    Bessere Alternative: Dezentrale Hood

Was ist ein Polygon?

Polygon "Schnaittachtal"

Jede neue Hood wird als Polygon definiert. Also eine Fläche mit Grenzpunkten und Geraden dazwischen. Die einfachste Hood ist 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 im keyxchange gespeichert, der die Berechnung übernimmt und ein API z.b. für das Monitoring bereit stellt.

Damit kann theoretisch die ganze Welt abgebildet werden:
Alles was nicht als Polygon definiert ist, also das "Drumherum" oder das "Dazwischen", landet in der daunterliegenden Voronoi-Hood.

So gehts

  • Zeichne ein Polygon um Dein Gebiet

Regeln

Es gelten folgende Regeln:

  1. Zeichenrichtung ist egal
  2. erster und letzter Punkt darf nicht identisch sein, sie werden im keyxchange automatisch verbunden (weniger fehleranfällig)
  3. Alles was in keinen Polygon liegt, fällt in die darüber liegende voronoi Map
  4. Polygon darf vorerst aus maximal 10 Ecken bestehen (Absprache unter keyxchange Admins, keine technische Einschränkung sondern erst mal zum Erfahrung sammeln eine Absprache, kann später u.U. erhöht werden)
  5. verschiedene Polygone dürfen sich nicht überschneiden oder ein Polygon im anderen Polygon liegen. Abhängigkeiten zu voronoi bestehen nicht (voronoi dürfen überschnitten werden, es dürfen mehrere Polygone in einem voronoi liegen o.ä.)
  6. Polygone dürfen sich nicht in sich selbst schneiden

Polygon Zeichen-Tool

Zum Zeichnen der Polygone braucht man ein Werkzeug. Dieses Werkzeug ist sowohl in Leaflet, als auch in OpenLayers bereits enthalten. Das Ergebnis bekommt einen passenden Hood-Namen (z.B. den Namen der zentralen Ortschaft) und wird als GeoJSON gespeichert.

Online mit GeoJSON.io

Von GeoJSON gibt es das Online-Tool GeoJSON.io. Damit kann man intuitiv Polygone zeichnen und als GeoJSON speichern.

Offline mit JOSM

JOSM als Editor

JOSM, der Java-Editor für OSM, kann Polygone als GeoJSON speichern.

Installiere JOSM.

  1. Lade über Menü "Hintergrundbild" den Hintergrund "OpenStreetMap Carto".
  2. Zoome zu dem Bereich, wo Du das Polygon zeichenen willst.
  3. Öffne über "Menü > Neue Ebene" eine neue leere Zeichenebene.
  4. Wähle in der linken Leiste das Zeichenwerkzeug "Punkte setzen" (3. Icon von oben)
    und zeichne durch setzen von Punkten das Poplygon als geschlossene Linie.
  5. Mit dem Werkzeug "Objekte auswählen" (1. Icon von oben) kannst Du:
    die Punkte anschliessend jederzeit verschieben,
    durch ziehen an den Kreuzen zwischen zwei Punkten neue Punkte einfügen,
    mit "Entf" Punkte löschen.
  6. Speichere das Polygon über Menü "Datei > Speichern unter" als GeoJSON.
    Gib der Datei den Namen der Hood, und wähle als Dateityp "GeoJSON Dateien".

Keyxchange

Neuer Ablauf im keychange:

alt

  1. Router sendet Koordinaten an den keyxchange
  2. Keyxchange prüft über voronoi welche Koordinaten am nächsten liegen und gibt dazu die Hoodfile aus
  3. Router konfiguriert sich nach der Hoodfile

neu

  1. Router sendet Koordinaten an den keyxchange
  2. keyxchange prüft der Reihe nach durch in welchen Polygon der Router liegt, wenn er eins trifft gibt er direkt von dem Polygon die Hoodfile aus und wir gehen direkt zu Punkt 4), trifft kein gespeichertes Polygon in der Datenbank zu geht es weiter mit...
  3. ...Keyxchange prüft über voronoi welche Koordinaten am nähesten liegen und gibt dazu die Hoodfile aus
  4. Router konfiguriert sich nach der Hoodfile

Cache

Ein Cache, siehe Hood_als_Polygon/Ideen#Idee_mit_Cache, wurde zum aktuellen Zeitpunkt nicht implementiert. Wir wollen erstmal Erfahrung sammeln wie sich das ganze verhält und wie das System angenommen wird.