{"id":3935,"date":"2019-01-03T21:54:14","date_gmt":"2019-01-03T20:54:14","guid":{"rendered":"http:\/\/roboblog.fatal-fury.de\/?p=3935"},"modified":"2019-01-04T01:23:45","modified_gmt":"2019-01-04T00:23:45","slug":"punktewolke-paarweiser-abstand-symmetrien-entdecken","status":"publish","type":"post","link":"http:\/\/roboblog.fatal-fury.de\/?p=3935","title":{"rendered":"Punktewolke Paarweiser Abstand - Symmetrien entdecken"},"content":{"rendered":"

Ich habe mir letztens, aus gegebenen Anlass, die wunderbare Weihnachtsvorlesung von Dr. Edmund Weitz angesehen und bin gegen Ende im dritten Teil stecken geblieben.
\nDie Poincar\u00e9-Vermutung (Teil 3 von 3, Weihnachtsvorlesung 2018)<\/a>
\nEs wurde die Frage gestellt, Wie sieht das Leben auf einem Torus aus?<\/a>
\nIch mach es kurz: Wenn das Universum ein Torus w\u00e4re (in h\u00f6herer Dimension versteht sich), dann w\u00e4re es endlich, ohne Rand. Man k\u00f6nnte in eine Richtung schauen und w\u00fcrde irgendwann sich selbst von Hinten sehen. Und wenn man noch weiter schaut, sieht man sich selbst noch einmal, und noch einmal u.s.w. Nat\u00fcrlich ist die Sicht immer etwas verzerrt.
\nDamit ergibt auch folgender Satz Sinn: Das Universum ist kleiner als das was wir sehen k\u00f6nnen. Bzw.: Das beobachtbare Universum ist gr\u00f6\u00dfer als das eigentliche. <\/p>\n

Wie auch immer, zur Veranschaulichung wurde in 2D einige Punkte erstellt, nach rechts\/links\/oben\/unten kopiert und von jedem Punkt zu jedem anderen den Abstand ermittelt und davon ein Histogramm erzeugt. Sieht etwa bei Minute 31:30<\/a>.
\nDer Witz ist nun folgender: Gibt es keine sich wiederholende Muster, ist eine Poison Verteilung sichtbar. Gibt es solche Muster, hat die Verteilung Peaks.<\/p>\n

Na, das l\u00e4sst sich doch wunderbar auf ein Digitales Gel\u00e4ndemodell (DGM) anwenden!<\/p>\n

In der Regel sind die Punkte aus unstrukturierte Laserscans ziemlich dicht verteilt. Es gibt Bereiche an denen sich mehr Messpunkte befinden. Das Flugzeug fliegt die Landschaft ja hin und her ab, und da gibt es \u00dcberlappungen. Auch bei der ersten Nachbearbeitung der Daten passieren magische Dinge. Ich habe also keine Ahnung wie das Histogramm aussieht und bin sehr gespannt.<\/p>\n

Als Datensatz fand ich von Open Geodata NRW<\/a> viele DGMs. Die kleinste Datei dgm1l_05974056_Wickede_Ruhr_EPSG25832_XYZ.zip beinhaltete aber immer noch viele GB an Daten. Also nutze ich nur die Kachel 32420_5705 mit 1812468 (1.8M) Punkten.<\/p>\n

So sieht die H\u00f6henverteilung aus:
\n\"32420_5707_hoehen\"<\/a><\/p>\n

Und hier die Punktverteilung. Nur an einigen wei\u00dfen Stellen sind nicht so viele Punkte vorhanden.
\n\"32420_5707_punktwolke\"<\/a><\/p>\n

Als n\u00e4chstes schrieb ich ein Programm welches die Punkte einliest, in einer quadratischen Schleife alle Punkt Abst\u00e4nde berechnet und on-thy-fly ein Histogramm mit den ersten drei Momenten erzeugt. Dabei werden die Abst\u00e4nde zweier Punkte nur einmal berechnet. Also von Punkt A zu B. Aber nicht von B zu A. Der ist ja der selbe. Damit ergeben sich 1642 Milliarden Abstandsberechnungen. Um die alle zu speichern, br\u00e4uchte man 12233 GB an Speicherplatz. Den habe ich nicht. Daher habe ich ein Histogramm entwickelt, welches kontinuierlich mit Daten erstellt werden kann.<\/p>\n

Auch die Laufzeit ist bei diesen Algorithmus ein Problem. Also berechne ich nur den quadratischen Abstand. Das spart eine Wurzel Berechnung. Und in der Summe ist das schon was. Zus\u00e4tzlich gibt es noch ein Point2D mit SIMD\/SSE F\u00e4higkeiten. Dies spart noch ein paar Operationen pro Abstands Berechnung.<\/p>\n

Auf einem 4GHz CPU dauerte die Berechnung drei Stunden. F\u00fcr einen doppelt so gro\u00dfen Datensatz sind es schon 9 Stunden. Und f\u00fcr nicht un\u00fcbliche 100M Punkte w\u00fcrde es ca. 12 Monate dauern. Immerhin noch realistisch. <\/p>\n

Aber wie sieht nun das Histogramm aus? Nicht vergessen: Das sind quadratische Abst\u00e4nde. In Klammern die Wurzel aus den Werten.<\/p>\n

\r\nMin: 0\r\nAvg: 3.31e+05 (575.3) \r\nMax: 2e+06    (1414.2)\r\nVar: 7.71e+10 (277668.9)\r\nStd 2.78e+05  (527.3)\r\n<\/pre>\n
Der minimaler Abstand von 0 deutet auf doppelte Punkte hin. Das ist nicht ungew\u00f6hnlich.
\nDer maximale Abstand ist gerade die L\u00e4nge der Diagonalen der Boundingbox von jeweils 1km Seitenl\u00e4nge. Auch richtig.
\nDer mittlere Abstand ist auch okay. Stelle ich mich gedanklich in die Mitte der BB, habe ich nach allen Seiten mehr als 500m Platz.<\/p>\n
\"hist200_1\"<\/a><\/p>\n
Mit Logscale
\n\"hist200_2\"<\/a><\/p>\n
Keine Peaks zu erkennen. Alles gut. Oder das Histogramm ist nicht fein genug ;)<\/p>\n
Update:
\nAuch bei einem Histogramm mit 5000 Bins zeigen sich keine Peaks.<\/p>\n","protected":false},"excerpt":{"rendered":"
Ich habe mir letztens, aus gegebenen Anlass, die wunderbare Weihnachtsvorlesung von Dr. Edmund Weitz angesehen und bin gegen Ende im dritten Teil stecken geblieben. Die Poincar\u00e9-Vermutung (Teil 3 von 3, Weihnachtsvorlesung 2018) Es wurde die Frage gestellt, Wie sieht das Leben auf einem Torus aus? Ich mach es kurz: Wenn das Universum ein Torus w\u00e4re […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-3935","post","type-post","status-publish","format-standard","hentry","category-allgemein"],"_links":{"self":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/3935","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3935"}],"version-history":[{"count":8,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/3935\/revisions"}],"predecessor-version":[{"id":3950,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/3935\/revisions\/3950"}],"wp:attachment":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3935"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3935"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3935"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}