Maximalabstand von einem Punkt zu allen Punkten, die den Körper angeben, in dem er sein darf |
| 20.02.2020, 10:20 | struppie | Auf diesen Beitrag antworten » | ||
| Maximalabstand von einem Punkt zu allen Punkten, die den Körper angeben, in dem er sein darf Durch 15 Punkte im Dreidimensionalen Raum wird ein abstrakter Körper erzeugt. Der Körper wird erzeugt dadurch das die äußersten Punkte der Wolke aus 15 Punkten miteinander verbunden werden und zwischen den dadurchentstehenden Geraden Ebenen erdacht werden. Da die Punkte auf einem Haufen sind, sind einige der Punkte jetzt auch innerhalb des Körpers. Die Frage ist, wie berechne ich einen Punkt innerhalb des Körpers der den größtmöglichen Abstand zu den Punkten um sich herrum hat? Meine Ideen: Mein Ansatz war die Abstände zwischen allen Punkten zu berechnen und mir dann anzuschauen welche am nächsten bei einander liegen und da zu schauen wo dieser Abstand am größten ist und den Punkt dann da dazwischen zu packen. |
||||
| 20.02.2020, 12:42 | Elvis | Auf diesen Beitrag antworten » | ||
1. Teste, ob Körper vorliegt. 1.1 Gibt es 3 paarweise verschiedene nichtkollineare Punkte ? 1.1.1 Ja. Lege Ebene durch diese 3 Punkte. 1.1.1.1 Gibt es einen Punkt ausserhalb der Ebene ? 1.1.1.1.1 Ja, weiter mit 2. 1.1.1.1.2 Nein. Ende, es gibt keinen Körper. 2. Polyeder bestimmen. 2.1 Zu je 3 verschiedenen Punkten (maximal Tripel) lege Ebene durch diese 3 Punkte. 2.1.1 Liegt je ein Punkt auf beiden Seiten der Ebene ? 2.1.1.1 Ja, vergiß die Ebene, denn sie schneidet den Körper und enthält keine Polyederseite. 2.1.1.2 Nein. Da ein Körper vorliegt, liegen alle anderen Punkte auf einer Seite der Ebene. In diesem Halbraum liegt der Körper. Erstelle die entsprechende Halbraumungleichung. 3. Löse das folgende Optimierproblem 3.1 maximiere das Minimum der Distanzen(P,Q) mit freiem Punkt P und allen (maximal) 15 Punkten Q 3.2 unter den Nebenbedingungen für P (Halbraumungleichungen) aus 2.1.1.2 Falls die Aufgabe so gemeint ist, dass nicht ein freier Punkt P gesucht ist sondern einer der vorgegebenen Punkte Q im Inneren des Körpers, ist die Zielfunktion auf ebendiese Punkte einzuschränken. Fraglich ist dabei, ob es derartige Punkte überhaupt gibt, z.B hat eine 14-seitige Pyramide keine inneren Punkte Q. Aber über solche Kleinigkeiten und Randbedingungen muss sich ohnehin jeder Programmierer Gedanken machen, und ich will dir ja auch nicht alles vorkauen. |
||||
| 20.02.2020, 13:48 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Eine Idee zur Detail-Ausführung von Punkt 3.1 (dabei gehe ich allerdings von "allgemeiner Lage" aus, d.h., keine vier Punkte liegen in einer Ebene): Die 15 Punkte bestimmen eine Voronoi-Zerlegung des Raumes. Zu jeder Voronoi-Zelle kann man einen Umkugelradius bestimmen. Dann schaut man sich die, bzw. genauer gesagt eine der Zellen mit dem maximalen Umkugelradius an und zugehörig einen der Eckpunkte jener Voronoi-Zelle, der in eben jener Umkugelentfernung vom Mittelpunkt liegt - das ist dann der gesuchte Punkt. |
||||
| 20.02.2020, 13:57 | Elvis | Auf diesen Beitrag antworten » | ||
Ich staune immer wieder, wie viele Leute Probleme gelöst haben, an die ich nie gedacht habe. 
Unter 3. habe ich mir ein lineares Programm vorgestellt, aber geometrische Verfahren sind mindestens ebenso elegant. |
||||
| 20.02.2020, 14:05 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Das ganze steht und fällt mit der Effizienz des Algorithmus zur Bestimmung der Voronoi-Zerlegung. Und da gibt es ein paar ganz ausgetüftelte, die mit auskommen. Lohnt sich beim hiesigen n=15 vermutlich noch nicht, da viel Arbeit reinzustecken, aber vielleicht geht es ja auch mal um n=15000.
|
||||
| 23.02.2020, 10:22 | Ulrich Ruhnau | Auf diesen Beitrag antworten » | ||
RE: Maximalabstand von einem Punkt zu allen Punkten, die den Körper angeben, in dem er sein darf
Um Handarbeit beim Definieren von Oberflächen wirst Du nicht herumkommen. Du wirst schon angeben müssen, welche Punkte Deiner Oberfläche durch Geraden verbunden werden müssen. Erst wenn Du Deinen Körper durch begrenzende Dreiecke im Raum definiert hast, samt Angabe, wo innen und wo außen ist, wird man in der Lage sein, zu berechnen, wie weit ein Punkt im Inneren des Körpers von seiner Oberfläche entfernt ist. |
||||
| Anzeige | ||||
|
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
|
