Wie finde ich den am weitesten von einer gegebenen Menge entfernten Punkt und seine Bounding Box

Question

Ich habe eine Bounding Box und eine Reihe von Punkten innerhalb davon. Ich möchte einen weiteren Punkt hinzufügen, dessen Position weit entfernt von den zuvor hinzugefügten Punkten und weit entfernt von den Kanten der Box liegt.

Gibt es eine gemeinsame Lösung für diese Art von Sache? Vielen Dank!

Answer 1

Hier ist ein kleines Mathematica Programm.

Obwohl es nur zwei Zeilen Code (!) ist, werden Sie wahrscheinlich mehr in einer konventionellen Sprache benötigen, sowie eine Mathematikbibliothek, die in der Lage ist, ein Maximum an Funktionen zu finden.

Ich nehme an, Sie sind nicht in Mathematica fließend, so werde ich Zeile für Zeile erklären und kommentieren.

Zunächst erstellen wir eine Tabelle mit 10 zufälligen Punkten in {0,1} x {0,1} und nennen sie p.

p = Table[{RandomReal[], RandomReal[]}, {10}]; 

Nun erstellen wir eine Funktion zu maximieren:

f[x_, y_] = Min[ x^2, 
       y^2, 
       (1 - x)^2, 
       (1 - y)^2, 
       ((x - #[[1]])^2 + (y - #[[2]])^2) & /@ p]; 

Ha! Syntax wurde knifflig! Lassen Sie uns erklären:

Die Funktion gibt Ihnen für jeden Punkt in {0,1} x {0,1} die Mindestabstand von diesem Punkt zu unserem Satz p UND die Kanten. Die ersten vier Terme sind die Abstände zu den Kanten und die letzte (schwer zu lesen, ich weiß) ist ein Set, das die Entfernung zu allen Punkten enthält.

Was wir als nächstes tun werden, ist maximiert diese Funktion, so dass wir den Punkt bekommen, wo der Mindestabstand zu unseren Zielen maximal ist.

Aber zuerst schauen wir uns f [] an. Wenn Sie es kritisch betrachten, werden Sie sehen, dass es nicht wirklich die Entfernung ist, sondern die Entfernung im Quadrat. Ich habe es so definiert, weil auf diese Weise die Funktion viel einfacher zu maximieren ist und die Ergebnisse gleich sind.

Beachten Sie auch, dass f [] keine "hübsche" Funktion ist. Wenn wir es in plotten {0,1}, erhalten wir so etwas wie:

Das ist, warum müssen Sie ein schönes mathematisches Paket das Maximum zu finden.

Mathematica ist so ein schönes Paket, dass wir einfach, die Sache zu maximieren:

max = Maximize[{f[x, y], {0 <= x <= 1, 0 <= y <= 1}}, {x, y}]; 

Und das ist es. Die Funktion "Maximieren" gibt den Punkt und die Quadratdistanz zum nächsten Rand/Punkt zurück.

HTH! Wenn Sie Hilfe bei der Übersetzung in eine andere Sprache benötigen, hinterlassen Sie einen Kommentar.

bearbeiten

Obwohl ich kein C# Person bin, nach dem in SO nach Referenzen suchen und googeln, kam dies:

Ein Kandidat Paket ist DotNumerics

Sie die folgen sollten, folgendes Beispiel in der Verpackung:

file: \DotNumerics Samples\Samples\Optimization.cs 
Example header: 

    [Category("Constrained Minimization")] 
    [Title("Simplex method")] 
    [Description("The Nelder-Mead Simplex method. ")] 
    public void OptimizationSimplexConstrained() 

HTH!

Answer 2

Der Name des Problems, das Sie lösen, ist the largest empty sphere problem.

Es kann leicht in O (n^4) Zeit in der Ebene gelöst werden. Betrachte einfach alle O (n^3) Tripel von Punkten und berechne ihren Umkreismittelpunkt. Einer dieser Punkte ist Ihr gewünschter Punkt. (Nun, in Ihrem Fall müssen Sie auch "eine Seite" als einen Ihrer drei Punkte betrachten, so dass Sie nicht nur Umkreise sondern etwas allgemeinere Punkte finden, wie zum Beispiel einen Punkt, der von zwei Punkten und einer Seite gleich weit entfernt ist.)

Wie der Wikipedia-Link oben zeigt, kann das Problem auch in O (n log n) -Zeit gelöst werden, indem ein Voronoi-Diagramm berechnet wird. Genauer gesagt, dann ist Ihr gewünschter Punkt der Umkreismittelpunkt eines der Dreiecke in der Delaunay-Triangulation Ihrer Punkte (welches das Duale des Voronoi-Diagramms ist), von denen es nur O (n) gibt. (Um sich genau an Ihr Problem anzupassen, müssen Sie die Auswirkungen der Seiten der Box berücksichtigen.)