Wie kann ich die am weitesten entfernten Punkte --- oder einen am weitesten entfernten Punkt --- innerhalb eines …

Question

Aufgabe:

Wie kann ich die am weitesten entfernten Punkte --- oder einen am weitesten entfernten Punkt --- innerhalb eines gegebenen Kreises brechnen, wobei diese am weitesten entfernten Punkte so weit wie moglich entfernt sein sollen von einem oder mehreren gegebenen Punkten, welche innerhalb oder ausserhalb des Kreises liegen koennen?

Eine Begrenzung auf max. 100 Punkte, fuer die die am weitesten entfernten Punkte berechnet werden sollen, ist moeglich. Integer Genauigkeit ist ausreichend.

Problem/Ansatz:

Ich koennte das programmieren; will ich aber nicht, weil das eine doofe Loesung waere, die relativ lange dauern koennte, und eine schnelle Loesung ist gefordert. Ansonsten habe ich keine Idee, wie man sowas machen koennte, deshalb frage ich hier.

Eine Loesung in 3D, d. h. fuer Kugeln anstatt Kreise, waere auch schoen; 2D reicht aber.

Comments

Der gesuchte Punkt liegt bei einem vorgegebenen Punkt am Kreis-/Kugelrand. Weißt Du, was eine Kreisgleichung ist?

---

Dass die gesuchten Punkte bzw. der gesuchte Punkt auf dem Radius des Kreises liegen muss ist mir klar. Doch wo liegt er?

Was eine Kreisgleichung ist weiss ich nicht. Ich verstehe keine Mathematik, da ich Dinge nur verstehen kann, indem ich Abstraktionen entferne, und wenn man das mit Mathematik macht, dann bleibt nichts uebrig. Mathematik ist gar nichts.

---

... Punkt auf dem Radius des Kreises liegen muss

Nicht auf dem Radius, sondern am Rand. Der Radius ist die Distanz vom Mittelpunkt zum Rand.

Mathematik ist gar nichts.

Suchst Du eine mathematische Formel für die Koordinaten des Punktes?

von einem oder mehreren gegebenen Punkten

Würdest Du "möglichst weit entfernt von mehreren gegebenen Punkten" definieren als Summe der Distanzen zwischen dem gesuchten Punkt und jedem gegebenen Punkt? Wenn anders, wie?

---

Sorry, ich meinte natuerlich den Umfang bzw. Rand, ja.

Ich vermute, dass man irgendwie vielleicht mit Hilfe von Winkelberechnungen herausfinden kann, welche Punkte am weitesten entfernt sind. Die Anzahl der am weitesten entfernten Punkte ist vermutlich umso geringer, je groesser die Anzahl der Punkte ist, von denen sie am weitesten entfernt sein sollen.

Aber das ist egal; ich brauche einfach nur die am weitesten entfernten Punkte oder zumindest einen davon. Wie findet man heraus, welcher das ist?

PS: Ja, eine Formel koennte hilfreich sein. Den Mittelpunkt und Radius des Kreises sowie die Koordinaten der Punkte, fuer die die am weitesten entfernten Punkte berechnet werden sollen, kann ich alle angeben.

---

> Würdest Du "möglichst weit entfernt von mehreren gegebenen Punkten" definieren als

> Summe der Distanzen zwischen dem gesuchten Punkt und jedem gegebenen Punkt?

> Wenn anders, wie?

Ich meine das raeumlich. Die Distanzen zwischen Referenzpunkten sind nicht relevant.

Es ist uebrigens ein Denkfehler, dass der am weitesten entfernte Punkt auf dem Rand liegen muss. Er kann auch z. B. in der Naehe des Mittelpunkts sein. Ich fuege mal Bilder an, die das verdeutlichen sollen:

Der gruene Punkt in der Mitte des blauen Kreises ist der Mittelpunkt des Kreises. Die roten Punkte sind die Referenzpunkte. Der gesuchte Punkt ist der Punkt bzw. die Punkte, die am weitesten von den Referenzpunkten entfernt sind; das ist das orange Quadrat. Als Mensch kann man das halt einfach sehen wo das sein muss, aber als Mensch kann ich das nicht ausrechnen.

---

Ok, ich denke, man koennte sagen, dass die Summe der Distanzen zwischen dem gesuchten Punkt und den Referenzpunkten am groessten dort ist, wo der gesuchte Punkt am weitesten entfernt ist.

Jetzt braucht man nur fuer alle Punkte innerhalb des Kreises zu berechnen, wo das der Fall ist. Aber kann man vermeiden, das berechnen zu muessen? Weil das will ich ja im Grunde vermeiden und irgendwie einfach so ausrechnen, welche Punkte am weitesten entfert sind, ohne zigtausend Berechnungen zu machen.

---

Für alle Punkte innerhalb des Kreises kannst Du das ohnehin nicht berechnen, da dies unendlich viele sind.

Da die Referenzpunkte beliebig viele innerhalb und außerhalb des Kreises sein können, ist das Problem sehr allgemein.

Der Einfachheit halber nehmen wir mal den Kreis mit Mittelpunkt im Ursprung und Radius r.

Die Distanz von einem Punkt P(x,y) des Kreises zu einem Referenzpunkt R(r₁,r₂) ist die Wurzel aus (x-r₁)² +(y-r₂)².

Analog die Abstände von allen anderen Referenzpunkten S, T etc. zu P.

Um P zu bestimmen suchst Du nun das Maximum der Summe aus all diesen Abständen unter der Nebenbedingung x²+y² ≤ r²

Das wird schnell beliebig scheußlich…

---

Das wird schnell beliebig scheußlich…

Das hast Du hübsch gesagt.

---

Ja im Prinzip ist es scheusslich, wenn man das nicht einfach direkt ausrechnen kann. Kann man das denn nicht einfach ausrechnen? Wozu Mathematik wenn sie sowas Einfaches nicht kann was im Prinzip jeder sehen kann, ohne auch nur darueber nachdenken zu muessen?

In der Praxis reicht mir Integer-Genauigkeit, und die Koordinaten gehen von 0/0 bis 255/255. Der Radius des Kreises wird voraussichtlich zwischen 2 und 15 liegen, maximal 64. (In der Praxis ist der Kreis sogar eine Ellipse, indem er zwei Radien hat.)  Dazu kommt, dass es in diesem Fall sogar gut ist, wenn das Ergebnis ungenau ist.

Damit kann ich die Berechnung stark vereinfachen, indem ich anstelle des Kreises ein Rechteck annehme, innerhalb dessen der gesuchte Punkt liegen darf. Der gesuchte Punk darf innerhalb des Rechtecks liegen.  Das reduziert die Anzahl der Punkte auf maximal auf 4096.

Weiterhin brauche in diesem Fall nur den 4ten, 8ten, oder vielleicht sogar nur 16ten Punkt zu berechnen, womit ich nur 1024, 512 oder sogar nur 256 Punkte zu betrachten brauche. Die Anzahl der Referenzpunkte wird voraussichtlich meistens zwischen 1 und 4, maximal 100 liegen. Leider multipliziert sich damit die Anzahl der Entfernungsbrechnungen.

Vermutlich kann man das wiederum etwas optimieren, denn fuer jeden Referenzpunkt braucht man nur einen Quadranten (vom Kreismittelpunkt aus gesehen) zu betrachten: Der von diesem Referenzpunkt am weitesten entfernte Punkt kann nur in dem Quadrant liegen, der diagonal gegenueber dem Referenzpunkt liegt. (Oder ist das ein Denkfehler?)  Damit kann man die Anzahl der Entfernungsberechnungen auf ein Viertel reduzieren.

Damit bleiben fuer jeden Referenzpunkt unter Anwendung eines 16er Gitters 64 Entfernungsbrechnungen, insgesamt maximal 6400.  Die Loesung wird damit vermutlich schnell genug gefunden werden. Zudem kann der Algorithmus die Genauigkeit dynamisch anpassen und ein groeberes Gitter verwenden, jenachdem, wieviele Referenzpunkte vorhanden sind.

Es ist halt einfach zu programmieren.  Trotzem haette ich natuerlich lieber eine 'richtige' Loesung anstelle dieser Approximation; insbes. eine Loesung, die schneller ist. Kann man das nicht mathematisch irgendwie direkt ausrechnen?

So macht der Programmierer das. Wie macht der Matehmatiker das?

---

Dann programmier es halt.

Beim Dreikörperproblem reichen bekanntlich schon drei Massen, damit man es nur numerisch lösen kann…