Häufung von Punkten herausfinden.

Willst du nur den Quadranten herausbekommen wo die Punkte am engsten aneinander liegen oder eine ganz bestimmte Koordinate unabhängig vom Quadranten?
Also wenn es nur der Quadrant sein soll dann teile deine Punkte in 4 Arrays (für jeden Quadranten eines).
Dann berechnest du für jedes Quadrantenarray einen Schwerpunkt( Mittelung der X und Y-Koordinaten).
Dann berechnest du für jeden Punkt in diesem Quadranten den Abstand zu diesem Mittelpunkt (Pythagoras) und aus den gesamten Abständen rechnest du die Standardabweichung für die Punkte des Quadranten.
Das machst du mit jedem Quadranten und der Quadrant mit der geringsten Standardabweichung ist der gesuchte.
Verfeinern könntest du das ganze dann noch in dem du grobe Ausreißer detektierst und eliminierst (z.B. über die 3-Sigma-Regel).

Wenn es allerdings nicht um den Quadranten geht dann würde mir spontan eine RANSAC-ähnliche Vorgehensweise vorschweben.
Das heißt allerdings du musst eine vorher definierte Streuweite eingeben.
Also im einfachsten Falle würdest du alle Punkte durchgehen und für jeden Punkt ermitteln wieviele Punkte sich innerhalb dieser Streuweite des Punktes befinden (jeweils über Pythagoras den Abstand).
Den Punkt mit der größten Anzahl an Punkten wird dann genommen und die Punkte innerhalb dieser Streuweite um diesen ermittelt und das ganze zu einem Schwerpunkt gemittelt.
Allerdings musst du wie gesagt erstmal eine Streuweite definieren - sonst funktioniert das nicht.

3. Möglichkeit:
Du erstellst ein Array mit den Ausmaßen deines Definitions und Wertebereiches.
Dann gehst du jeden Punkt durch und alle "Pixel" des erstellten Arrays mit einem gewissen Abstand um diesen Punkt werden in ihrem Wert um 1 erhöht.
Am Ende wird das Pixel mit dem höchsten Wert als Ergebnis genommen.
Um das mal bildlicher darzustellen:
Jeder Punkt ist eine Lampe und beleuchtet seine Umgebung in einem gewissen Abstand.
Sind viele Lampen in der Gegend machen sie Punkte die von beiden Lampen erreicht werden umso heller.
Unser anfangs erstelltes Array ist demnach eine Art Bild wo für jeden Ort die Helligkeit angegeben wird.
Besonders hell ist es dann dort wo die meisten Punkte eng aneinander liegen.
Verfeinern könnte man das ganze dann auch wieder wenn man nicht einfach 1 addiert sondern in Abhängigkeit vom Abstand.

Hi,
->Standortplanung<-
das erklärt ziemlich ausführlich was du suchst, aber ganz so einfach ist das nicht mehr. Da musst du dich halt ein wenig reinlesen.

Unter dem Namen "Standorttheorie" und "Standortprobleme" findest du auch noch einiges.

@anno
Ich glaube kaum das ihm das hier weiterhilft.
Die Formeln dienen dazu einen Standort zwischen n Punkten so zu legen das die Summe der Entfernungen aller Punkte zu diesem minimal wird.
Das funktioniert ja aber nur wenn alle Punkte welche zur Berechnung herangezogen werden auch relevant sind. Aber genau darum geht es ja - sie sind es eben nicht alle.
Es sollen nur die Punkte genommen werden welche einer größeren Häufung angehören.
Alle anderen Punkte sind demnach Ausreißer welche das Ergebnis verfälschen.
Das mag bei einer geringen Anzahl von Ausreißern ausgeglichen werden aber sobald der Bruchpunkt zu hoch wird wars das.
Die Ausreißer müssen also erst einmal eliminiert werden - das ist das eigentliche Problem hierbei - nicht die Berechnung des Mittels, Medians oder sonst irgendwas.
Im übrigen bin ich der Meinung das hier ein Schwerpunkt anstatt einer entfernungsoptimierten Standortwahl vollkommen ausreichend ist.

@quertz
Das entspricht aber nicht meiner 3. Möglichkeit sondern eher der 2.

Zitat von AspirinJunkie

@anno
Ich glaube kaum das ihm das hier weiterhilft.
Die Formeln dienen dazu einen Standort zwischen n Punkten so zu legen das die Summe der Entfernungen aller Punkte zu diesem minimal wird.
Das funktioniert ja aber nur wenn alle Punkte welche zur Berechnung herangezogen werden auch relevant sind. Aber genau darum geht es ja - sie sind es eben nicht alle.
Es sollen nur die Punkte genommen werden welche einer größeren Häufung angehören.
Alle anderen Punkte sind demnach Ausreißer welche das Ergebnis verfälschen.
Das mag bei einer geringen Anzahl von Ausreißern ausgeglichen werden aber sobald der Bruchpunkt zu hoch wird wars das.
Die Ausreißer müssen also erst einmal eliminiert werden - das ist das eigentliche Problem hierbei - nicht die Berechnung des Mittels, Medians oder sonst irgendwas.
Im übrigen bin ich der Meinung das hier ein Schwerpunkt anstatt einer entfernungsoptimierten Standortwahl vollkommen ausreichend ist.

Alles anzeigen

Eigentlich ist das schon wichtig. Natürlich ist das nicht der komplette Ansatz, aber eine Kombination würde funktionieren. qwertz hat gefragt "an welcher stelle die punkte am nähesten beieinander liegen". Am einfachsten ist dann die 2. Lösung von dir. Allerdings bekommt er dann den Punkt, der am nächsten an den anderen liegt und nicht die Stelle im Haufen, von der alle Punkte am nächsten dran liegen. Ich hätte als allererstes mit dieser Methode den "Haufen" ausfindig gemacht und dann von den jetzt noch vorhandenen Punkten die Stelle gesucht, die am nächsten an allen Punkten liegt. Es kommt halt drauf an wie genau das sein muss.

Außerdem ist in deinem Modell ein Denkfehler qwertz. Wenn du den Satz von Pythagoras benutzt, dann hast du einen Kreis um jeden Punkt, der abgesucht wird, und kein Quadrat.

Nein - mit "am engsten beieinander liegen" meint quertz den Bereich(!) wo eine starke Häufung der Punkte zu verzeichnen ist.
Also die Abstände der Punkte untereinander sehr klein ist und nicht die Summe der Abstände zu einem direkten einzelnen Punkt.

Den Haufen bekommst du mit dem Standortproblem nicht heraus - zumindestens nicht bei einem hohen Bruchpunkt.
Dann zieht es den Standort mit den geringsten Summe der Entfernungen außerhalb des Haufens.
Das Verfahren ist also alles andere als ein robustes Verfahren.
Es geht hier also nicht lediglich um Genauigkeit sondern direkt um richtig oder falsch.
Eine reine Standortsuche nach der Methode der geringsten Entfernungssumme kann hier durchaus zu falschen Ergebnissen führen.
Hilfreich um sich das etwas klarer werden zu lassen ist ein Einlesen in die Thematik der robusten Schätzverfahren .
Stell dir doch einfach vor der Haufen besteht nur aus 10 Punkten in der oberen linken Ecke.
Im Rest des Systems sind 100 andere Punkte zufällig verteilt (das sind unsere Ausreißer).
Den berechneten Standort zieht es Richtung Koordinatenursprung weit weg von unseren Haufen.
Das Ergebnis ist also grob falsch.

Glaub mir - die entfernungsoptimierte Standortwahl ist hier nicht das MIttel der Wahl.
Aber wie gesagt - wie die Punkte dann gemittelt werden ist eh das geringste Problem hier.

Ich hab das Verstanden!
Ich würde deine Methode benutzen, um den Haufen ausfindig zu machen, keine Frage. Aber um dann aus den Punkten die Stelle - und darum ging es ihm in dem ersten Post - zu finden, an der alle Punkte am nächsten liegen musst du irgendein solches Verfahren anwenden. Das man keinen Standort aus allen Punkten finden kann ist klar. Nur mit deiner Methode suchst du nur den Bereich. Er will aber auch eine Stelle, also X und Y Koordinate haben, von der aus die Punkte möglichst nah beieinander liegen. Das geht ja wohl nur damit.

Ja ich hab dich ja auch verstanden.
Das Verfahren kannst du durchaus anwenden - wär auch durchaus das beste um den wirklich besten Schwerpunkt zu finden.
Aber das ist ja erst der letzte Schritt.
Dort ist das ja auch legitim.
Ob der Aufwand im Vergleich zu einer einfachen Koordinatenmittelung, wozu der Unterschied eher gering ausfallen wird lohnt, ist eine andere Frage.
Denn jede Mittelungsmethode im 2. Schritt wird sehr gut innerhalb des Haufens liegen.
Und er will ja lediglich einen - Zitat: "coordinaten eines punktes in der mitte dieses haufens".
Also benötigt er gar keine streckenoptimierte Methode.

Du sagtest jedoch aber das du den Haufen über die entfernungsoptimierte Standortsuche identifizieren willst - darum geht es hier in Wirklichkeit.
Eigentlich könnte die Aufgabe auch lauten: Finde alle Punkte welche die größte Häufung im Koordinatensystem darstellen.
Dann brauch gar nicht mehr gemittelt werden - das ist der eher triviale Punkt welcher erst nach der Identifizierung des Haufens folgt - das ist ja aber, wie so oft schon gesagt, gar nicht das Problem.
Die wirkliche Aufgabe - die Identifizierung der Häufung lässt sich nicht robust mit der entfernungsoptimierten Standortbestimmung bewerkstelligen.
Aber genau das wolltest du ja damit machen - nur wie?

Hallo,
ich würde nach der 3. Methode vorgehen. "Hellsten" Punkt suchen, alle anderen Punkte unterhalb einer bestimmten "Helligkeitsschwelle" eliminieren und vom Rest den Schwerpunkt nehmen. Bei nur einem Punkthaufen kein Problem, je nach Verfahren liegen die berechneten Zentren jedenfalls nicht weit auseinander.
Die Geschichte wird dann verzwickt, wenn es mehrere weiter voneinander entfernt befindliche Wolken gibt. In den Quadranten I,II und III befinden sich in den äußeren Ecken Punktewolken mit ähnlicher "Helligkeit", der Rest der Sterne ist zufällig verteilt. Dann wären mehrere Zentren richtig. Es müsste also eine Funktion "_Haufen_erkennen" auf alle Punkte losgelassen werden, welche auch mehrere Haufen erkennt. Jedenfalls mal eine nette Aufgabe, mach doch ein µ-It drauss^^
ciao
Andy

Schluss mit der Theorie :D.
Ich hab die 2. Methode umgesetzt, eigentlich ist das ja nicht besonders schwer. Nur bekommt man so halt nur den Punkt, von dem aus innerhalb der "Streuweite" die meisten anderen Punkte liegen.
Aber eigentlich dürfte das ja so reichen...

_arrayunique()