ubuntuusers.de

Halloe Leute,

ich habe hier ein Array, das aus etwa 100 Zeilen besteht, die wiederum ein Array darstellen(also im Pinzip ähnlich wie eine DB-Abfrage nach fetch).

In den Zeilen stehen Geodaten/Koordinaten und ich muss die Einträge aussortieren, die zu dicht beienanderliegen. Ein Beispiel:

12.345,32.16

wird angezeigt.

12.342,32.12

würde so nahe danebenliegen, dass er den ersten verdeckt (die fasse ich später zusammen...)

13.412,22.12

ist schön weit weg, wird also auch gezeigt.

aber auch

12.345,28.17

der hat zwar die gleiche Breite wie der erste aber eine ganz andere Länge Analog bei gleicher Länge.

Ich habe also 100 durch zwei Zahlen repräsentierte geometrische Objekte und muss herausfinden, welche der 100 sich verdecken und welche nicht.

Dazu habe ich erst mal ganz simpel geprüft, ob ich eine Breite schon mal hatte und habe diese dann verworfen. Damit gehen aber die verloren, die sich in der Länge ausreichend unterscheiden.

Jetzt suche ich nach einer Methode, das Array nach dem zweiten Key der enthaltenen Arrays zu sortieren

array(51) 
  [0]=>
  array(3) 
    [0]=>
    string(2) "97"
    [1]=>
    string(7) "13.3838"
    [2]=>
    string(17) "23.86934162089847"

13.3838 Grad ist die Breite, danach sollen alle 100 sortiert werden (so wie bei einer DB-Abfrage mit ORDER BY).

Danach kann ich die Liste durchgehen und Werte finden, die sich von Ihrem Vorgänger nicht ausreichend unterscheiden. Bei diesen Prüfe ich dann an Hand der enthaltenen Längengrade ob die Länge ausreichend von allen abweicht.

Der Stolperstein ist das Sortieren nach Key: ich kann im PHP-Manual keine Sortiermethode finden, bei der man einen Key in einem Subarray angeben kann....

usort/uksort/uasort kannst deine eigene Sortierfunktion definieren.

frostschutz schrieb:

usort/uksort/uasort kannst deine eigene Sortierfunktion definieren.

Das scheint mir aber sehr umständlich, ich will ja keinen komplizierten Vergleichsvorgang in den Subarrays sondern einfach eine Sortierung in der Art:

sortbykey($meinarray,[x]=>[1])

wobei x nur ein Platzhater für die Stufe in der Struktur wäre(um sagen zu können, dass man den zweiten Key im Subarray meint.

Ja, statt [x]=>[1] (so eine Syntax gibts nun mal nicht) schreibst eben function($a,$b) { return $a[x][1] > $b[x][1]; } oder vergleichbares.

Warum sich eine komplizierte Sortierfunktion überlegen die dann doch nicht alles kann wenn man mit einer eigenen Sortierfunktion alles machen kann was man will?

Das ist in fast jeder Scriptsprache so - wenn die allgemeine Sortierfunktion nicht reicht schreibt man halt seine eigene Vergleichsfunktion.

zettberlin schrieb:

Ich habe also 100 durch zwei Zahlen repräsentierte geometrische Objekte und muss herausfinden, welche der 100 sich verdecken und welche nicht.

Eine nicht optimierte, dafür leicht programmierbare Methode wäre ein erschöpfendes Vergleichen aller mit allen, also den 1. Wert mit 99 anderen, den 2. mit 98, den 3. mit 97 ... und den 99. mit einem, also ca. 100*100/2 Vergleiche. Bei viel mehr Koordinaten wird das schnell sehr langsam, aber wie große Programmierer sagen: When in doubt, use brute force.

Nun, und die Entfernung misst man natürlich mit Pythagoras, seit ebenjenem, allerdings kann man sich das Wurzelziehen sparen, in dem man als Schwellwert für die erlaubte Entfernung einfach das Quadrat dieser nimmt.

Allerdings kann ich kein PHP um die Details auszuklamüsern. Du willst ja später gelistete Koordinaten diskriminieren? Wenn die Entfernungen a:b 3, b:c 3 und a:c 5 ist, und der Schwellwert ist 4, dann fällt ja b aus den zu malenden Orten heraus. Dann kann man sich aber alle weiteren Vergleiche mit b sparen. c würde jedoch, da es von b nicht weit weg ist, wieder gemalt, denn von a ist es weit genug weg.

Was er mit verdecken genau meint hat er ja nicht geschrieben, insofern muß er das selber lösen... je nachdem ob es Rechtecke, Kreise, Polygone, oder transparente Rastergrafiken sind, wird das halt einfach oder kompliziert...

user unknown schrieb:

zettberlin schrieb:

Ich habe also 100 durch zwei Zahlen repräsentierte geometrische Objekte und muss herausfinden, welche der 100 sich verdecken und welche nicht.

Eine nicht optimierte, dafür leicht programmierbare Methode wäre ein erschöpfendes Vergleichen aller mit allen, also den 1. Wert mit 99 anderen, den 2. mit 98, den 3. mit 97 ... und den 99. mit einem, also ca. 100*100/2 Vergleiche. Bei viel mehr Koordinaten wird das schnell sehr langsam, aber wie große Programmierer sagen: When in doubt, use brute force.

Nun, und die Entfernung misst man natürlich mit Pythagoras, seit ebenjenem, allerdings kann man sich das Wurzelziehen sparen, in dem man als Schwellwert für die erlaubte Entfernung einfach das Quadrat dieser nimmt.

Allerdings kann ich kein PHP um die Details auszuklamüsern. Du willst ja später gelistete Koordinaten diskriminieren? Wenn die Entfernungen a:b 3, b:c 3 und a:c 5 ist, und der Schwellwert ist 4, dann fällt ja b aus den zu malenden Orten heraus. Dann kann man sich aber alle weiteren Vergleiche mit b sparen.

Das wäre ganz leicht: man müsste nur alle Werte sortieren, dann durchgehen und jeden verwerfen, der seinem Vorgänger zu nahe ist. Doof nur, dass es eben Länge *und* Breite gibt und man will eben nicht Punkte verwerfen, die zwar auf der gleichen Länge aber auf einer ganz anderen Breite als die anderen liegen...

Wenn ich also eine Liste von dreispaltigen Datensätzen habe, der nach dem zweitenFedl sortiert ist, kann ich den Abstand des sortierten Felds zum Vorgänger prüfen und beim Unterschreiten des gewünschen Thresholds prüfe ich noch den Abstand der dritten Felder des Vorgängers? Also so:

der Datensatz sieht so aus:

ID=>12 lang=>12.34 lat=>24.56

und jetzt:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

$langdiff=($prevlang-$lang)*1;
$latlangdiff=($prevlat-$lat)*1;

  if($langdiff>5 or $latlangdiff>5){
   //cooler Datensatz, nehme ich
  }
  else{
   //hatten wir schon, wollma nich meh
  } 

c würde jedoch, da es von b nicht weit weg ist, wieder gemalt, denn von a ist es weit genug weg.

Du musst dann eben einmal in x- und einmal in y- durchlaufen und nur die rauswerfen die bei beiden im Ergebnis auftauchen.

frostschutz schrieb:

Du musst dann eben einmal in x- und einmal in y- durchlaufen und nur die rauswerfen die bei beiden im Ergebnis auftauchen.

Das hatte ich mir auch schon überlegt, ich neige auch zu der brute force Methode 😉

Also:

ich nehme erst mal nur x, wenn ich nahe beieinanderliegende Werte finde, hole ich den y-Wert dazu und schau, ob es für diesen in der y-liste ebenfalls naheliegende Werte gibt, finde ich einen, suche ich für diesen den x-Wert und vergleiche den mit dem ersten gefundenen x-Wert, dann weiß ich, ob ich hier zwei Punkte habe, die tatsächlich nahe beieinander liegen.

Ich würde dann einmal 100 Datensätze durchgehen und bei jedem Treffer noch mal 200 Datensätze durchsuchen, für eine Entscheidung...

Das ist übrigens ein Demomodus, im laufenden Betrieb muss ich mit mehr als 2000 Datensätzen rechnen...

Und wie oft ändern sich diese Daten? Wenn nicht oft, dann ist die beste Optimierung, das bei Änderung einmal berechnete Ergebnis wiederzuverwenden. 😉

frostschutz schrieb:

Du musst dann eben einmal in x- und einmal in y- durchlaufen und nur die rauswerfen die bei beiden im Ergebnis auftauchen.

Das klappt nicht, weil A (0, 10), B(0, 20), C(10, 20) - hier kommt B A-seitig in die Liste x-Werte, und C-seitig in die Liste y-Werte, aber weder zu a, noch zu C liegt es nah.

zettberlin schrieb:

Das ist übrigens ein Demomodus, im laufenden Betrieb muss ich mit mehr als 2000 Datensätzen rechnen...

2000 * 2000 ist immernoch erst 4 Millionen - selbst auf einem Rasperry-PI sollte das in Null-komma-Nix fertig sein.

Ansonsten ist es möglich ein Raster über die Daten zu legen. Angenommen - nur der einfachen Darstellung wegen - der Mindestabstand wäre 4 Einheiten, den 2 Punkte auseinander liegen müssen. Dann könntest Du alle Punkte in ein 4x4 großes Raster packen, und dann brauchst Du nur Punkte zu untersuchen, die im gleichen Segment liegen, oder in einem der 8 Nachbarsegmente. Nur für diese müsste nachgerechnet werden, wie weit sie nun wirklich voneinander entfernt liegen.

1
2
3
4
5
6
7
8

   a|b   |c   |
   d|    |    |
----------------------
    |f   |    |
   e|   g|    |
----------------------
    |    |h   |
    |    |    |

Das sieht nicht quadratisch aus, weil Zeichen nicht so hoch wie breit sind. Bzw. es sieht halbwegs quadratisch aus, aber es sind nur 2 Zeilen auf 4 Spalten.

• ab sind in unterschiedlichen, aber benachbarten Feldern. Die Berechnung ergäbe, dass sie zu nah zueinander sind

• ae sind in unterschiedlichen, aber benachbarten Feldern. Die Berechnung ergäbe, dass sie nicht zu nah zueinander sind

• ad sind im gleichen Feld und zu nah

• fg sind im gleichen Feld, und weit genug voneinander entfernt

• gh in unterschiedlichen, aber zu nah

Wenn man die Punkte auf viele Felder verteilen kann, dann kann sich dieser Vorsortierungsaufwand rasch bezahlbar machen.

Ob ein Array überhaupt eine geeignete Datenstruktur ist, wenn da Werte entfernt werden müssen, bezweifle ich, aber ich weiß nicht wie Arrays in PHP sind. In Sprachen die ich verwende wäre ein Array nix dafür.

user unknown schrieb:

Das klappt nicht, weil A (0, 10), B(0, 20), C(10, 20) - hier kommt B A-seitig in die Liste x-Werte, und C-seitig in die Liste y-Werte, aber weder zu a, noch zu C liegt es nah.

Dann nimmst du eben Pairings in die Liste und nicht nur Einzelpunkte.

Aber ein Durchlauf reicht eh, es kann ja nicht so schwer sein, wenn man festgestellt hat daß die X-Koordinaten nah beieinander liegen, dann auch noch auf die Y-Koordinate zu schauen.

frostschutz schrieb:

user unknown schrieb:

Das klappt nicht, weil A (0, 10), B(0, 20), C(10, 20) - hier kommt B A-seitig in die Liste x-Werte, und C-seitig in die Liste y-Werte, aber weder zu a, noch zu C liegt es nah.

Dann nimmst du eben Pairings in die Liste und nicht nur Einzelpunkte.

Aber ein Durchlauf reicht eh, es kann ja nicht so schwer sein, wenn man festgestellt hat daß die X-Koordinaten nah beieinander liegen, dann auch noch auf die Y-Koordinate zu schauen.

Kann man, wenn die Liste nach x sortiert ist. Alles, was seinem direkten Vorgänger zu nahe kommt, wird verworfen und fertig. Ist die Liste aber nicht sortiert, kann ich nicht wissen, ob ein Punkt in der *vor*letzten Reihe schon einmal vorgekommen ist. Und was die Sache noch mal erschwert ist, dass es nicht um exakte Werte geht, sondern um ungefähre. Die Daten haben in echt 8-10 Stellen nach dem Komma ich kann nicht nach genauen Zahlen, sondern immer nur nach Bereichen suchen...

frostschutz schrieb:

Dann nimmst du eben Pairings in die Liste und nicht nur Einzelpunkte.

Ich nicht - ist ja nicht mein Problem.

Aber ein Durchlauf reicht eh, es kann ja nicht so schwer sein, wenn man festgestellt hat daß die X-Koordinaten nah beieinander liegen, dann auch noch auf die Y-Koordinate zu schauen.

Wohl nicht, aber was meinst Du mit einem Durchlauf? Man vergleicht den ersten Punkt mit allen anderen - alle anderen ist für mich schon ein Durchlauf - und dann den zweiten Punkt, so er verblieben ist, mit den restlichen verbliebenen. Und eben die Frage, ob die Punkte überhaupt verblieben sind, ist nicht völlig trivial. Aber vielleicht doch, in PHP?

@zettberlin:

Kann man, wenn die Liste nach x sortiert ist. Alles, was seinem direkten Vorgänger zu nahe kommt, wird verworfen und fertig.

Wenn aber ein Punkt verworfen wurde muss der nächste mit dem Vorvorgänger verglichen werden. Und wie macht man das praktisch, bei PHP?

Und was die Sache noch mal erschwert ist, dass es nicht um exakte Werte geht, sondern um ungefähre.

Ich denke Du hast einen Schwellwert, wie nahe die Punkte liegen dürfen. Dafür ist doch unerheblich, wieviele Nachkommastellen Du kennst.

Wenn Du Punkt m und m+1 hast, und x(m), x(m+1), y(m), y(m+1) nimmst Du erst die Abstände: dx=x(m+1)-x(m), dy=y(m+1)-y(m). dx*dx+dy*dy ?>= Schwellwert². Das meine ich mit Pythagoras ohne Wurzelziehen.