Polygon umkreisen?

[Mikrowelle]

Hallo

Ich habe ein Polygon mit bis zu 1000 Ecken. Ich möchte nun ein Kreis Zeichnen der alle Ecken beinhaltet, so das die Ecken etweder auf der Fläche des Kreises sind und oder der Kreis die ecken schneidet. Kein Punkt darf ausserhalb des Kreises bleiben.

Der Kreis soll also maximal gross sein um alle Punkte zu schneiden oder auf seine Fläche aufzunehmen aber darf kein pixel grösser sein als Erforderlich.

Hier ein Bild, auf der Linken seiten seht ihr 3 Punkte welche von einem Kreis umschlossen sind.

Gibts da eine einfache Methode dazu?

 

[SlaterB]

Kreis mit kleinstem Radius, der vorgegebene Punkte enthält

 

[Int42]

Hallo,

Ich bin das mal theoretisch durchgegangen, hab es also noch nicht ausprobiert.
Das erste ist, den Mittelpunkt des Kreises zu finden. Der Mittelpunkt des Kreises liegt in der Mitte der Strecke zwischen den zwei Punkten, die am weitesten voneinander entfernt sind. Also könnte man mit jedem Punkt testen, wie weit die anderen Punkte jeweils entfernt sind. Da das allerdings bei 1000 Punkten relativ rechenlastig werden könnte, hab ich mir mit einem Kollegen noch eine weitere Lösung überlegt:

Edit: Achtung, diese Lösung führt nicht zum gewünschten Ergebnis!

Ausgangssituation:
eine Anzahl an beliebigen Punkten in einem zweidimensionalen Raum:

Zunächst findest du die vier Punkte heraus, die das kleinste Reckteck um die Punktmenge bilden. Also die Punkte, mit dem geringsten und höchsten x- und y-Wert.

Dann nimmst du den Mittelpunkt dieses Rechtecks und bestimmst den davon am weitesten entferntesten Punkt (hier P). Für diesen Punkt bestimmst du wiederum den davon am weitesten entferntesten Punkt (hier Q).

Nun hast die Strecke zwischen den zwei Punkten, die am weitesten voneinander entfernt sind. Die Mitte dieser Strecke ist der Mittelpunkt deines Kreises.

Et voilà, der Kreis mit dem minimalsten Radius um eine Punktmenge.

Wenn du weitere Fragen hast, nur heraus damit

 

[SlaterB]

was sagst du zu diesem neuen Punkt?

 

[HimBromBeere]

Das ist zwar eine nette Methode, erstellt aber nicht den Umkreis (übrigens: minimal kann man nicht steigern, nur so am Rande ).

 

[SlaterB]

@HimBromBeere
du sagst das so bestimmt, kannst du das näher begründen?

wenn ich mir mein ergänzendes Beispiel anschaue:
wie wäre es, diese Methode anzuwenden, bei allen verbleibenden Punkten außerhalb des Kreises den Abstand zum Mittelpunkt zu bestimmen,
und dann den entferntesten Punkt zusammen mit einem der beiden bisherigen?
durch mindestens zwei Punkte geht der Umkreis doch sicherlich immer

scheint aber immer noch viel zu einfach im Vergleich zu meinem Link, auch wenn ich den gar nicht erst genauer angeschaut habe..
vielleicht nicht das Optimum

 

[Int42]

minimal kann man nicht steigern, nur so am Rande

Ups, da hast du natürlich recht

was sagst du zu diesem neuen Punkt?

Ja, das ist tatsächlich ein Problem. Wie gesagt, ich habs mir nur mal theoretisch überlegt. Aber ich hab noch einen Lösungsansatz. Folgt sogleich.

 

[hüteüberhüte]

Also bei 1000 Punkten müsstest du 999+998+...+1 Abstände berechnen... Denke mal, dass lässt sich problemlos berechnen (in O(n^2))

 

[Spacerat]

Einfachste Methode:

int minX = Integer.MAX_VALUE;
int maxX = Integer.MIN_VALUE;
int minY = Integer.MAX_VALUE;
int maxY = Integer.MIN_VALUE;
for(Point p : myPointList) {
  if(p.x > maxX) {
    maxX = p.x;
  }
  if(p.Y > maxY) {
    maxY = p.y;
  }
  if(p.x < minX) {
    minX = p.x;
  }
  if(p.y < minY) {
    minY = p.Y;
  }
}
Point m = new Point((maxX - minX) / 2, (maxY - minY) / 2);
double r = Math.sqrt(m.x * m.x + m.y * m.y);
Point circlePos = new Point(m.x + minX, m.y + minY);

[EDIT]Soviel zum Thema BoundingBox bzw. BoundingSphere.
@SlaterB: Das mit dem Hinzufügen neuer Punkte klappt ja, so wie du es sagst. Nun aber entfernen wir mal einen Punkt aus dem Polygon. Wenn das einer der Grenzpunkte war, darf man alles gleich neu berechnen oder gibt's da 'nen anderen Weg?[/EDIT]

 

[Int42]

Das ist aber auch nicht der minimale Umkreis, glaube ich. Schlag mich bitte, wenn ich schon wieder falsch liege

 

[SlaterB]

das wäre ein Kreis genau durch die Ecken des Vierecks aus den bisherigen Bildern?
scheint mir nicht optimal falls nicht zufällige zwei Punkte genau gegenüberliegende Ecken sind,
wie in jenem Beispiel, wäre ja noch größer als durch P und Q

jaja, meckern an anderen Lösungen macht schon Spass (falls man damit nicht falsch liegt)

 

[Int42]

Also, nächster theoretischer vorschlag:

Wie gehabt, Kreis mit Mittelpunkt in dem Rechteck. Dann der am weitesten entferte Punkt.

Dann könnte man den Mittelpunkt diesem Punkt immer weiter annähern, bis der Kreis an einen weiteren Punkt kommt.

EDIT: ist wohl auch nicht der minimale Kreis...

 

[Spacerat]

@SlaterB: Irrtum. Das ist der kleinste Umkreis. Dieser geht nun mal durch alle 4 Ecken des aus den Punkten gebildeten Rechtecks. Den einzigen Fehler den Int42 gemacht hat war, er hat statt der Rechteckseiten die Strecke PQ halbiert.
[EDIT]Moment mal... wie können denn 2 Punkte genau auf dem Kreis liegen? OMG... das könnte komplett der falsche Ansatz sein. siehe Thaleskreis
...und dann... siehe Code
Daraus folgt Int42's zweiter fehler (jener der mich grad' verwirrte). Er nimmt, wozu auch immer, den vom Mittelpunkt des Rechtecks am weitesten entfernten Punkt. Dieser schneidet aber nicht immer eine Ecke des Rechtecks.[/EDIT]

 

[SlaterB]

@SlaterB: Irrtum. Das ist der kleinste Umkreis. Dieser geht nun mal durch alle 4 Ecken des aus den Punkten gebildeten Rechtecks. Den einzigen Fehler den Int42 gemacht hat war, er hat statt der Rechteckseiten die Strecke PQ halbiert.

wie gesagt ist ein Kreis durch alle Rechteckpunkt viel zu groß!
der durch PQ ist kleiner, in dem Beispiel der richtige,
in meinem Beispiel mit roten Punkt wirds komplizierter, das ganze Rechteck ist in jedem Fall zu groß,
außer für den Spezialfall, dass in beiden Ecken ein Punkt liegt,
ansonsten geht der Kreis maximal durch einen, eher durch gar keinen Punkt, offensichtlich zu groß,

es ist der minimale Kreis um alle Punkte gesucht, und solange nicht zwei Punkte berührt werden kann man ja ganz leicht den Radius kürzen
(auch mit schon zwei Punkten berührten Punkten geht das freilich immer noch, kompliziert genug.., gar 3 nötig?
edit: nein nein, zumindest wenn genau zwei Punkte gegenüber, immer zu sehr ins spekulieren )

 

[Int42]

Den Beitrag hatte ich glatt überlesen, bevor ich meinen zweiten Lösungsansatz geschrieben hatte:

wie wäre es, diese Methode anzuwenden, bei allen verbleibenden Punkten außerhalb des Kreises den Abstand zum Mittelpunkt zu bestimmen,
und dann den entferntesten Punkt zusammen mit einem der beiden bisherigen?

Dieser Ansatz klingt nicht schlecht. Aber wo wäre dann der Mittelpunkt?

 

[Spacerat]

Den Beitrag hatte ich glatt überlesen, bevor ich meinen zweiten Lösungsansatz geschrieben hatte:

Dieser Ansatz klingt nicht schlecht. Aber wo wäre dann der Mittelpunkt?

Der wäre immer noch mitten in dem gebildeten Rechteck.

 

[Int42]

Meinst du so?

Falls ja, dann wäre das ja nicht der minimale Kreis?

 

[Spacerat]

Okay... irgendwas läuft da grad' schief. Fakt ist aber, dass das Rechteck schon mal der erste Ansatz ist. Fakt ist auch, das man mit Thales einen Kreis hinbekommt, der alle drei Punkte eines Dreiecks schneidet.
Evtl. greift da die Idee mit den drei grössten Abständen. Evtl. schaut man sich auch mal diesen Link an.
Das mach' ich jetzt auch... schönen Tag noch.

 

[Int42]

Evtl. schaut man sich auch mal diesen Link an.

Ich dachte zuerst auch, das wäre die Lösung.

In dem Artikel steht allerdings: "In der ebenen Geometrie ist ein Umkreis ein Kreis, der durch alle Eckpunkte eines Vielecks (eines Polygons) geht." Unser Kreis muss ja nicht durch alle Punkte gehen.

Aber ich gebe dir Recht, das Rechteck scheint auf jeden Fall ein guter Ansatz zu sein.

 

[Int42]

Gibts da eine einfache Methode dazu?

Also, ich glaube, man kann sagen, eine wirklich einfache Methode, die völlig exakt ist, gibt es wohl nicht. Im Moment fällt mir auch kein Ansatz mehr ein.
Allerdings kannst du mal hier nachschauen. Der Beitrag von "AD" scheint ganz vernünftig.
Wenn du es allerdings in Kauf nehmen kannst, dass der Kreis nur ungefähr um die Punkte geht, bzw. über die Punkte hinaus, dann ist die Methode von Spacerat auf jeden Fall nicht schlecht.

 

[hüteüberhüte]

Jetzt hab ich zwei Stunden gewartet, und ihr beschäftigt euch immer noch mit diesem Thema^^

Ist doch klar, dass der Mittelpunkt des Kreises die Hälfte der Strecke der am weitesten voneinander entfernten Punkte ist. Diese zwei Punkte lassen sich nur durch "Ausprobieren" herausfinden -> also zwei verschachtelte Schleifen...

 

[Spacerat]

Wenn du es allerdings in Kauf nehmen kannst, dass der Kreis nur ungefähr um die Punkte geht, bzw. über die Punkte hinaus, dann ist die Methode von Spacerat auf jeden Fall nicht schlecht.

Danke für die Blumen...
Kennt ihr das Gefühl? Jahrelang macht man etwas falsch ohne es zu hinterfragen, weil's einleuchtend ist. Dann kommt so ein "Anfänger" (mal so gedacht, weil Anfängerforum) daher und indirekt wird man gezwungen, es anders zu machen. Das bedeutet: Selbst wenn dem TO mein Vorschlag genügt, mir genügt er jedenfalls nicht mehr. Einen Dreiecksmittelpunkt zu finden scheint ja nicht allzuschwer, das Applet hier ist zumindest insgesammt nur ca. 20KB gros. Hoffentlich lässt sich was draus machen.
Ein Kreis um die drei vom Mittelpunkt entferntesten Punke sollte den Rest ja einschliessen, oder liege ich mit meiner Logik wieder falsch?

Ist doch klar, dass der Mittelpunkt des Kreises die Hälfte der Strecke der am weitesten voneinander entfernten Punkte ist.

Diese Erkenntnis ist wie bereits festgestellt falsch.

 

[AquaBall]

Der Kreis soll also maximal gross sein um alle Punkte zu schneiden oder auf seine Fläche aufzunehmen aber darf kein pixel grösser sein als erforderlich.

... kein pixel grösser ...

 

[AquaBall]

Ein empirischer, vollständiger Ansatz wäre:
1) Hüllpunkte bestimmen => streng konkaves Polygon aller äußersten Punkte, Da können schon malö 90% wegfallen.
verbleiben n relevante Punkte
2) alle restlichen Punkte in jeder 3er Kombination als 3-Eck interpretieren
verbleiben n*(n-1)*(n-2) ~ n³ Dreiecke
3) zu jedem Dreieck den Umkreismittelpunkt bestimmen
verbleiben n³ Mittelpunkte
4) zu jedem Mittelpunkt den Abstand aller Punkte prüfen.
Abbruch bei Länge größer Radius
Sieg bei alle Längen kleiner Gleich Radius

Lass doch den Compi rechnen. Wozu haben wir ihn?

(PS: Mit Geogebra kann man da ganz nett rumspielen.)

 

[Melfis]

Hab hier was, hoffe es hilft euch:
http://www.fernuni-hagen.de/imperia/md/content/fakultaetfuermathematikundinformatik/fakultaet/programmierpraktikum/2012_ss_aufgabenstellung.pdf

MFG Melfis

 

[Spacerat]

Hab hier was, hoffe es hilft euch:
http://www.fernuni-hagen.de/imperia/md/content/fakultaetfuermathematikundinformatik/fakultaet/programmierpraktikum/2012_ss_aufgabenstellung.pdf

MFG Melfis

Also mir schon... Danke

 

[AquaBall]

Der Link ist ja sehr interessant.

Ich hab jetzt noch etwas rumgespielt, und das Problem reduziert auf 4 Punkte.
Wer eine Strategie hat, kann es daran ausprobieren.
3 Punkte sind fix:
P1(3/3)
P2(3/-3)
P3(5/2)
Der 4. Punkt wird zu Prüfzwecken auf 3 verschiedene Positionen gesetzt:
Position 1: P4(1/1)
Position 2: P4(0/1)
Position 3: P4(0/2)
Trotz minimaler Änderung ergeben sich 3 verschiedene OptimalKreise, und ich hab noch keinen Mathematischen Zusammenhang entdeckt, wann welcher zu nehmen wäre.
Es zeigt sich sogar, dass schon die Vermutung

"Mittelpunkt liegt auf der Streckensymetrale der entferntesten Punkte"

falsch ist.

Die 3 Lösungen sind auf Papier leicht mit Zirkel nachzukonstruieren.
Aber die Strategie welche Punkte zu nehmen sind erschließt sich mir nicht.
Bin neugierig auf Antworten!

Zum Experimentieren: Geogebra (Kostenloses WebOnline-GeometrieKonstruktionsProgramm)

 

[Ullenboom]

Ein schönes geometrisches Problem. Rein intuitiv würde ich folgendes tun: Erst die konvexe Hüllen berechnen lassen (etwa mit Hilfe von https://forums.oracle.com/forums/thread.jspa?messageID=6966715). Als nächstes nimmst du dir das Polygon/Shape und berechnest den Mittelpunkt (Google....), das das gibt dir den Mittelpunkt deines Kreises. Jetzt kannst du noch mal alle Punkte ablaufen, dir den mit der größten Distanz zum Mittelpunkt holen, und du hast den Radius.

 

[hüteüberhüte]

Ein anderes, ähnliches Problem ist glaub ich einen Kreis mit festem Radius/Umfang so zu platzieren, dass er am meisten Punkte enthält^^ Muss ich später mal nachlesen wie das ging

 

[Spacerat]

Ich hab' jetzt mal ein wenig Zeit investiert und das ist dabei rum gekommen:

// Auschnitt aus der Demo im Anhang
	private void recalc() {
		reset();
		Random r = new Random();
		List<Line> p2p = new ArrayList<Line>(cloud.size());
		List<Line> p2c = new ArrayList<Line>(cloud.size());
		List<Line> p2s = new ArrayList<Line>(cloud.size());
		Map<Point, Lines> map = new IdentityHashMap<Point, Lines>();
		Point a = triangle.get(POINT_A);
		Point b = triangle.get(POINT_B);
		Point c = triangle.get(POINT_C);
		for(Point p1 : cloud) {
			p1.x = r.nextInt(WIDTH - 400);
			p1.y = r.nextInt(HEIGHT - 300);
			if(minQuad.x >= p1.x) {
				minQuad.x = p1.x;
			}
			if(minQuad.y >= p1.y) {
				minQuad.y = p1.y;
			}
			if(maxQuad.x <= p1.x) {
				maxQuad.x = p1.x;
			}
			if(maxQuad.y <= p1.y) {
				maxQuad.y = p1.y;
			}
			Lines l = new Lines();
			l.p2p = new Line(p1, a);
			l.p2s = new Line(p1, centerSphere);
			map.put(p1, l);
			p2p.add(l.p2p);
			p2s.add(l.p2s);
			p2c.add(new Line(p1, centerQuad));
		}
		// p2c enthält nun Linien aller Punkte zu einem möglichen Rechteckmittelpunkt
		// p2p Linien aller Punkte zu einem möglichen Punkt A und
		// p2s Linien aller Punkte zu einem möglichen Kreismittelpunkt
		recalcBox(); // berechnet die BoundingBox (funktioniert)
		Collections.sort(p2c); // sortiert p2c absteigend
		// der erste Eintrag von p2c enthält nun die Linie mit dem
		// grössten Abstand zum Center der BoundingBox...
		Line tmpCenterBox = p2c.remove(0);
		// Linie mit Punkt A aus p2s und p2p entfernen
		Lines tmp = map.get(tmpCenterBox.a);
		p2s.remove(tmp.p2s);
		p2p.remove(tmp.p2p);
		// ... ihr äusserer Punkt wird in Punkt A geschieben.
		a.x = tmpCenterBox.a.x;
		a.y = tmpCenterBox.a.y;

		Collections.sort(p2p); // sortiert p2p absteigend
		// der erste Eintrag von p2p enthält nun die Linie mit dem
		// Punkt mit grösstem Abstand zu Punkt A...
		Line tmpBA = p2p.remove(0);
		// Linie mit Punkt B aus p2s entfernen
		tmp = map.get(tmpBA.a);
		p2s.remove(tmp.p2s);
		// ... dieser wird in Punkt B geschrieben.
		b.x = tmpBA.a.x;
		b.y = tmpBA.a.y;

		// Das Zentrum des Kreises liegt nun auf halber Strecke von AB...
		centerSphere.x = (int) Math.round((b.x - a.x) / 2.0) + a.x;
		centerSphere.y = (int) Math.round((b.y - a.y) / 2.0) + a.y;
		// ... der äusserste Punkt ist A
		s.x = a.x;
		s.y = a.y;

		Line tmpCenterSphere = null;
		double max = Integer.MIN_VALUE;
		do {
			Collections.sort(p2s); // sortiert p2s absteigend
			// Tja, hatte eigentlich angenommen, dass Punkt C hier gleich
			// im ersten Eintrag zu finden ist, aber neee...
			if(tmpCenterSphere == p2s.get(0) || max > p2s.get(0).length()) {
				break;
			}
			tmpCenterSphere = p2s.get(0);
			if(tmpCenterSphere.length() > max) {
				max = tmpCenterSphere.length();
			}
			c.x = tmpCenterSphere.a.x;
			c.y = tmpCenterSphere.a.y;
			recalcCenter();
		} while(true);
		repaint();
	}

Das funktioniert soweit schon mal, allerdings brechen hin und wieder noch ein paar Punkte aus und ich hab' keinen Plan warum. Evtl. ist es doch nicht immer ratsam, von der längsten Strecke AB auszugehen um C dann darüber zu spannen. Jedenfalls kam es vor, das das do-while Konstrukt öfters in einer Endlosschleife endete. Das habe ich durch Feststellen der maximalen Länge aber bereits abgeschaltet. Jemand 'ne Idee, wie es weitergehen kann?
Im übrigen scheint das Verfahren, bei welchem man erst die äussere Hülle sucht inzwischen aufwändiger. Kann aber auch sein, dass ich mich Irre. Kann aber auch sein, dass ich rein Zufällig dieses Verfahren implementiert habe.

 

[Spacerat]

Ich will euch zwar keineswegs mit Ansätzen zuspammen, aber dieses muss noch sein. Es ist eine Verbesserung gegenüber der alten Version, welche im 2. Pass nach Erstellung der Box und festlegen der längsten Strecke statt do-while einfach über die verbleibenden Punkte iteriert und dabei eine Liste von möglichen Radien und Mittelpunkten anlegt. Ich würde sagen, das entspricht einer Laufzeit von O(n) (evtl. das unbenannte Verfahren aus dem PDF von Melfis?).
Leider ist auch diese Version noch nicht ausgereift. Ich komme einfach nicht dahinter, wieso er manchmal keinen Punkt C ausmachen kann. Habe sogar versucht, ob es daran liegen kann, wenn der Kreisdurchmesser grösser als die Diagonale der Box ist. Aber nö... der Umstand tauchte noch nicht auf.
Hoffe nur, der berechnet wirklich die kleinstmöglichen Keise.
Der Quelltext ist dieses mal komplett im Jar.

 

[hüteüberhüte]

Ok, hab mal nachgesehen. Für jeden Punkt ist die Strecke des am weitesten von ihm entfernten Punktes der Radius des Kreises, der alle Punkte umschließt. Dann bleibt nur noch zu ermitteln, welche Strecke am kürzesten ist. Das ist dann der kleinste, alle Punkte umschließende Kreis. Das kann für viele Punkte etwas aufwändig werden, aber es gibt z.B. randomisierte Algorithmen dazu, die auch eine genau Lösung berechnen (siehe Kenneth Clarkson, Convex hull)

 

[hüteüberhüte]

Hier einmal abgetippt:

        Point[] parray = new Point[100];
        for (int i = 0; i < parray.length; i++) {
            parray[i] = new Point((int) (Math.random() * 1000.0), (int) (Math.random() * 1000.0));
        }

        double rmin = Double.MAX_VALUE;
        Point pmin = null;
        for (Point p1 : parray) {
            double rmax = Double.MIN_VALUE;
            for (Point p2 : parray) {
                double dist = p1.distance(p2);
                if (dist > rmax) {
                    rmax = dist;
                }
            }
            if (rmax < rmin) {
                rmin = rmax;
                pmin = p1;
            }
        }

        System.out.println("rmin = " + rmin);
        System.out.println("pmin = " + pmin);

pmin ist der Mittelpunkt und rmin ist der Radius

 

[Spacerat]

Kann man denn davon ausgehen, dass der Mittelpunk definitiv ein Punkt aus der Punktwolke ist? Bei deinem Code ist das zumindest immer der Fall.

 

[hüteüberhüte]

Kann man denn davon ausgehen, dass der Mittelpunk definitiv ein Punkt aus der Punktwolke ist? Bei deinem Code ist das zumindest immer der Fall.

Stimmt, daran hab ich jetzt nicht gedacht. Dann wäre das Verfahren nur annähernd genau, bzw. würde eine Lösung zu einer anderen Problemstellung bestimmen..
sry

 

[AquaBall]

Außerdem wäre das noch lange nicht der kleinste mögliche Kreis!

(Versuch es mit meinen 4 Punkten von oben!)

 

[hüteüberhüte]

Edit: Wenn der Mittelpunkt ein Punkt aus der Punktmenge sein soll, dann schon

 

[Spacerat]

Okay, ich denke ich hab's (siehe Anwendung mit Source im Anhang). Das habe ich zwar schon oft gesagt, aber solange bei dieser Version niemandem Punkte ausserhalb des Kreises auffallen (manchmal sieht es zwar so aus, aber das können nur Rundungsfehler sein), lasse ich die Aussage jetzt mal so stehen.
Erkenntnisse:
1. Richtig! Die Boxdiagonale ist als minimaler Durchmesser definitiv zu gross.
2. Oh Wunder! Die Strecke mit dem grössten Abstand zweier Punkte kann als minimaler Durchmesser schon zu klein sein. Denn
3. Verbleiben Punkte ausserhalb dieses Kreises, muss ein Dreieck aufgespannt werden, dessen Punkte auf dem Kreis liegen. Zu den Punkten des längsten Abstands kommt deswegen noch der am weitesten vom augenblicklichen Mittelpunkt hinzu. Dadurch wird der aktuelle Durchmesser natürlich vergrössert und der Mittelpunkt ändert sich auch.
4. Nachdem sich der Mittelpunkt geändert hat, muss erneut gemessen werden, ob noch Punkte ausserhalb des Kreises liegen. Punkt 3 muss jetzt solange widerholt werden, bis kein Punkt mehr ausserhalb des Kreises liegt oder...
5. Der Fall eintritt, dass einer der Punkte der längsten Strecke nicht Teil der Hülle sind. Das erkennt man daran, wenn die Punkte 3 und 4 zwischen zwei Punkten hin und her springen. Der eine dieser beiden Punkte ist C der andere ersetzt je nach dem, welche Stecke kürzer ist, A oder B.

Ich habe darüber hinaus auch mal wieder überhaupt keine Ahnung, was ich da implementiert habe, ob es den Algo bereits gibt, geschweige denn einen Namen dafür. Sicher ist jedoch, dass er selbst bei massig vielen Punkten - selbst 30000 bearbeitete er in Null Komma Nix - extrem schnell ist.
[EDIT]Ausserdem filtere ich vorm Berechnen auch nicht die Punkte der äusseren Hülle. Beim Erstellen der Box speichere ich wie oben im Code jeden Punkt zusammen mit einem gemeinsamen Mittelpunkt als Linie in einer Liste. Ändert man diesen Mittelpunkt, ändert man auch die Längen all dieser Linien gleichzeitig. Diese Liste lässt sich dann auch nach Längen sortieren.[/EDIT]

 

[Spacerat]

Nun kann ich's nicht mehr editieren, um den letzten Fehler zu Korregieren...
In der Beschreibung muss es bei 5. natürlich "Teil des äusseren Durchmessers" statt "Teil der äusseren Hülle heissen".
Bis auf einen kleinen Bug in "recalcCenter()", der manchmal (eher selten) dafür sorgt, dass ein viel zu grosser Kreis berechnet wird, ist der Algo dennoch recht zuverlässig.
Schnell ist er auch, nachdem alle Punkte in der Liste stehen, benötigt er anscheinend nie mehr als 3 Schritte um Punkt C zu bestimmen. Bleibt nur zu hoffen, dass meine Logik dieses mal 100%ig passt und er wirklich den kleinsten Umkreis berechnet.

 

[Marco13]

Hab' den Thread nur am Rande gelesen und weder die verlinkten Sachen noch den Code im Detail verfolgt, aber...
Die Boxdiagonale ist als minimaler Durchmesser definitiv zu gross.
Wenn mit "Box" die Bounding Box der Punkte gemeint ist, kann ich mir nicht vorstellen, wie ein Kreis aussehen sollte, der alle Punkte enthält, und einen Durchmesser hat, der geringer ist, als die Diagonale.

Ansonsten... fände ich (bei dem angehängten Programm) eine nicht-Box-Förmige Punktverteilung mal interessant. Gelegentlich erschienen Punkte außerhalb des Kreises... und so weit dass ich persönlich es nicht mehr auf "Rundungsfehler" schieben würde. Aber ich habe mir den Code nicht angesehen.

Teilweise erinnerte mich das an Delaunay-Triangulation ? Wikipedia - aber eben genau das "Gegenteil" davon: Statt sicherzustellen, dass der Umkreis eines Dreiecks KEINE anderen Punkte enthält, muss man sicherstellen, dass man einen findet, der ALLE Punkte enthält.

Hat jemand mal den Linear Programming Ansatz von Megiddo probiert?

Ich würde spontan erstmal einen Graham Scan für die konvexe Hülle machen, und schauen, was man mit den Hüllenpunkten so alles anfangen kann.

 

[Spacerat]

Kennt ihr das Gefühl? Jahrelang macht man etwas falsch ohne es zu hinterfragen, weil's einleuchtend ist...

Ja, die BoundingBox ist gemeint. Dachte bisher auch, dass da nichts drunter geht, wurde im Verlauf dieses Themas aber eines besseren belehrt. Deswegen arbeitete ich am WE auch so akribisch an dieser Mini-Anwendung.
Was genau meinst du eigentlich mit "nicht boxförmiger Punkteverteilung"? Jedes Objekt hat eine BoundingBox, dessen Abmaße sich aus ihren Punkten ergeben. Eine Kugel mit dem Durchmesser der Box-Diagonale umschliesst zwar definitiv alle Punkte des Objektes, aber keiner dieser Punkte läge auf ihrer Aussenhaut, wenn er nicht eine Ecke dieser Box ist.
Am besten erklärt das wohl einem sein bestes 3D-Programm. In diesem erstelle man eine Kugel, lässt sich davon die BoundingBox errechnen und aus dieser wiederum die BoundingSphere. Der Durchmesser dieser BoundingSphere wäre um den Faktor Wurzel 3 (Wurzel 2 bei 2D) höher als der Durchmesser der vorher erstellten Kugel. Die kleinste BoundingSphere einer Kugel aber ist die Kugel selber. Ergo, gibt es was kleineres, als den Durchmesser der Box-Diagonale. Für diese Einsicht brauchte ich knapp 10 Jahre, was solls, bin Autodidakt.
Daher müssen es also Rundungsfehler sein, denn wenn man im Quelltext überall, wo "Math.round()" verwendet wird, "Math.ceil()" einsetzt, sieht man womöglich nie mehr einen Punkt ausserhalb des Kreises. Sooft, wie ich nun schon auf "recalc" geklickt habe ist das jedenfalls noch nicht passiert.
Was aber sein kann, die aufgespannten Dreiecke in der Anwendung haben grösstenteils immer rund 90° an einem Punkt. Denkbar, dass Dreiecke mit rund 60° an den Ecken zu einem noch kleinerem Durchmesser führen könnten.
[EDIT]BTW.: Graham-Scan? OMG... da muss ich erst mal durchsteigen... Evtl. kann ja jemand noch mal seine TODO-Liste überarbeiten und das übernehmen. Bin gespannt, ob man damit noch kleinere Durchmesser hinbekommt.[/EDIT]

 

[Marco13]

Aaaah ja, wenn es um die (Axis Aligned) Bounding Box von beliebig vielen Punkten geht (und nicht nur zwei), ist es ja klar (schon die Bounding Box einer um 45° gedrehten Box wäre ja zu groß). (Ich hatte mir schon so oft vorgenommen, in Gremlin-Manier nicht mehr nach 0:00 zu versuchen, zu Themen zu antworten, wo man denken muss )

Der Graham Scan ist gar nicht sooo kompliziert, wie er auf der Wiki-Seite aussieht, hab' den schon mal implementiert. BTW: Wie fast immer bei solchen Fragen findet man die "Komplettlösung" auf Geometric Tools: Containment (und die sind i.a. sehr leicht nach Java zu portieren... ich kenne Anwendungen, die für viel Geld verkauft werden, und zu einem nicht unerheblichen Teil aus Funktionen bestehen, die von dieser Lib portiert wurden). Im speziellen eine Implementierung von "Welzl's Algorühdmuß" in http://www.geometrictools.com/LibMathematics/Containment/Wm5ContMinCircle2.cpp

 

[Spacerat]

Aaaah ja, wenn es um die (Axis Aligned) Bounding Box von beliebig vielen Punkten geht (und nicht nur zwei), ist es ja klar (schon die Bounding Box einer um 45° gedrehten Box wäre ja zu groß). (Ich hatte mir schon so oft vorgenommen, in Gremlin-Manier nicht mehr nach 0:00 zu versuchen, zu Themen zu antworten, wo man denken muss )

Aber jetzt ist Nachmittag... 0° wären doch perfekt. Also wäre sogar eine nur geringfügig gedrehte BoundingBox schon zu gross. 45° wären deswegen der worst case. Bis 90° würde sie wieder kleiner. Dieser Verlauf widerholt sich auf einer gesamten Umkreisung ganze 4 Mal.
Es zeichnet sich gerade ab, dass der durch die Anwendung gefundene Durchmesser immer noch nicht der kleinstmögliche ist. Bei dem Verfahren handelt es sich wohl wahrhaftig um jenes, welches in Melfis PDF nicht benannt wurde. Die Laufzeit von Verfahren, bei welchem man erst die äussere Hülle definiert sind definitiv stets langsamer. Liegt am Algo zum auffinden dieser Hülle, im Gegensatz zum Sammeln der Punkte als Linien zu einem gemeinsamen Fixpunkt schafft man das nicht in O(n).
Wenn man als erste Strecke AB (Durchmesser) die längste mal "sqrt(3) / 6" nimmt, davon die nächst höhere und die nächst kleinere, kann man ein Dreieck wie in meiner nächtlichen Hypothese gestern angenommen habe aufspannen, dessen Umkreismittelpunkt auch jenen Punkt der längsten Stecke einschliesst. Diese Erkenntnis ergibt sich aus der Umkreisformel eines Gleichseitigen Dreiecks. Schneller geht's nicht. Der Nachteil: Man hat keine äussere Hülle der Punktwolke und wenn man später noch triangulieren will, fängt man erneut an zu rechnen. Was dann rum kommt liegt ungefähr bei einer Laufzeit von O(n + n log n).

 

[Spacerat]

Das war voreilig... kann gelöscht werden...

 

[Spacerat]

So, die letzten aller Erkenntnisse:
1.

... längste mal "sqrt(3) / 6"

Was Blödsinn. "Radius mal Wurzel 3" oder "Durchmesser durch 2 mal Wurzel 3" natürlich.
2. Der Plan mit den gleichseitigen Dreicken war nur scheinbar ein guter. Grösstenteils ist ein entsprechender Algo viel langsamer als als mein vorheriger und liefert trotzdem die gleichen Ergebnisse.
3. Wenn's in meinem vorherigen Algo anfängt zwischen zwei Punkten zu "zappeln", verkürzt sich der Durchmesser dadurch auch. Im Programm muss dann der entsprechende Punkt mit C ausgetauscht und erneut getestet statt abgebrochen werden.
4. Bei den neuen Tests (max. +2 Berechnungen) kann es passieren, dass nun die neue Strecke AB ebenfalls wieder bereits den Durchmesser liefert.

Das Bild im Anhang zeigt, dass der Algo auch ungefähr gleichseitige Dreiecke berechnet und dazu nicht mehr als 5 Berechnungen benötigt. Das macht er evtl. nur bei weniger Punkten, weil sich diese besser auf der Fläche verteilen können.

Wer noch interesse an der finalen Anwendung hat, bitte sagen.

 

[Crian]

Du kannst ja deinen Kreis spaßeshalber gegen

• Für alle Paare (Pi; Pj) von Punkten aus S testen wir, ob der Kreis mit
dem Durchmesser von Pi nach Pj alle anderen Punkte enthält.
• Für alle Tripel (Pi; Pj ; Pk) von Punkten aus S testen wir, ob der Umkreis U(Pi; Pj ; Pk) alle anderen Punkte enthält.
• Von allen dabei gefundenen Kreisen, die alle Punkte enthalten, nehmen wir den kleinsten.

stellen.

 

[Spacerat]

Klar, mach ich spasseshalber mal...
Da kann nur bei rumkommen, dass ich bei meinem Algo anfangs manchmal gar nicht die längste Strecke zwischen zwei Punkten ermittle, sondern die 2. längste. Wenn das passiert, fängt der Algo vermutlich an zu zappeln. Faktisch zappelt er dann zwischen den beiden Punkten der eigentlich längsten Strecke, welche nun zu AB wird und der Punkt von Ex-AB, welcher weiter von dem neuen Mittelpunkt dieser Strecke weg ist, evtl. Punkt C.

Ich liste den Algo nun nochmal zusammenfassend auf, denn so scheint's zu gehen.

1. Erstellen der BoundingBox. Dabei muss über jeden Punkt iteriert werden und wo man schon dabei
   ist, kann dabei jeder Punkt als Linie zu einem noch nicht festgelegten fixpunkt in einer Liste
   angelegt werden.
2. Den noch nicht festgelegten Fixpunkt in das Zentrum der Box legen und die Liste der Linien
   der Länge nach absteigend sortieren. Der erste Eintrag der Liste ist Punkt A des Dreiecks.
3. Den gemeinsamen Fixpunkt auf Punkt A legen und Liste erneut absteigend sortieren. Der
   erste Eintrag ist Punkt B des Dreiecks.
4. Den Mittelpunkt der Strecke AB in den Fixpunkt legen, erneut absteigend sortieren.
5. Wenn der erste Eintrag kürzer als die halbe Strecke AB ist, ist der augenblickliche Fixpunkt
   der gesuchte Mittelpunkt, Strecke AB der Kreisdurchmesser und der Algo ist fertig.
6. Sonst enthält der Erste Eintrag der Liste Punkt C des Dreiecks.
7. Umkreismittelpunkt des Dreiecks berechnen und in Fixpunkt legen, Liste mal wieder
   absteigend sortieren.
8. Ist der erste Eintrag länger als der augenblickliche Kreisradius, war AB nicht die längste
   Strecke. Der erste Eintrag der Liste und Punkt C bilden nun die neue Strecke AB. Der Algo
   wird ab 4. widerholt.
9. Der Algo ist durch.

 

[Spacerat]

Der Vollständigkeit halber sei hier noch mal die Finale Anwendung (2D) verlinkt, da sie bereits in einem anderen Thema veröffentlicht wurde. Nun das Ganze noch in 3D visualisieren, dann soll's gut sein.
BoundingSphere2DDemo