Hood-Bildung - Gemeindegrenzen

Mi Sep 19 22:52:28 CEST 2018

hi

On 19.09.2018 20:07, mail at adrianschmutzler.de wrote:
> Hallo,
> 
> eine Idee zur Performance:
> 
> Man könnte für die Gemeinde-Hoods eine Höchstgröße festlegen (= +/- Winkelbruchteile).

im Prinzip so:

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.

Versteh ich das so richtig?

mfg

Christian

> 
> 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.
> 
> Grüße
> 
> Adrian
> 
>> -----Original Message-----
>> From: franken [mailto:franken-bounces at freifunk.net] On Behalf Of
>> Christian Dresel
>> Sent: Mittwoch, 19. September 2018 12:39
>> To: michael at fritscher.net; Freifunk Franken <franken at freifunk.net>
>> Subject: Re: Hood-Bildung - Gemeindegrenzen
>>
>> hi
>>
>> On 19.09.2018 12:14, michael at fritscher.net wrote:
>>> Moin,
>>>
>>> kurz: klingt lecker :-) Danke fürs Ausprobieren!
>>>
>>> 2 Anmerkungen:
>>>
>>> 1. Die Umrüstung von mysql auf pqsql dürfte eigentlich recht einfach
>>> machbar sein, gerade beim v2 Keyxchange. Ist mir aber egal, wenn die
>>> php Variante auch gut funktioniert (scheint sie ja bisher).
>>
>> ich weiß nicht, so ein großer Umbau auf ein System das zumindest ich gar
>> nicht verstehe finde ich unschön. Wenn die restlichen keyxchange Admins
>> alle sagen "Joa psql, kein Problem, kann ich, machen wir" dann wegen mir
>> aber ich bin eher dagegen mich da jetzt in nen neue System einzuarbeiten
>> und wenn du dann der einzige bist der psql kann... Ne sorry dann Veto.
>>
>>> 2. Was sagt die Performance? Du könntest ja mal Schaittach 100x auf
>>> die Karte klatschen, immer bissle verschoben, und gucken was passiert,
>>> wenn alle durchgeschaut werden. Wenn das max. 2-3 Sekunden dauert
>>> könnte man das durch einen Cache ablindern. Wir haben ja nur
>>> Größenordnung 5k Router, also 5k unterschiedliche Koords, da könnte
>>> man die
>>> Koord->Hoodzuordnung speichern. Der Cache würde dann halt bei
>>> Hoodänderungen geleert werden.
>>
>> 1000 Durchläufe durch ein gleiches Polygonen mit jeweils 3 abfragen (also
>> eigentlich 3000 Abfragen, ein Router sendet ja nur einen
>> Koordinantensatz):
>>
>> http://fff-jupiter.fff.community/poly/speed.php
>>
>> ca. 10-11 Sekunden Scriptlaufzeit auf meiner VM (siehe ganz am Ende der
>> Ausgabe), ich denke damit können wir leben, es fragen ja "nur" die
>> Uplinkrouter an und das auch nur alle 5 Minuten.
>>
>> mfg
>>
>> Christian
>>
>>>
>>> Grundsätzlich wäre ich klar für weiter ausprobieren :-)
>>>
>>> Viele Grüße und Danke,
>>> Michael Fritscher
>>>
>>>
>>>
>>> Am 2018-09-19 11:52, schrieb Christian Dresel:
>>>> hi
>>>>
>>>> um gegen ein System zu sein, sollte man ein System erstmal verstehen.
>>>> Bisher war ich dagegen, weil ich dachte es ist zu aufwendig. Aber hey
>>>> ich spiel doch gerne mit Technik und so hab ich mal bisschen
>>>> herumprobiert.
>>>> Mein Ergebniss möchte ich nun mal der Community vorstellen und würde
>>>> mich über bisschen Feedback (sowohl technisch als auch nicht
>>>> technisch) freuen.
>>>>
>>>> Ich hab Markus seine Anleitung erstmal soweit abgearbeitet das ich
>>>> eine GeoJson File von Schnaittach (und Simmelsdorf und noch irgendein
>>>> Nachbarort den Markus genannt hat) lokal hatte, das sieht dann so aus:
>>>>
>>>> http://fff-jupiter.fff.community/schnaittach.GeoJson
>>>>
>>>> Hier drinnen ist bereits für jeden Ort ein MultiPolygon (keine Ahnung
>>>> ob das der richtige Begriff ist, aber so wird es hier genannt) enthalten.
>>>>
>>>> Nun ist der Punkt von Markus "Ist-in-Abfrage" allerdings nicht ganz
>>>> leicht umzusetzen, der keyxchange hat keine PostgreSQL und das
>>>> nachzurüsten uff... Will ich mir eigentlich ersparen. Also hab ich
>>>> mal geguckt wie ich das in PHP (damit ist der keyxchange geschrieben)
>>>> einfacher lösen kann. Ich bin dabei auf diese Funktion gestolpert:
>>>>
>>>> http://assemblysys.com/php-point-in-polygon-algorithm/
>>>>
>>>> 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) mit dem Bereich Simmelsdorf,
>>>> sieht dann so aus:
>>>>
>>>> http://fff-jupiter.fff.community/poly/array.txt
>>>>
>>>> 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):
>>>> 11.339509 49.559324
>>>> 11 49
>>>> 11.327267 49.618443
>>>>
>>>> Im moment sich lat/lon noch verdreht, da die MultiPolygon so
>>>> aufgebaut ist, hab ich erstmal damit gearbeitet. Das Ergebnis sieht dann
>> so aus:
>>>>
>>>> http://fff-jupiter.fff.community/poly/index.php
>>>> (Sourcecode kann hier angeguckt werden:
>>>> http://fff-jupiter.fff.community/poly/index.txt )
>>>>
>>>> Man sieht, die Funktion arbeitet auch mit Koordinanten korrekt, die
>>>> ersten 2 Koordinaten liegen eindeutig nicht im Bereich Simmelsdorf,
>>>> die 3. aber schon.
>>>>
>>>> So wie könnte man dies nun technisch in den keyxchange klopfen:
>>>>
>>>> Schritt 1) Der Knoten schickt seine Koordinaten an den keyxchange.
>>>> Schritt 2) wir prüfen die Koordinaten gegen alle (ich nenn dieses
>>>> Hoodsysten jetzt mal frech so) GeoJson-Hood. Passen die Koordinaten
>>>> des Knoten in eine dieser vorhandenen GeoJson-Hoods, wird diese Hood
>>>> an den Knoten zurückgegeben und er konfiguriert sich auf diese Hood
>>>> falls sie in keine GeoJson-Hood passen, machen wir mir Schritt 3
>>>> weiter ansonsten endet hier der Ablauf bereits Schritt 3) wir prüfen
>>>> wie jetzt auch schon, zu welcher voronoi Hood der Knoten gehört und
>>>> geben ihn diese Hood zurück.
>>>>
>>>> Bisher arbeitet der Keyxchange nur mit Schritt 1 und 3, man würde
>>>> also einen Schritt 2 "dazwischen" schieben.
>>>>
>>>> Vorteile:
>>>> - Wer GeoJson verwenden will, kann dies tun. Wer es nicht tun will
>>>> bleibt einfach bei den alten voronoi System, es ist die freie
>>>> Entscheidung jedermann (und das ist mir persönlich sehr wichtig)
>>>> - Das GeoJson System liegt "über" den voronoi System. Somit werden
>>>> Hoods die aktuell nach voronoi arbeiten absolut nicht beeinflusst
>>>> sofern "da drinnen" niemand eine Geo-Json Hood anlegt. Die Systeme
>>>> können also wunderbar pararell agieren
>>>>
>>>> Nachteil:
>>>> - Das Zeug muss man erstmal umsetzen
>>>> - Der Wartungsaufwand vom keychange steigt etwas an, man muss auf
>>>> noch mehr Sachen acht geben
>>>>
>>>> So Meinungen? Was meint ihr? Umsetzbar? Sollen wir es probieren? Hab
>>>> ich Dinge übersehen?
>>>>
>>>> mfg
>>>>
>>>> Christian
>>>>
>>>> On 06.09.2018 09:46, fff at mm.franken.de wrote:
>>>>> Moin Michael,
>>>>>
>>>>>>> Markus, wir können uns da gerne mal (virtuell oder physikalisch)
>>>>>>> zamhocken und da was zusammenbrauen ;-)
>>>>>
>>>>> Habe mal etwas Doku zusammengetragen:
>>>>> https://wiki.freifunk-franken.de/w/Hood_nach_Gemeinden
>>>>>
>>>>> Vielleicht hilft das Dir und anderen Hood-Profis ja ein bisschen?
>>>>>
>>>>> Rückfragen gern per Mail oder telefonisch.
>>>>>
>>>>> Mit herzlichem Gruss,
>>>>> Markus
>>>>>
> 