PHP-Scripte PHP-Tutorials PHP-Jobs und vieles mehr

PHP-Scripte PHP-Tutorials PHP-Jobs und vieles mehr (https://www.php-resource.de/forum/)
-   PHP Developer Forum (https://www.php-resource.de/forum/php-developer-forum/)
-   -   Kleinstmöglicher Kreis um Koordinaten (https://www.php-resource.de/forum/php-developer-forum/105946-kleinstmoeglicher-kreis-um-koordinaten.html)

Koda 27-03-2017 17:52

Kleinstmöglicher Kreis um Koordinaten
 
Guten Abend

Gibt es eine Möglichkeit, den Kleinstmöglichen Kreis zu Zeichnen welcher noch alle Koordinaten umfasst?

Ich habe einen Array mit diversen Koordinaten (Nicht Geolocations)
PHP-Code:

$myCoordinates[1]['x'] = 50.345;
$myCoordinates[1]['y'] = 20.345;
$myCoordinates[2]['x'] = ....;
$myCoordinates[2]['y'] = ....;
$myCoordinates[3]['x'] = ....;
$myCoordinates[3]['y'] = ....;
$myCoordinates[4]['x'] = ....;
$myCoordinates[4]['y'] = ....; 

Nun möchte ich einen Kreis zeichnen, der noch alle Koordinaten umschliesst (https://en.wikipedia.org/wiki/Smallest-circle_problem)

Ich habe schon Ansätze gefunden, kann damit aber nur ein Quadrat erstellen der alle umschliesst. Nur hilft mir das leider nicht weiter:
PHP-Code:

$Xs array_column($myCoordinates'x');
$Ys array_column($myCoordinates'y');
$boxMin = [min($Xs), min($Ys)];
$boxMax = [max($Xs), max($Ys)];
imagefilledrectangle($image$boxMin[0],$boxMin[1],$boxMax[0],$boxMax[1], $red); 

Vielleicht kann mir ja jemand weiterhelfen wie ich den Kreis generieren kann sowie die grösse des Kreises in cm bestimmen kann.

Berechnung des Kreises in cm: Da der Durchmesser pixel sind, nehme ich an dass ich mit der Formel mm = (pixels * 25.4) / dpi einfach meine cm umrechnen kann.

Vielen Dank schon im Voraus für jede Hilfe.

Gruss

Koda

boeserfrosch 27-03-2017 19:06

Hast du eventuell schon daran gedacht das über den Flächenschwerpunkt zu lösen?
Das heißt betrachte jeden Punkt als Masse, die Summe der Positionen einer Achse geteilt durch die Anzahl der Werte ergibt damit den Schwerpunkt auf dieser Achse.
Das ganze für alle Achsen durchführen, damit hättest du den Mittelpunkt.
Nun musst du noch den größten absoluten Abstand zu diesem Punkt finden, beispielsweise über die Norm. Das wäre dann der Radius des Kreises.
Das müsste dann auch für höher dimensionale Probleme funktionieren.

Pseudo-Code:
Code:

CenterX = sum(array[x])/length(array);
CenterY = sum(array[y])/length(array);
Radius = max(max(abs(array[x]-CenterX)),max(abs(array[y]-CenterY)));

Circle c = Circle(CenterX,CenterY,Radius);

In anbetracht das dein Array bereits in Zentimeter statt Pixel (Pixel können/sollten nur ganze Werte haben) aufgeführt ist, ist der Radius auch schon in Zentimeter

Koda 27-03-2017 19:43

Guten Abend

Vielen Dank für deine Antwort.
Zitat:

In anbetracht das dein Array bereits in Zentimeter statt Pixel (Pixel können/sollten nur ganze Werte haben) aufgeführt ist, ist der Radius auch schon in Zentimeter
Sind die Kommawerte Problematisch? Ich bin mir eigentlich sicher das es px. sind. Die Koordinaten bestimme ich mit dieser funktion in JS Das seltsame ist bei mir hat die x axe immer komma werde. Das Bild ist rechteckig. Auch wenn ich ein anderes nutze. Ich weiss jedoch nicht wieso

Zitat:

Hast du eventuell schon daran gedacht das über den Flächenschwerpunkt zu lösen?
Ich muss ehrlich gestehen ich weiss es nicht. Ich habe so viel Lösungsansätze versucht, zuletzt den Code im ersten Beitrag, komme aber einfach nicht mehr weiter, resp. weiss nicht was ich noch versuchen könnte.

Zitat:

CenterX = sum(array[x])/length(array);
Was meinst du damit? Die summe aller X werte durch die Anzahl der X werte?

Gruss

Koda

boeserfrosch 27-03-2017 20:26

Beschreib am besten mal dein Gesamtproblem, dann lässt sich einfacher ein Vorschlag machen wie man das lösen könnte.

Durch die Komma-Werte sah es für mich nach Zentimeter-Werten aus.
Wenn ich mir den von dir verlinkten Code ansehen dann kommen die krummen Werte vom ratio. Hast du den angepasst?

Mit
Code:

CenterX = sum(array[x])/length(array);
meine ich, wie du schon korrekt erkannt hast, das alle XWerte summiert werden und die Gesamtsumme dann durch die Anzahl der Punkte geteilt wird.

Mit dem Flächenschwerpunkt berechnet man die Position an welchem sich das "Gewicht" eine Fläche konzentrieren würde wenn man die Fläche immer weiter verkleinert.
Oder im drei-dimensionalen: Wo liegt das Gewichtszentrum eines Körpers.

Stell dir beispielsweise einen optimalen Kreisel vor: Das Gewichtszentrum liegt in X-Y-Richtung genau im Mittelpunkt - In Z-Richtung irgendwo auf der Z-Achse.
Hast du nun einen nicht optimalen Kreisel, beispielsweise durch einen Ausbruch an der Kante so liegt der Schwerpunkt nicht mehr im Mittelpunkt.
Deine Punkte sind dann sowas wie Teilflächen mit der Ausdehnung 0 aber dem Gewicht der ursprünglichen Flächen. In deinem Fall sind alle gleich schwer, also können wir das tatsächliche Gewicht vernachlässigen.
Das Zentrum aller Punkte ist somit das Zentrum aller Flächen und damit der Flächenschwerpunkt.

Anderes Beispiel um sich das zu verdeutlichen ist eine Wippe, wenn beide Kinder gleich viel wiegen und beide gleich weit vom Mittelpunkt entfernt sitzen liegt der Flächenschwerpunkt in der Mitte -> Die Wippe bleibt waagerecht. Sitzt ein Kind weiter weg oder ist es schwerer als das andere wandert der Flächenschwerpunkt zu diesem Kind und die Wippe kippt.

Genauso verhält es sich mit deinen Punkten.

Die berechneten Werte lassen sich dann mit der Gleichung:
Code:

mm = pixels * mm/pixel
oder deiner Gleichung:
Code:

mm = (pixels * 25.4) / dpi
in milimeter umrechenen.
Beachte aber das du bei dpi auch die korrekten Angaben nutzt.

Ansonsten wie Anfangs gesagt, schildere am besten was du genau vorhast!

Koda 27-03-2017 21:33

Guten Abend

Vielen dank. Es ist sehr schwer zu erklären was ich Vorhabe, da ich sowas noch nie gesehen habe. Auf einem Bild mit einer Art Scala "zeichne" ich die Punkte ein. Mit dem kleinsten kreis habe ich dann den durchmesser, und kann somit auswerten wie viel weiter ich gekommen bin. Also je kleiner der Kreis wird umso besser für mich. Ich weiss nicht ob du dir das vorstellen kannst was ich meine.

Mit dem ersten code von mir konnte ich das kleinste Rechteck generieren. Nun könnte ich die Fläche ausrechnen und hätte dann eine ähnliche Auswertung. Jedoch brauche ich das mit dem Kreis.

Zitat:

Wenn ich mir den von dir verlinkten Code ansehen dann kommen die krummen Werte vom ratio. Hast du den angepasst
Nein. Ich habe so eine Funktion benötigt und die klappte am besten. Würdest du sagen die ist fehlerhaft? Bis auf die Kommawerte hatte ich bisher keinerlei Probleme

EDIT: Du siehst, mit dem oberen Code erhalte ich ein Rechteck mit dem Mittelpunkt (Rot). Jedoch schaffe ich nur ein Kreis zu generieren für das Rechteck, nicht aber der kleinstmögliche Kreis. Für einen Kreis wäre ja auch der Mittelpunkt falsch. Hier siehst du ein Beispiel: http://imgur.com/a/FD7sh
http://imgur.com/a/FD7sh
Gruss

Koda

boeserfrosch 28-03-2017 15:17

Ich habe den Javascript-Code nicht getestet, aber er scheint zu funktionieren.

ABER:
Der Code basiert darauf das der Fragesteller nach einer Möglichkeit gesucht hat auf ein eingebundenes Bild zu klicken und die Position in Pixel im Orginalbild zurück zu bekommen. Das heißt die Größe des eingebundenen Bild entspricht NICHT der Größe des Orginalbild.
Du musst also in dem Code noch die Variable "naturalWidth" anpassen.
Wenn also dein Bild auf der Festplatte eine Breite von 1000 Pixel hat musst du da 1000 eingeben auch wenn du das Bild nur auf 100 skalierst einbindest.

Der Teil oben ab dem ABER ist aber nur notwendig wenn du die Potentiellen Zentimeter auf dem Orginalbild haben willst.
Willst du die Zentimeter auf dem Bildschirm haben ist die größe des Orginalbild irrelevant und du solltest dann den Teil mit der "Ratio" Umrechung aus der Javascriptfunktion entfernen.

Wie du siehst ist das herangehen an die Sache abhängig davon was du genau vorhast.
Das heißt nicht nur das du Punkte auf einem Bild anklicken willst und einen Kreis darum ziehen willst sondern auch zu welchen Zweck!

Ein Beispiel: Ein Zweck könnte sein du bindest eine Landkarte ein und markierst mehrere Punkte. Du möchstest nun herausfinden wo das Zentrum der Punkte ist und den Umkreis um das Zentrum welcher alle Punkte einschließt. Beispielsweise um hearuszufinden wo sich eine Gruppe von Personen in der Mitte trifft.
In diesem Fall wäre das Vorgehen wie folgt:
Du bindest das Bild der Landkarte auf eine bestimmte Breite ein. Sagen wir auf eine Breite von 500 Pixeln.
Das Orginalbild (das unskalierte) auf deiner Festplatte hat eine Breite von 2000 Pixel.
Das verhältnis ist demnach 500/2000 = 1/4.
Desweiteren musst du ermitteln wie viele mm/cm/m/km einem Pixel in deinem Orginalbild entspricht -> Vergleich Maßstab
Nun ermittelst du mit Javascript im Browser die Pixelpositionen deiner Punkte im eingebundenen Bild.
Diese Pixelwerte teilst du nun mit dem Verhältnis von eingebundenen zum orginal Bild und multiplizierts dann noch den Maßstab dazu.
Dann berechnest du wie oben beschrieben
den Flächenschwerpunkt und den Radius des umschließenden Kreises und weißt nun wie weit die Person mit dem längsten Weg zum zentralen Treffpunkt laufen muss.

Ich habe übrigens grad meine Theorie mit dem Flächenschwerpunkt überprüft.
Meine Annahme passt bedauerlicherweise nicht.


Koda 28-03-2017 17:47

Passt alles. Vielen Dank :)


Alle Zeitangaben in WEZ +2. Es ist jetzt 08:00 Uhr.

Powered by vBulletin® Version 3.8.2 (Deutsch)
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.3.0
[c] ebiz-consult GmbH & Co. KG