Kreis um Punkte

[Matthias Frey]

Hallo,

ich suche einen Algorithmus. Es soll ein Kreis bestimmt werden, der um alle
gegebenen Punkte geht.
Alle Punkte liegen in einer Ebene. Der Kreis soll kleinstmöglich sein, alle
Punkte sollen auf oder im Kreis liegen.

Habe schon etwas gegoogelt, aber alles was ich finde ist ein Kreis
um die Punkte eines Dreiecks

Der Algorithmus sollte ab drei Punkte funktionieren.

Weiss jemand was oder mit welchen Begriffen man suchen könnte?
Danke.

Matthias

[Ralf Goertz]

Am Thu, 7 Jan 2021 16:53:25 +0100

Post by Matthias Frey
Hallo,
ich suche einen Algorithmus. Es soll ein Kreis bestimmt werden, der
um alle gegebenen Punkte geht.
Alle Punkte liegen in einer Ebene. Der Kreis soll kleinstmöglich
sein, alle Punkte sollen auf oder im Kreis liegen.
Habe schon etwas gegoogelt, aber alles was ich finde ist ein Kreis
um die Punkte eines Dreiecks
Der Algorithmus sollte ab drei Punkte funktionieren.
Weiss jemand was oder mit welchen Begriffen man suchen könnte?
Danke.

Ich würde es mit der konvexen Hülle versuchen
<https://de.wikipedia.org/wiki/Konvexe_H%C3%BClle>. Damit hättest du das
Problem gegebenfalls auf weniger Punkte bzw. darauf reduziert, den
kleinsten Kreis um ein konvexes Polygon zu finden, was mir deutlich
leichter zu sein scheint.

[Helmut Richter]

Post by Ralf Goertz
Am Thu, 7 Jan 2021 16:53:25 +0100

Post by Matthias Frey
Hallo,
ich suche einen Algorithmus. Es soll ein Kreis bestimmt werden, der
um alle gegebenen Punkte geht.
Alle Punkte liegen in einer Ebene. Der Kreis soll kleinstmöglich
sein, alle Punkte sollen auf oder im Kreis liegen.
Habe schon etwas gegoogelt, aber alles was ich finde ist ein Kreis
um die Punkte eines Dreiecks
Der Algorithmus sollte ab drei Punkte funktionieren.
Weiss jemand was oder mit welchen Begriffen man suchen könnte?
Danke.

Ich würde es mit der konvexen Hülle versuchen
<https://de.wikipedia.org/wiki/Konvexe_H%C3%BClle>. Damit hättest du das
Problem gegebenfalls auf weniger Punkte bzw. darauf reduziert, den
kleinsten Kreis um ein konvexes Polygon zu finden, was mir deutlich
leichter zu sein scheint.

Im Rademacher/Toeplitz steht ein Kapitel drüber drin; der dort gewählte
Ausdruck heißt „Pferchkreis eines Punkthaufens“, andere nennen ihn
„Hüllkreis“. Hier haben wir es im Frühjahr 2005 diskutiert. Mein letzter
Beitrag im Thread:

---- ab hier Zitat eines alten Beitrags ----

Newsgroups: de.sci.mathematik
From: Helmut Richter
Subject: Re: Kreisberechnung um 5 Punkte
References: <***@posting.google.com>
<d0t42o$mpi$***@online.de>
Reply-To: hhr-***@web.de
Date: Mon, 21 Mar 2005 13:11:31 +0100
Message-Id: <***@lxhri01.lrz.lrz-muenchen.de>
Mime-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Transfer-Encoding: 8bit
User-Agent: slrn/0.9.7.3 (Linux)

Post by Ralf Goertz
Vielleicht hilft ja auch der Satz von Heinrich W. E. Jung (1876 - 1953)
http://www.mathematik.uni-halle.de/history/jung/index.html
http://mathworld.wolfram.com/JungsTheorem.html
http://dz-srv1.sub.uni-goettingen.de/sub/digbib/loader?did=D261177

Mindestens der letzte Link ist unzugänglich.

Aber egal, wir hatten die meisten Ergebnisse hier schon im Thread. Weil
sie so verstreut sind, fasse ich sie noch einmal zusammen, nicht zuletzt
für mich selbst.

Def.: Ein Punkthaufen (das ist die Terminologie in Toeplitz/Rademachers
Buch) ist eine endliche, mindestens zweielementige Menge von Punkten in
der Ebene.

Def.: Der Hüllkreis (T/R nennen das "Pferchkreis", aber das ist
unglücklich, weil das Wort in der Messtechnik etwas anderes bezeichnet)
eines Punkthaufens ist der kleinste Kreis, der alle Punkte des
Punkthaufens enthält.

Der Hüllkreis ist eindeutig, und er ist der Hüllkreis einer zwei- oder
dreielementigen Teilmenge des Punkthaufens. Im zweielementigen Fall liegen
die beiden Punkte sich auf dem Kreis gegenüber, im dreielementigen Fall
bilden die drei Punkte ein spitzwinkliges Dreieck. Das hatte ich im Thread
vorausgesetzt, ohne es zu beweisen; hole ich unten nach.

Die zwei bzw. drei Punkte nenne ich "Stützpunkte" des Kreises; liegen mehr
als drei Punkte des Punkthaufens auf der Kreislinie, gibt es
möglicherweise mehr als ein spitzwinkliges Dreieck von Stützpunkten, aber
das ist egal: man kann dann irgendeines nehmen.

Damit hat man einen Algorithmus: Man beginne mit zwei Punkten als
Stützpunkten und dem Kreis dazu. Solange noch Punkte außerhalb des Kreises
liegen, konstruiert man den Hüllkreis der Menge, die aus einem der Punkte
außerhalb sowie den alten Stützpunkten besteht, und macht dann mit den
Stützpunkten des neuen Hüllkreises weiter. Da es nur endlich viele
potentielle Hüllkreise gibt und die Radien immer größer werden, terminiert
das Verfahren. Es terminiert aber nicht, bevor alle Punkte eingefangen
sind. Daher liefert es die Lösung.

Man darf nicht glauben, dass ein einmal eingefangener Punkt in den
folgenden Kreisen weiterhin enthalten ist - das ist i.A. nicht wahr. Das
macht aber nichts, weil er später wieder eingefangen wird, wenn er
entwischt ist.

Um die blöde Rechnerei nicht zu oft machen zu müssen, möchte man bald
große Kreise haben. Das macht man, indem man mit zwei weit entfernten
Punkten beginnt und dann immer recht weit entfernte dazunimmt. Viel Grips
in die Entfernungsberechnungen zu stecken lohnt aber nicht, weil
mitnichten die entferntesten auch die besten Punkte zum Weitermachen sind.
Ich würde vorschlagen, am Anfang den nördlichsten, südlichsten,
östlichsten und westlichsten Punkt zu nehmen und mit diesen zwei bis vier
Punkten zu beginnen; die Reduktion von vier Punkten auf drei braucht man
im Algorithmus eh.

So, und jetzt die fehlenden Sätze:

Satz 1: Der Hüllkreis ist eindeutig.

Beweis: Gäbe es zwei Hüllkreise, so würden sie sich in einem
Kreisbogenzweieck schneiden, das alle Punkte des Punkthaufens enthält. Das
hätte aber einen kleineren Hüllkreis.

Satz 2: Der Hüllkreis enthält nicht zwei Punkte des Punkthaufens in der
Weise, dass sie sich nicht gegenüberliegen und der längere der beiden
Kreisbögen keinen weiteren Punkt des Punkthaufens enthält.

Beweis: Wir teilen die Ebene mittels der Geraden durch die beiden Punkte
in zwei Halbebenen. Sei R die Halbebene (ohne die Gerade), die den
längeren Kreisbogen enthält und sei K die Menge der Punkte des
Punkthaufens, die in R liegen. Wir bestimmen nun den kleinsten Winkel
alpha unter den Winkeln, unter denen von einem Punkt aus K die Strecke
zwischen den beiden gegebenen Punkten erscheint. Dann unterscheiden wir:

- Ist alpha > 90° oder ist K leer, so ist der Kreis ein Hüllkreis, der die
Strecke zwischen den beiden Punkten als Durchmesser hat.

- Sonst ist der Fasskreis zum Winkel alpha über dieser Strecke der
Hüllkreis.

In beiden Fällen ist der neu konstruierte Hüllkreis kleiner als der
gegebene, im Gegensatz zur Minimaleigenschaft.

Satz 3: Der Hüllkreis eines Punkthaufens enthält mindestens zwei Punkte
davon. Wenn er genau zwei Punkte enthält, liegen sie sich auf dem Kreis
gegenüber.

Beweis: Im Fall von zwei Punkten folgt das aus Satz 2. Im Fall von keinem
oder einem Punkt ließe sich der Punkthaufen um zwei bzw. einen Punkt so
ergänzen, dass Satz 2 verletzt würde.

Satz 4: Der Hüllkreis der Ecken eines spitzwinkligen Dreieck ist dessen
Umkreis.

Beweis: Nach Satz 3 gibt es nur drei Kandidaten für einen Hüllkreis mit
nur zwei Punkten darauf. Die funktionieren alle nicht. Also muss der
Hüllkreis durch alle drei Punkte gehen und das tut nur der Umkreis.

Satz 5: Der Hüllkreis eines Punkthaufens ist der Hüllkreis einer zwei-
oder dreielementigen Teilmenge des Punkthaufens.

Beweis: Der Hüllkreis enthält mindestens zwei Punkte des
Punkthaufens. Enthält er mehr als drei, so kann man welche weglassen,
solange das Dreieck spitzwinklig bleibt; das lässt sich immer erreichen,
wenn sich nicht zwei Punkte gegenüberliegen.

Das wars.

[Alfred Flaßhaar]

Post by Matthias Frey
Hallo,
ich suche einen Algorithmus. Es soll ein Kreis bestimmt werden, der um
alle gegebenen Punkte geht.
Alle Punkte liegen in einer Ebene. Der Kreis soll kleinstmöglich sein, alle
Punkte sollen auf oder im Kreis liegen.

(...)

Lege irgendein cartesisches Koordinatensystem in die Punktewolke und
bestimme den Schwerpunkt (dessen Koordinsaten) als Mittelpunkt des
gesuchten Kreises.
Oder:
Bestimme die Koordinaten des Mittelpunktes des gesuchten Kreises aus dem
Minimum der Abstandsquadrate zu den Punkten der Wolke.

[Ralf Goertz]

Am Thu, 7 Jan 2021 17:27:57 +0100

Post by Alfred Flaßhaar

Post by Matthias Frey
Hallo,
ich suche einen Algorithmus. Es soll ein Kreis bestimmt werden, der
um alle gegebenen Punkte geht.
Alle Punkte liegen in einer Ebene. Der Kreis soll kleinstmöglich
sein, alle Punkte sollen auf oder im Kreis liegen.

(...)
Lege irgendein cartesisches Koordinatensystem in die Punktewolke und
bestimme den Schwerpunkt (dessen Koordinsaten) als Mittelpunkt des
gesuchten Kreises.

Hm, funktioniert das? Nimm zum Beispiel folgende („lineare“) Punktwolke:

*-------------------------------------------------------------**********
^ Schwerpunkt

Wenn ich den Mittelpunkt in den Schwerpunkt lege, bekomme ich sicher
nicht den kleinsten Kreis.

Post by Alfred Flaßhaar
Bestimme die Koordinaten des Mittelpunktes des gesuchten Kreises aus
dem Minimum der Abstandsquadrate zu den Punkten der Wolke.

Das würde oben (wenn ich richtig verstehe, was du meinst) zu einem
ähnlichen Mittelpunkt führen.

[Alfred Flaßhaar]

Post by Ralf Goertz
Am Thu, 7 Jan 2021 17:27:57 +0100

Post by Alfred Flaßhaar
(...)
Lege irgendein cartesisches Koordinatensystem in die Punktewolke und
bestimme den Schwerpunkt (dessen Koordinsaten) als Mittelpunkt des
gesuchten Kreises.

*-------------------------------------------------------------**********
^ Schwerpunkt
Wenn ich den Mittelpunkt in den Schwerpunkt lege, bekomme ich sicher
nicht den kleinsten Kreis.

(...)

Der kleinste Kreis hätte hier den Schwerpunkt als Mittelpunkt und der
Ausreißer liegt auf dem Kreis, die Wolke liegt im Kreis. Welcher
umhüllende Kreis, der alle Punkte der Wolke erwischt, hätte einen
kleineren Durchmesser?

[Ralf Goertz]

Am Thu, 7 Jan 2021 17:54:46 +0100

Post by Alfred Flaßhaar

Post by Ralf Goertz
Am Thu, 7 Jan 2021 17:27:57 +0100

Post by Alfred Flaßhaar
(...)
Lege irgendein cartesisches Koordinatensystem in die Punktewolke
und bestimme den Schwerpunkt (dessen Koordinsaten) als Mittelpunkt
des gesuchten Kreises.

*-------------------------------------------------------------**********
^ optimaler MP ^ Schwerpunkt
Wenn ich den Mittelpunkt in den Schwerpunkt lege, bekomme ich sicher
nicht den kleinsten Kreis.

(...)
Der kleinste Kreis hätte hier den Schwerpunkt als Mittelpunkt und der
Ausreißer liegt auf dem Kreis, die Wolke liegt im Kreis. Welcher
umhüllende Kreis, der alle Punkte der Wolke erwischt, hätte einen
kleineren Durchmesser?

Siehe oben.

[Rainer Rosenthal]

Post by Alfred Flaßhaar

Post by Ralf Goertz
*-------------------------------------------------------------**********
                                                    ^ Schwerpunkt
Wenn ich den Mittelpunkt in den Schwerpunkt lege, bekomme ich sicher
nicht den kleinsten Kreis.

(...)
Der kleinste Kreis hätte hier den Schwerpunkt als Mittelpunkt und der
Ausreißer liegt auf dem Kreis, die Wolke liegt im Kreis. Welcher
umhüllende Kreis, der alle Punkte der Wolke erwischt, hätte einen
kleineren Durchmesser?

Hallo Alfred,

gutes Neues!
Nenne den Punkt links außen L und den rechts außen R.
Ralf will bestimmt darauf hinaus, dass der Mittelpunkt M von L und R ein
guter Kandidat für den Mittelpunkt des kleinsten Kreises wäre.
Und ich stimme ihm zu.

Was haben wir übersehen?

Lieben Gruß,
Rainer

[Alfred Flaßhaar]

Post by Ralf Goertz
*-------------------------------------------------------------**********
                                                    ^ Schwerpunkt
Wenn ich den Mittelpunkt in den Schwerpunkt lege, bekomme ich sicher
nicht den kleinsten Kreis.

(...)

Ja, ihr habt Recht, habe den Sonderfall nicht gesehen. Ein
eindimensionales Gebilde einzupacken ist wohl gesondert zu untersuchen.
Vielleicht hilft es, ein Raster/Gitter in die Wolke zu legen und brutal
drauflos zu rechnen, jeden Gitterpunkt zu prüfen als Kreismittelpunkt.
Trotzdem "glaube" ich, daß bei echt zweidimensional angeordneter Wolke
der gesuchte Kreismittelpunkt nicht weit weg vom Schwerpunkt liegt und
als Startwert für eine Suche genutzt werden kann, weil eben ein Kreis
gesucht wird.

Und auch euch ein gesundes Neues.

Wünscht Alfred

[Rainer Rosenthal]

Post by Alfred Flaßhaar
Trotzdem "glaube" ich, daß bei echt zweidimensional angeordneter Wolke
der gesuchte Kreismittelpunkt nicht weit weg vom Schwerpunkt liegt und
als Startwert für eine Suche genutzt werden kann, weil eben ein Kreis
gesucht wird.

Du glaubst halt an das Gute in den Punktwolken.
Aber Ralfs Beispiel zeigt auch hier die latente Boshaftigkeit
zweidimensionaler Punktwolken:

Um einen Punkt P scharen sich tausende von Punkten in einem kleinen
Kreis von 5 cm Durchmesser. Selbst wenn der Schwerpunkt S aller dieser
Punkte sehr dicht bei P liegt oder sogar P = S ist und P der
Kreismittelpunkt, nützt das gar nichts, wenn die einzukreisende
Punktwolke aus diesen tausenden von Punkten *und* einem drei Kilometer
entfernten Punkt besteht.
Der gesuchte Kreismittelpunkt M ist dann etwa drei Kilometer von P entfernt.

Herzlich grüßend,
Rainer

[Stephan Gerlach]

Post by Rainer Rosenthal

Post by Alfred Flaßhaar
Trotzdem "glaube" ich, daß bei echt zweidimensional angeordneter Wolke
der gesuchte Kreismittelpunkt nicht weit weg vom Schwerpunkt liegt und
als Startwert für eine Suche genutzt werden kann, weil eben ein Kreis
gesucht wird.

Du glaubst halt an das Gute in den Punktwolken.

Was Alfred schreibt, ist ja auf den ersten Blick intuitiv irgendwie
einleuchtend.
Auf den zweiten, genaueren Blick leider nicht mehr.
Ein gutes Beispiel dafür, daß die (erste) Anschauung in der Mathematik
oft trügerisch sein kann.

Post by Rainer Rosenthal
Aber Ralfs Beispiel zeigt auch hier die latente Boshaftigkeit
Um einen Punkt P scharen sich tausende von Punkten in einem kleinen
Kreis von 5 cm Durchmesser. Selbst wenn der Schwerpunkt S aller dieser
Punkte sehr dicht bei P liegt oder sogar P = S ist und P der
Kreismittelpunkt, nützt das gar nichts, wenn die einzukreisende
Punktwolke aus diesen tausenden von Punkten *und* einem drei Kilometer
entfernten Punkt besteht.
Der gesuchte Kreismittelpunkt M ist dann etwa drei Kilometer von P entfernt.

Ganz so krass ist die Sachlage dann doch nicht; ich würde hier ungefähr
1,5 Kilometer Entfernung vorschlagen?!

Es gibt auch ein noch einfacheres Beispiel:
* C
* A
* B

Man betrachte das gleichschenkliche Dreieck ABC.
Annahmen (näherungsweise):
AB = AC = 1 LE
S ... Schwerpunkt des Dreiecks
M ... Mittelpunkt des "Minimalkreises"
Dann gilt (näherungsweise)
AS = 2/3 LE, aber
AM = 1/2 LE.

[Ralf Goertz]

Am Thu, 7 Jan 2021 18:39:49 +0100

Post by Rainer Rosenthal

Post by Alfred Flaßhaar
Trotzdem "glaube" ich, daß bei echt zweidimensional angeordneter
Wolke der gesuchte Kreismittelpunkt nicht weit weg vom Schwerpunkt
liegt und als Startwert für eine Suche genutzt werden kann, weil
eben ein Kreis gesucht wird.

Du glaubst halt an das Gute in den Punktwolken.
Aber Ralfs Beispiel zeigt auch hier die latente Boshaftigkeit
Um einen Punkt P scharen sich tausende von Punkten in einem kleinen
Kreis von 5 cm Durchmesser. Selbst wenn der Schwerpunkt S aller
dieser Punkte sehr dicht bei P liegt oder sogar P = S ist und P der
Kreismittelpunkt, nützt das gar nichts, wenn die einzukreisende
Punktwolke aus diesen tausenden von Punkten *und* einem drei
Kilometer entfernten Punkt besteht.
Der gesuchte Kreismittelpunkt M ist dann etwa drei Kilometer von P entfernt.

Alfreds Intuition ist ja auch gar nicht so verkehrt, wenn man statt
aller Punkte nur die betrachtet, die auf der konvexen Hülle liegen. Auch
dann stimmt's nicht, wie Stephans Beispiel zeigt. Aber die Approximation
ist sicher besser, weshalb ich ja die Betrachtung der konvexen Hülle
überhaupt vorgeschlagen habe. Allerdings scheint es nach oberflächlichem
Blick auf die Wiki-Seiten zur konvexen Hülle und zum Hüllkreis doch eher
so zu sein, dass letzterer in linearer Zeit zu finden ist, während die
Suche nach ersterem äquivalent zur Sortierung zu sein scheint („For a
finite set of points in the plane the lower bound on the computational
complexity of finding the convex hull represented as a convex polygon is
easily shown to be the same as for sorting using the following
reduction…“), von der ich mich zu erinnern glaube, dass sie im Mittel
mindestens O(n log n) ist.

[Alfred Flaßhaar]

Post by Ralf Goertz
Am Thu, 7 Jan 2021 18:39:49 +0100

(...)

Ok, die Gegenbeispiele zeigen, daß ich "intuitiv" auf die Fragestellung
hereingefallen bin. Nun habe ich inzwischen etwas zu diesem für mich
neuen Thema gelesen und ich möchte es so, wie ich es verstanden habe
hier zur Kritik stellen, weil das eine sehr interessante Fragestellung
ist. Eine geschlossene allgemeine Lösung im klassischen Sinne gibt es
anscheinend nicht. Also rechnet man entweder eine Unzahl von
Möglichkeiten brutal durch oder es wird iteriert, wie es z. B. in
https://www.informatik.uni-leipzig.de/~stjaenicke/ag/6-Smallest_Enclosing_Discs.pdf
auf Seite 7, Pkt. 3, demonstriert wird.

Grundsätzlich gilt theoretisch, daß genau eine Lösung existiert und die
durch drei Punkte der konvexen Hülle als Kreis verläuft (den
Diametralfall lasse ich hier mal weg). Daher bietet sich bekannterweise
an, alle Punktetripel der Wolke als kreiserzeugend durchzuprobieren -
ein Kreis aus der so produzierten Menge ist es dann.

Bleibt für mich die Frage:
Gibt es ein Konstruktions-/Rechenverfahren, daß nach endlich vielen
Schritten den gesuchten Kreis mit vorgegebener Genauigkeit findet?

Literaturhinweise, die mehr topologisch orientiert und weniger den
Computer, dessen Architektur oder auch die Wahrscheinlichkeitsrechnung
benötigen wären mir sehr willkommen.

Freundliche Grüße, Alfred Flaßhaar

[Carlo XYZ]

.. Allerdings scheint es nach oberflächlichem
Blick auf die Wiki-Seiten zur konvexen Hülle und zum Hüllkreis doch eher
so zu sein, dass letzterer in linearer Zeit zu finden ist, während die

Durch einen nicht ganz offensichtlichen und außerdem
randomisierten Algorithmus (Welzl).

Suche nach ersterem äquivalent zur Sortierung zu sein scheint („For a
finite set of points in the plane the lower bound on the computational
complexity of finding the convex hull represented as a convex polygon is
easily shown to be the same as for sorting using the following
reduction…“), von der ich mich zu erinnern glaube, dass sie im Mittel
mindestens O(n log n) ist.

Was ja immerhin um einiges besser ist als der
naive Ansatz mit einem genügend großen Umkreis,
den man sukzessive verkleinert.

Ein etwas neuerer Übersichtsartikel:

<http://www.lix.polytechnique.fr/Labo/Frank.Nielsen/pdf/2009-EnclosingBallMachineLearning-IJCGA.pdf>

[Alfred Flaßhaar]

(...)

Post by Carlo XYZ
<http://www.lix.polytechnique.fr/Labo/Frank.Nielsen/pdf/2009-EnclosingBallMachineLearning-IJCGA.pdf>

Das hilft weiter und der Satz von Jung. :-)

[Alfred Flaßhaar]

(...)

Post by Carlo XYZ
<http://www.lix.polytechnique.fr/Labo/Frank.Nielsen/pdf/2009-EnclosingBallMachineLearning-IJCGA.pdf>

Und noch ´ne Literatur für Computerfreaks:

Solution Methodologies for the Smallest Enclosing Circle Problem
Sheng Xu, Robert M. Freund, Jie Sun

Gruß, Alfred

[Jens Kallup]

Hallo,

Danke Alfred für Deinen Link.
Ich habe mal ein sehr einfaches Beispiel für dieses
Problem erarbeitet.

Als Resultat ist eine Internet Seite entstanden die,
so wie ich denke, recht komfortabel bedienbar ist.

Es muss keine Software zusätzlich installiert werden.
Browser müsste aber neueren Datums sein.

Einfach mal aufrufen (test1.html) mit der Maus im
großen Quader Punkte (gut Rechtecke) setzen und dann
unten auf die Buttons klicken.

Wie gesagt alles nur einfache Sachen, daher werden
bei zu großen oder zu kleinen Abständen Fehler
auftreten.

Falls Dir die Technik/Umsetzung beliebt, kannst Du
ja vom Browser den Seitentext (Quellcode) anzeigen
lassen.

Ok, nun aber viel Spaß !
Hier noch der Link:

http://www.kallup.net/news/canvas/

Gruß, Jens

[Jens Kallup]

muss irgendwie am webserver liegen.
den muss ich mal richtig einstellen, weil kein zugriff ist.

Im Anhang die HTML Datei, einfach auf Datenträger speichern,
browser öffnen, und unter Datei->Öffnen die abgespeicherte
Datei öffnen.

Ansonsten wie gehabt.

Gruß, Jens

<!DOCTYPE html>
<html>
<head><title>test1</title></head>
<body>
<canvas id="myCanvas" width="400" height="400" style="border:1px solid
#011d00;">
</canvas><p>
<button onClick="clearAll()" >clear All</button>
<button onClick="clearBoard()">clear board</button>
<button onClick="setPoints()" >draw points </button>
<br>
<button onClick="drawCircle()" >draw circle </button>
</p>
<script>
var can, ctx;
var pos = { x: 0, y: 0 };
var tmp = [];

var points = [];

function init()
{
// reset buffer ...
points = [];

// get canvas ...
can = document.getElementById("myCanvas");
ctx = can.getContext('2d');

// set mouse handler ...
can.addEventListener('mousedown', draw);
can.addEventListener('mouseenter', setPosition);
}

function setPosition(e) {
pos.x = e.clientX;
pos.y = e.clientY;
}

function draw(e) {
setPosition(e);
if (e.buttons !== 1) return;

var pnt = { x: pos.x+5, y: pos.y+5 };
points.push(pnt);

// draw rect as point
ctx.beginPath(); // begin
ctx.rect(pos.x-5,pos.y-5,5,5);
ctx.fillStyle = 'black';
ctx.fill();
ctx.stroke();
}

function clearAll() {
ctx.clearRect(0, 0, can.width, can.height);
points = [];
}
function clearBoard() {
ctx.clearRect(0, 0, can.width, can.height);
}
function setPoints() {
ctx.clearRect(0, 0, 400, 400);
for (var len = 0; len < points.length; len++) {
ctx.beginPath();
ctx.rect(
points[len].x-10,
points[len].y-10,5,5);
ctx.fillStyle = 'black';
ctx.fill();
ctx.stroke();
}
}
function drawCircle()
{
let len, found;

let xmin, ymin;
let xmax, ymax;

pt_alt = 0;

// kein Punkt vorhanden? ...
if (points == undefined)
return;

if (points.length < 1) {
console.log('kein Punkte.');
return;
}

console.log('Punkte: ' + points.length);

// minimum links
// aufsteigend sortieren nach xpos ...
points.sort(function(a,b) {
var keyA = a.x;
var keyB = b.x;

if (keyA < keyB) return -1;
if (keyA > keyB) return 1;

return 0;
});
console.log('minimum:');
found = false;
for(xmin = 0; xmin < 400; xmin++) {
for (len = 0; len < points.length; len++) {
if (points[len].x <= xmin) {
console.log('x-min: --> ' + xmin);
found = true;
break;
}
}
// alle anderen Punkte ignorieren
if (found == true) {
break;
}
}

// minimum oben
// aufsteigend sortieren nach ypos ...
points.sort(function(a,b) {
var keyA = a.y;
var keyB = b.y;

if (keyA < keyB) return -1;
if (keyA > keyB) return 1;

return 0;
});
found = false;
for(ymin = 0; ymin < 400; ymin++) {
for (len = 0; len < points.length; len++) {
if (points[len].y <= ymin) {
console.log('y-min: --> ' + ymin);
found = true;
break;
}
}
// alle anderen Punkte ignorieren
if (found == true) {
break;
}
}

// maxium rechts
// absteigend sortieren nach xpos ...
points.sort(function(a,b) {
var keyA = a.x;
var keyB = b.x;

if (keyA > keyB) return -1;
if (keyA < keyB) return 1;

return 0;
});
console.log('maximum:');
found = false;
for(xmax = 400; xmax >= 0; xmax--) {
for (len = 0; len < points.length; len++) {
if (points[len].x >= xmax) {
console.log('x-max: --> ' + xmax);
found = true;
break;
}
}
// alle anderen Punkte ignorieren
if (found == true) {
break;
}
}

// maxium unten
// absteigend sortieren nach ypos ...
points.sort(function(a,b) {
var keyA = a.y;
var keyB = b.y;

if (keyA > keyB) return -1;
if (keyA < keyB) return 1;

return 0;
});
found = false;
for(ymax = 400; ymax >= 0; ymax--) {
for (len = 0; len < points.length; len++) {
if (points[len].y >= ymax) {
console.log('y-max: --> ' + ymax);
found = true;
break;
}
}
// alle anderen Punkte ignorieren
if (found == true) {
break;
}
}

// boinding-rect ...
ctx.beginPath();
ctx.rect(
xmin-10,ymin-10,
xmax-xmin+5,ymax-ymin+5);
ctx.stroke();

// Ellipse vom rect ...
let mitte_x = (xmax - xmin) / 2;
let mitte_y = (ymax - ymin) / 2;
let ellipse_radius_w = (xmax - xmin) / Math.sqrt(2);
let ellipse_radius_h = (ymax - ymin) / Math.sqrt(2);

ctx.beginPath();
ctx.ellipse(
xmin+mitte_x-10, ymin+mitte_y-10,
ellipse_radius_w,
ellipse_radius_h, 0, 0, Math.PI * 2, true);
ctx.stroke();
}
addEventListener( 'load', init );
</script>

</body>
</html>

[Ulrich D i e z]

Post by Jens Kallup
Ich habe mal ein sehr einfaches Beispiel für dieses
Problem erarbeitet.

[...]

Post by Jens Kallup
Falls Dir die Technik/Umsetzung beliebt, kannst Du
ja vom Browser den Seitentext (Quellcode) anzeigen
lassen.

[...]

Post by Jens Kallup
http://www.kallup.net/news/canvas/

Hallo Jens,

ich habe mir Dein Programm mal angeschaut.

Ich fand es interessant und konnte mal wieder meine Scipting-
Kenntnisse auffrischen. ;-)

Es werden (durch Mausklick) Punkte gegeben, die alle in der
selben Ebene liegen.

Das Programm soll den kleinsten Kreis zeichnen, auf dessen Line
oder innerhalb dessen Fläche alle diese gegebenen Punkte liegen.

Wenn ich richtig verstanden habe, liegt Deinem Programm die
folgende Idee zugrunde:

- Die Punkte haben kartesische Koordinaten, d.h.,
x-Werte und y-Werte.

- Man bestimme den kleinsten bei all diesen Punkten vorkommenden
x-Wert und nenne ihn MinX.

- Man bestimme den kleinsten bei all diesen Punkten vorkommenden
y-Wert und nenne ihn MinY.

- Man bestimme den größten bei all diesen Punkten vorkommenden
x-Wert und nenne ihn MaxX.

- Man bestimme den größten bei all diesen Punkten vorkommenden
y-Wert und nenne ihn MaxY.

- Die beiden Punkte mit den Koordinaten (MinX, MinY) und
(MaxX, MaxY) bilden die Endpunkte einer Strecke, die einen
Durchmesser des gesuchten Kreises darstellt.

Letzteres stimmt aber leider nur in Sonderfällen.

Nämlich nur dann, wenn mindestens zwei der Punkte (MinX, MinY),
(MinX, MaxY), (MaxX, MinY), (MaxX, MaxY) zu den gegebenen Punkten
gehören.

In Fällen, in denen das nicht so ist, hat der gesuchte Kreis
einen kleineren Durchmesser.

Um das zu veranschaulichen habe ich Dir ein .jpg-Bildchen
gebastelt und unter
<Loading Image...>
verlinkt.

Auf dem Bildchen siehst Du

- links einen Fall, bei dem keiner der Punkte
(MinX, MinY), (MinX, MaxY), (MaxX, MinY), (MaxX, MaxY)
zu den gegebenen Punkten gehört.
- rechts einen Fall, bei dem alle vier der Punkte (MinX, MinY),
(MinX, MaxY), (MaxX, MinY), (MaxX, MaxY) zu den gegebenen
Punkten gehören, was die Bedingung, dass mindestens zwei
dieser Punkte zu den gegebenen Punkten gehören, erfüllt.

Mit freundlichemn Gruß

Ulrich

[Ulrich Diez]

Post by Ulrich D i e z
Letzteres stimmt aber leider nur in Sonderfällen.
Nämlich nur dann, wenn mindestens zwei der Punkte (MinX, MinY),
(MinX, MaxY), (MaxX, MinY), (MaxX, MaxY) zu den gegebenen Punkten
gehören.

Nicht "zwei" sondern "drei":

Nämlich nur dann, wenn mindestens _drei_ der Punkte (MinX, MinY),
(MinX, MaxY), (MaxX, MinY), (MaxX, MaxY) zu den gegebenen Punkten
gehören.

Ulrich

[Ulrich Diez]

- Die beiden Punkte mit den Koordinaten (MinX, MinY) und
(MaxX, MaxY) bilden die Endpunkte einer Strecke, die einen
Durchmesser des gesuchten Kreises darstellt.
Letzteres stimmt aber leider nur in Sonderfällen.
Nämlich nur dann, wenn mindestens zwei der Punkte (MinX, MinY),
(MinX, MaxY), (MaxX, MinY), (MaxX, MaxY) zu den gegebenen Punkten
gehören.

Korrektur:

Nämlich nur dann, wenn
entweder mindestens die Punkte (MinX, MinY) und (MaxX, MaxY)
oder mindestens die Punkte (MinX, MaxY) und (MaxX, MinY)
zu den gegebenen Punkten gehören.

Ulrich

[Jens Kallup]

Hallo Ulrich,

danke für dein Feedback!
Die Anforderung mind. 3 Punkte hab ich vergessen.
Schande über mein Haupt.
Das Problem ist, das nicht immer ein Kreis entsteht;
dann wenn die Punkte keinen Quader, sondern ein
Rechteck beschreiben.
Dafür müsste eine Ellipse gezeichnet werden.
Was nicht aus dem OP von mir nicht heraus gelsen
werden konnte.

Gruß, Jens

[Rainer Rosenthal]

Post by Alfred Flaßhaar
Solution Methodologies for the Smallest Enclosing Circle Problem
Sheng Xu, Robert M. Freund, Jie Sun
Gruß, Alfred

Danke. Schön auch diese historische Referenz darin:
[4] Chrystal, P. (1885), “On the problem to construct the minimum circle
enclosing n given points in a plane”, in: Proceedings of the Edinburgh
Mathematical Society, Third Meeting, p.30.

Ist ja auch ein für Schotten spannendes Thema, sparsame Kreise zu finden.

Lieben Gruß,
Rainer

[Klaus-R. Loeffler]

Post by Rainer Rosenthal

Post by Alfred Flaßhaar
Solution Methodologies for the Smallest Enclosing Circle Problem
Sheng Xu, Robert M. Freund, Jie Sun
Gruß, Alfred

[4] Chrystal, P. (1885), “On the problem to construct the minimum circle
enclosing n given points in a plane”, in: Proceedings of the Edinburgh
Mathematical Society, Third Meeting, p.30.
Ist ja auch ein für Schotten spannendes Thema, sparsame Kreise zu finden.
Lieben Gruß,
Rainer

Mac-Nutzer weise ich auf mein Programm GeometNull hin, mit dem sich geometrische Konstruktionen - darunter auch konvexe Hülle und Hüllkreis - ausführen lassen und zu dem Kritik jeder Art willkommen ist.
Gruß, Klaus-R.

[Alfred Flaßhaar]

Post by Ralf Goertz
Am Thu, 7 Jan 2021 18:39:49 +0100

(...)

Wie bekommt man das hier

http://www.lee-mac.com/mecfunction.html

zum Laufen?
Meine Programmierfähigkeiten enden bei Assembler, Algol, Fortran, PL1.

[Jens Kallup]

Post by Alfred Flaßhaar
Wie bekommt man das hier
http://www.lee-mac.com/mecfunction.html
zum Laufen?
Meine Programmierfähigkeiten enden bei Assembler, Algol, Fortran, PL1.

das ist LISP Programmcode, der an das Produkt "AutoCAD" (ein Designer
Tool für Prototypen) verheiratet ist.

Das wirst Du nicht so zum Laufen bekommen.
Es sei denn Du installierst Dir AutoCAD.

MfG Jens

[Helmut Richter]

Post by Jens Kallup

Post by Alfred Flaßhaar
Wie bekommt man das hier
http://www.lee-mac.com/mecfunction.html
zum Laufen?
Meine Programmierfähigkeiten enden bei Assembler, Algol, Fortran, PL1.

das ist LISP Programmcode, der an das Produkt "AutoCAD" (ein Designer
Tool für Prototypen) verheiratet ist.
Das wirst Du nicht so zum Laufen bekommen.
Es sei denn Du installierst Dir AutoCAD.

Wie ein Algorithmus funktioniert, habe ich ja schon geschrieben. Man kann
danach programmieren, wenn man weiß, wie man den Umkreis eines Dreiecks
berechnet. Ich setz mich jetzt aber nicht hin und mache es.

[Alfred Flaßhaar]

(...)

Post by Helmut Richter

Post by Jens Kallup
das ist LISP Programmcode, der an das Produkt "AutoCAD" (ein Designer
Tool für Prototypen) verheiratet ist.

"AutoCAD" kenne ich seit vielen Jahren als Handwerkszeug von Architekten
und Ingenieuren, habe es aber selber nicht anwenden müssen. Hatte
gehofft, daß es eine stand-alone-Variante für den lisp-Baustein
"Hüllkreis" gibt.
(...)

Post by Helmut Richter
Wie ein Algorithmus funktioniert, habe ich ja schon geschrieben. Man kann
danach programmieren, wenn man weiß, wie man den Umkreis eines Dreiecks
berechnet. Ich setz mich jetzt aber nicht hin und mache es.

Das habe ich auch nicht erwartet oder gar verlangt. Und solche simplen
Rechenaufgaben aus der Geometrie (Dreiecksumkreis) schaffe ich immer
noch allein und zu Fuß.

Aber das Thema "Kreis um Punkte" im Sinne des Satzes von Jung
interessiert mich nun mal sehr u.a. auch aus sentimentalen Gründen.
Insbesondere habe ich mich heute nun gründlich mit den aktuell zum
üblichen Lehrstoff gehörigen Algorithmen zur Ermittlung des Hüllkreises
beschäftigt und habe u. a. nach einem geeigneten Spielzeug dazu gesucht.

С сердечным приветом,

Alfred Flaßhaar

[Christian Gollwitzer]

Post by Alfred Flaßhaar
(...)

Post by Jens Kallup
das ist LISP Programmcode, der an das Produkt "AutoCAD" (ein Designer
Tool für Prototypen) verheiratet ist.

"AutoCAD" kenne ich seit vielen Jahren als Handwerkszeug von Architekten
und Ingenieuren, habe es aber selber nicht anwenden müssen. Hatte
gehofft, daß es eine stand-alone-Variante für den lisp-Baustein
"Hüllkreis" gibt.

Naja, ich hab mal einen Blick auf die Seite geworfen. Jens hat zwar
Recht, dass die Beispielcodes dort für AutoCAD gedacht sind und
offensichtlich dann (wie in der animierten Grafik) mit einer
interaktiven GUI daherkommen. Andererseits scheint der Code, der die
eigentliche Arbeit macht (unter dem Link:
http://www.lee-mac.com/lisp/MinEncCircle.lsp ) damit nichts zu tun zu
haben - also das sollte mit einem gewöhnlichen Common LISP-Interpreter
laufen.

Ich bin jetzt allerdings auch viel zu faul um das zu testen und meine
rudimentären LISP-Kenntnisse rauszukramen.

Heutzutage setzt sich für derartige Berechnungen immer mehr Python
durch, und so ist es auch nicht schwer, Beispiele zu finden:

[1]
https://stackoverflow.com/questions/27673463/smallest-enclosing-circle-in-python-error-in-the-code

verweist auf

[2]
https://www.nayuki.io/res/smallest-enclosing-circle/smallestenclosingcircle.py

In der Frage [1] findest Du auch den Code, mit dem Du das Ganze dann
laufen lässt. Solltest Du gar keinen Bock haben, Python zu installieren,
kannst Du das sogar einfach hier ausprobieren:

https://trypython.jcubic.pl/

Dazu zuerst den Code aus [2] per copy-paste reinkopieren und enter drücken.

Danach kannst Du die Punkte definieren wie in [1] in der ersten Zeile
und mit

make_circle(points)

berechnen lassen.

Christian

[Jens Kallup]

Hallo,

vielleicht suchts Du ShapesDetection:

http://85.10.199.202/news/shapes.zip

nicht verirren lassen von der IP, ist mein
Server, nur irgendwie will der Apache mit
der Domain nicht mehr so recht.

Startdatei liegt im Hauptverzeichnis und ist
in Python abgehandelt.

Naja, hth - hope this helps

Jens

[Christian Gollwitzer]

Am 09.01.21 um 08:23 schrieb Jens Kallup: > vielleicht suchts Du
ShapesDetection

Post by Jens Kallup
http://85.10.199.202/news/shapes.zip

Nein, das hat damit nicht das Geringste zu tun. Ich hatte einen Link auf
Code gepostet, der das Originalproblem löst:

https://www.nayuki.io/res/smallest-enclosing-circle/smallestenclosingcircle.py



Christian

[Rainer Rosenthal]

Post by Alfred Flaßhaar
Aber das Thema "Kreis um Punkte" im Sinne des Satzes von Jung
interessiert mich nun mal sehr u.a. auch aus sentimentalen Gründen.
Insbesondere habe ich mich heute nun gründlich mit den aktuell zum
üblichen Lehrstoff gehörigen Algorithmen zur Ermittlung des Hüllkreises
beschäftigt und habe u. a. nach einem geeigneten Spielzeug dazu gesucht.

Der Link von Carlo XYZ [1] enthält eine historische Notiz, die besagt,
dass die Fragestellung auf 1857 datiert werden kann, als ein gewisser J.
J. Sylvester sich dafür interessierte. Dass unter den drei
Literatur-verweisen auch einer mit algebraischem Titel ist, finde ich
erstaunlich:
"On Poncelet's approximate linear valuation of Surd forms" von 1860.

Herzlich grüßend,
Rainer

[1]
http://www.lix.polytechnique.fr/Labo/Frank.Nielsen/pdf/2009-EnclosingBallMachineLearning-IJCGA.pdf

[Alfred Flaßhaar]

(...)

Post by Rainer Rosenthal
Der Link von Carlo XYZ [1] enthält eine historische Notiz, die besagt,
dass die Fragestellung auf 1857 datiert werden kann, als ein gewisser J.
J. Sylvester sich dafür interessierte. Dass unter den drei
Literatur-verweisen auch einer mit algebraischem Titel ist, finde ich
"On Poncelet's approximate linear valuation of Surd forms" von 1860.

Anscheinend stammte der Hintergrund für diese damaligen Überlegungen aus
der Praxis und war keine geometrische "wissenschaftliche Spielerei". Das
hat sich in den vergangenen Jahrzehnten bestätigt. Den Fakten nach zu
urteilen, die ich bisher zum Thema gefunden habe, reicht die
Problemspanne von "Bewertung Treffergenauigkeit von Sportschützen" bis
"Qualitätskontrolle im Maschinenbau". Letzteres ist interessant, weil
darin die mathematische Wechselwirkung zwischen der Genauigkeit des
abtastenden Meßgerätes mit der Zielgenauigkeit eines Produkts (z. B.
Maßhaltigkeit des Durchmessers einer Antriebswelle) enthalten ist, weil
Meßpunkte dann eine kleine Fläche (Meßfehler) erhalten. Ein
faszinierendes Thema.

BTW:
Gibt es irgendwo Überlegungen, die Punktewolke in der Ebene als Bilder
einer stereographischen Projektion aufzufassen? Das wäre eine
kreisverwandte und winkeltreue Abbildung.

HerzlicheGrüße an den See, Alfred

[Carlo XYZ]

Post by Rainer Rosenthal
Der Link von Carlo XYZ [1] enthält eine historische Notiz, die besagt,
dass die Fragestellung auf 1857 datiert werden kann, als ein gewisser J.
J. Sylvester sich dafür interessierte. Dass unter den drei

Das war allerdings kein kleiner Mathematz, sondern ein großer
Mathematiker mit einer höchst interessanten Vita. Ihm verdanken
wir die Begriffe "Matrix" und "Graph" (im algebraischen Sinn).

Post by Rainer Rosenthal
Literatur-verweisen auch einer mit algebraischem Titel ist, finde ich
"On Poncelet's approximate linear valuation of Surd forms" von 1860.

Wieso erstaunlich? Algebra war damals im Reich, in dem die Sonne
nie unterging, eine blühende Wissenschaft, nicht zuletzt durch
den Genannten vertreten, aber auch z.B. durch de Morgan.

Was ich nicht kannte, war der Begriff "Surd form". Der geht
offenbar aufs Arabische zurück, siehe etwas unten im Text bei

<https://en.wikipedia.org/wiki/Nth_root>

Inhaltlich bedeutet er, dass man in einer Surd form den
Irrationalteil von Ausdrücken in Wurzelform stehen lässt,
so wie im bekannten Lösungsausdruck für quadratische
Gleichungen, siehe Zeile 6 von

<https://de.wikipedia.org/wiki/Quadratische_Gleichung>

[Rainer Rosenthal]

Post by Carlo XYZ

Post by Rainer Rosenthal
Literatur-verweisen auch einer mit algebraischem Titel ist, finde ich
"On Poncelet's approximate linear valuation of Surd forms" von 1860.

Wieso erstaunlich? Algebra war damals im Reich, in dem die Sonne
nie unterging, eine blühende Wissenschaft, nicht zuletzt durch
den Genannten vertreten, aber auch z.B. durch de Morgan.

Ich finde es erstaunlich, weil Graphen für mich erst einmal mit
Geometrie und Zeichnungen zu tun haben. Insofern war diese Referenz
nicht so erstaunlich für mich:
[2] J. J. Sylvester. A question in the geometry of situation. Quarterly
Journal of Pure and Applied Mathematics, 1:79, 1857.

Post by Carlo XYZ
Was ich nicht kannte, war der Begriff "Surd form".

Andere Leute finden halt andere Dinge für erstaunlich.
Zwar war England/Großbritannien ein "Reich, in dem die Sonne nie
unterging", aber dieser Ausdruck wird üblicherweise für das Reich Karls
V. verwendet, und dann allgemein der Habsburger.

Aber danke nochmal für den sehr interessanten Link, der mir auch für
meine aktuellen Ausflüge in die Graphentheorie hilfreiche Referenzen
geliefert hat, als ich dem Ausdruck "minimum piercing set" im Abstract
nachging und z.B. dies hier fand:
"Nerves, minors, and piercing numbers", Andreas F. Holmsen, Minki Kim
and Seung Hun Lee, March 19, 2019
https://www.ams.org/journals/tran/2019-371-12/S0002-9947-2019-07608-0/home.html

Gruß,
RR

[Rainer Rosenthal]

Post by Matthias Frey
Hallo,
ich suche einen Algorithmus. Es soll ein Kreis bestimmt werden, der um
alle gegebenen Punkte geht.
Alle Punkte liegen in einer Ebene. Der Kreis soll kleinstmöglich sein, alle
Punkte sollen auf oder im Kreis liegen.
Habe schon etwas gegoogelt, aber alles was ich finde ist ein Kreis
um die Punkte eines Dreiecks
Der Algorithmus sollte ab drei Punkte funktionieren.
Weiss jemand was oder mit welchen Begriffen man suchen könnte?
Danke.

Hallo Matthias,

das ist ein sehr interessantes Problem, und es gibt fertige Programme
dafür. Ich habe zwar gerade keins parat, aber im Rahmen eines
Al-Zimmermann-Wettbewerbs wurde darüber eifrig diskutiert. Ich war
neugierig und dachte damals, das könne ja nicht so schwierig sein.
*hihihi* ich hab's dann irgendwann gesteckt - hat aber Spaß gemacht.

Passende Stichworte und vielleicht auch fertige Programme findest Du
sicher hier:

https://en.wikipedia.org/wiki/Smallest-circle_problem

(Gibt es nicht auf Deutsch. Den Mangel könntest Du bei der Gelegenheit
gleich beheben :-) )

Gruß,
Rainer

Rainer Rosenthal
***@web.de

[Carlo XYZ]

Post by Rainer Rosenthal
Passende Stichworte und vielleicht auch fertige Programme findest Du
https://en.wikipedia.org/wiki/Smallest-circle_problem

Ja. Du warst 8 Minuten schneller; ich hab zu lange gezögert ..;)

Auf Deutsch gibt's zwar einiges an Material, zum Beispiel:

<https://www.informatik.uni-leipzig.de/~stjaenicke/ag/6-Smallest_Enclosing_Discs.pdf>

.. aber tatsächlich wohl keinen deutschen Wikipedia-Eintrag.

[Andreas Mattheiss]

Hallo,

Post by Rainer Rosenthal
Passende Stichworte und vielleicht auch fertige Programme findest Du
https://en.wikipedia.org/wiki/Smallest-circle_problem

das ist interessant, vor allem, weil der Aufwand im besten Fall nur linear
mit der Punktanzahl steigt.

In Unkenntnis der dort erwähnten Algorithmen hätte ich das mit
brachialer Gewalt versucht; falls es nicht allzu viele Punkte sind
(<100?), ist das akzeptabel. Dazu würde ich einfach alle möglichen
Punktetripel bilden, und durch jedes den Mittelpunk und Radius des durch
sie definierten Kreises finden. Das geht sehr schnell, und dann können
die übrigen n-3 Punkte getestet werden, ob sie im Kreis liegen. Das geht
auch schnell. Das mit den zwei Punkten auf einem Kreis hätte ich wohl am
Anfang übersehen.

Nun ist es so: dieser Lösungsweg wird im Artikel unter "Other Algorithms"
gleich am Anfang als "naive algorithm" bezeichnet (das ist er auch ...),
mit einem Aufwand von O(n**4). Echt? Ich meine: die Anzahl aller Tripel
aus n Punkten ist n*(n-1)*(n-2)/6, mithin ist der Aufwand doch O(n**3)?!?
Das mit den zwei Punkten schlägt mit n*(n-1)/2 zu Buche, ist also
unbedeutend gegen O(n**3). Habe ich da etwas übersehen?

mfg
Andreas

[Ralf Goertz]

Am Sat, 16 Jan 2021 00:56:28 +0100

Post by Andreas Mattheiss
Nun ist es so: dieser Lösungsweg wird im Artikel unter "Other
Algorithms" gleich am Anfang als "naive algorithm" bezeichnet (das ist
er auch ...), mit einem Aufwand von O(n**4). Echt? Ich meine: die
Anzahl aller Tripel aus n Punkten ist n*(n-1)*(n-2)/6, mithin ist der
Aufwand doch O(n**3)?!? Das mit den zwei Punkten schlägt mit n*(n-1)/2
zu Buche, ist also unbedeutend gegen O(n**3). Habe ich da etwas
übersehen?

Na ja, es kommt ja für jedes Tripel noch der Test hinzu, ob die
restlichen n-3 Punkte im Kreis liegen. Das ergibt dann O(n^4).

[Andreas Mattheiss]

Hallo,

Post by Ralf Goertz
Na ja, es kommt ja für jedes Tripel noch der Test hinzu, ob die
restlichen n-3 Punkte im Kreis liegen. Das ergibt dann O(n^4).

natürlich, das hatte ich übersehen. Beim Programmieren wäre es
aufgefallen: die äußere Schleife wird O(n**3), die innere (die mit dem
Test) O(n) mal -> O(n**4).

Danke, mfg
Andreas

[Carlo XYZ]

Post by Matthias Frey
ich suche einen Algorithmus. Es soll ein Kreis bestimmt werden, der um
alle gegebenen Punkte geht.
Alle Punkte liegen in einer Ebene. Der Kreis soll kleinstmöglich sein, alle
Punkte sollen auf oder im Kreis liegen.
Habe schon etwas gegoogelt, aber alles was ich finde ist ein Kreis
um die Punkte eines Dreiecks
Der Algorithmus sollte ab drei Punkte funktionieren.
Weiss jemand was oder mit welchen Begriffen man suchen könnte?
Danke.

<https://en.wikipedia.org/wiki/Smallest-circle_problem>

[Jens Kallup]

Hallo,

- man nehme ein kartesisches Koordinaten-System
- man zeichne einen Punkt: P(0,0)

da die kleinste Ausdehnung eines Punktes 1 Einheiten
beträgt, ist auch die Größe des kleinsten Kreises
bestimmt - nämlich mit den Radius 1.

Man kann auch ein Dreieck konstruieren, das 3 mal 1
Längen-Einheiten besitzt, in dem dann der 1x1 Kreis
liegt.

Ich gehe mal davon aus, das es sich um ein gleichseitiges
Dreieck mit 3 60 Grad Winkel handelt...

diese 3 Seiten-Längen teile ich jeweils um 2 Einheiten,
und erhalte 3x 0,5 Einheiten.
Diese 3 Einheiten verbinde ich zusammen und erhalte einen
Schwerpunkt in der Mitte des Dreiecks.
Das ist die leichte (falsche) Übung.

Hier nun exakter, etwas schwieriger Teil:

3 Längen ausgeklappt (Semilänge):
s = 3 cm / 2 = 1.5

Fläche nach Heron-Formel:

A = sqrt(1.5 * (1.5 - 1) * (1.5 - 1) * (1.5 - 1))
= sqrt(0.19)
= 0,43

Höhe des Dreiecks (Hälfte einer Dreiecks-Länge):
a,b,c = 1

H_a = (a * h_a) / 2
H_b = (b * h_b) / 2
H_c = (c * h_c) / 2

h_a = (2 * H) / a = (2 * 0,43) / 1 = 0,87
h_b = (2 * H) / b = (2 * 0,43) / 1 = 0,87
h_c = (2 * H) / c = (2 * 0,43) / 1 = 0,87

Inkreisradius (kleinste Radius):

A = r * s
r = A / s = 0.43 / 1.5 = 0.29

Somit ist der kleinste Kreis nicht 1, wie gedacht,
sondern nur 0.29 Einheiten.

Gruß, Jens

Post by Matthias Frey
Hallo,
ich suche einen Algorithmus. Es soll ein Kreis bestimmt werden, der um
alle gegebenen Punkte geht.
Alle Punkte liegen in einer Ebene. Der Kreis soll kleinstmöglich sein, alle
Punkte sollen auf oder im Kreis liegen.
Habe schon etwas gegoogelt, aber alles was ich finde ist ein Kreis
um die Punkte eines Dreiecks
Der Algorithmus sollte ab drei Punkte funktionieren.
Weiss jemand was oder mit welchen Begriffen man suchen könnte?
Danke.
Matthias

[Jens Kallup]

Hallo,

- man nehme ein kartesisches Koordinaten-System
- man zeichne einen Punkt: P(0,0)

da die kleinste Ausdehnung eines Punktes 1 Einheiten
beträgt, ist auch die Größe des kleinsten Kreises
bestimmt - nämlich mit den Radius 1.

Man kann auch ein Dreieck konstruieren, das 3 mal 1
Längen-Einheiten besitzt, in dem dann der 1x1 Kreis
liegt.

Ich gehe mal davon aus, das es sich um ein gleichseitiges
Dreieck mit 3 60 Grad Winkel handelt...

diese 3 Seiten-Längen teile ich jeweils um 2 Einheiten,
und erhalte 3x 0,5 Einheiten.
Diese 3 Einheiten verbinde ich zusammen und erhalte einen
Schwerpunkt in der Mitte des Dreiecks.
Das ist die leichte (falsche) Übung.

Hier nun exakter, etwas schwieriger Teil:

3 Längen ausgeklappt (Semilänge):
s = 3 cm / 2 = 1.5

Fläche nach Heron-Formel:

A = sqrt(1.5 * (1.5 - 1) * (1.5 - 1) * (1.5 - 1))
  = sqrt(0.19)
  = 0,43

Höhe des Dreiecks (Hälfte einer Dreiecks-Länge):
a,b,c = 1

H_a = (a * h_a) / 2
H_b = (b * h_b) / 2
H_c = (c * h_c) / 2

h_a = (2 * H) / a  =  (2 * 0,43) / 1 = 0,87
h_b = (2 * H) / b  =  (2 * 0,43) / 1 = 0,87
h_c = (2 * H) / c  =  (2 * 0,43) / 1 = 0,87

Inkreisradius (kleinste Radius):

A = r * s
r = A / s  =  0.43 / 1.5 = 0.29

Diese Rechnung ist für die Ausdehnung von 1 Einheiten.
Man beachte, das der Sender und Empfänger zwar auf der
gleichen Ebene liegen kann, jedoch kommt es dann zu
Überlagerungen bzw. loopback - ein Echo, das immer lauter
und überlagerter wird.

bei 2 Einheiten muss man natürlich die entsprechenden
Daten aufsummieren.

Hier ein kleines PDF, das den größten Kreis bzw. Radius
aufzeigt - habs nicht schöner hinbekommen :-)
ich bitte um Vergebung.

http://www.kallup.net/news/station.pdf

Jens

[Jens Kallup]

das wichtigste ja vergessen - sorry!

1. Alle Stationen werden ermittelt in deren Einheiten
(logischerweise in Meter oder Kilometer)

2. man überträgt diese Daten in einen 2 Dimensionalen
Array bzw. in eine map (mit C++):

std::map< int entfernung , std::string name> Station;

3. evtl. noch sotieren (müsste aber std::map<T,T> selbst machen
(nach entfernung),

4. Abstand berechnen, indem man die std::map durch iteriert und
die Funktion "max" bzw. "min" anwendet, um den größten bzw.
kleinsten Radius zu bestimmen,

5. Werte ausgeben.

hier der Quellcode in C++:


// ---------------------------------------------------
// Datei: sender.cc
// Author: Jens Kallup - <***@web.de>
// (c) 2021 kallup.net - non-profit Software
// Alle Rechte vorbehalten.
//
// Berechnung der Reichweite eines Senders innerhalb
// eines minimalen gleichseitigen Dreiecks mit geg.
// Ausdehnung von 1 Einheiten = 0.29
// ---------------------------------------------------
#include <iostream>
#include <iomanip>
#include <map>
#include <cmath>

using namespace std;

const double PI = 3.141592653589793238463;

// statische! map Vorbelegung ...
const map<int, int> stationen =
{
{ 1, 1 },
{ 50, 2 },
{ 100, 3 },
{ 150, 4 },
{ 200, 5 },
{ 250, 6 },
{ 300, 7 },
{ 350, 8 },
{ 400, 9 },
{ 450, 10 },
};

int main()
{
for (const auto& x: stationen) {
{
double drei_lang_a = 1.00 ; // Dreieck-Seiten-Länge a
double drei_lang_b = 1.00 ; // Dreieck-Seiten-Länge b
double drei_lang_c = 1.00 ; // Dreieck-Seiten-Länge c

double drei_umfang = drei_lang_a + drei_lang_b + drei_lang_c;
double drei_semip = drei_umfang / 2.00;

double drei_heron = sqrt(
( drei_semip *
( drei_semip - drei_lang_a ) *
( drei_semip - drei_lang_b ) *
( drei_semip - drei_lang_c )));

double drei_hoehe_a = (2 * drei_heron) / drei_lang_a;
double drei_hoehe_b = (2 * drei_heron) / drei_lang_b;
double drei_hoehe_c = (2 * drei_heron) / drei_lang_c;

// zur Probe ...
double drei_winkel_a =
( pow(drei_lang_b, 2) +
pow(drei_lang_c, 2) -
pow(drei_lang_a, 2) )/(2 * (drei_lang_b * drei_lang_c));

double drei_winkel_b =
( pow(drei_lang_a, 2) +
pow(drei_lang_c, 2) -
pow(drei_lang_b, 2) )/(2 * (drei_lang_a * drei_lang_c));

// alle Winkel gleich
double drei_winkel_acos = acosf(drei_winkel_a) / (PI / 180);
double drei_winkel_bcos = acosf(drei_winkel_b) / (PI / 180);
double drei_winkel_ccos = acosf(drei_winkel_a) / (PI / 180);

double kreis_radius = drei_heron / drei_semip;

fprintf(stdout,"Station: %5d, Radius: %10.5f\n",
x.second,
x.first * kreis_radius);

} }
return 0;
}


Übersetzt mit: g++ -o sender.exe sender.cc

unter Windows 10 mit MinGW GCC 6.0.8

Hope this helps
Jens

[Jens Kallup]

hmm, wieder was vergessen:
das Result des ausführbaren Programmes sollte
folgende Werte ausgeben:

Station: 1, Radius: 0.28868
Station: 2, Radius:
14.43376
Station: 3, Radius: 28.86751

Station: 4, Radius: 43.30127
Station: 5, Radius:
57.73503
Station: 6, Radius: 72.16878

Station: 7, Radius: 86.60254
Station: 8, Radius:
101.03630
Station: 9, Radius: 115.47005

Station: 10, Radius: 129.90381

so, nu aber ;-)

Jens

[Jens Kallup]

hmm, wieder was vergessen:
das Result des ausführbaren Programmes sollte
folgende Werte ausgeben:

Station: 1, Radius: 0.28868
Station: 2, Radius: 14.43376
Station: 3, Radius: 28.86751
Station: 4, Radius: 43.30127
Station: 5, Radius: 57.73503
Station: 6, Radius: 72.16878
Station: 7, Radius: 86.60254
Station: 8, Radius: 101.03630
Station: 9, Radius: 115.47005
Station: 10, Radius: 129.90381

so, nu aber ;-)

Jens

[Jens Kallup]

// ---------------------------------------------------
// Datei: sender.cc
// Author: Jens Kallup - <***@web.de>
// (c) 2021 kallup.net - non-profit Software
// Alle Rechte vorbehalten.
//
// Berechnung der Reichweite eines Senders innerhalb
// eines minimalen gleichseitigen Dreiecks mit geg.
// Ausdehnung von 1 Einheiten = 0.29
// ---------------------------------------------------
#include <iostream>
#include <iomanip>
#include <map>
#include <cmath>

using namespace std;

const double PI = 3.141592653589793238463;

// statische! map Vorbelegung ...
const map<int, int> stationen =
{
{ 1, 1 },
{ 50, 2 },
{ 100, 3 },
{ 150, 4 },
{ 200, 5 },
{ 250, 6 },
{ 300, 7 },
{ 350, 8 },
{ 400, 9 },
{ 450, 10 },
};

int main()
{
for (const auto& x: stationen) {
{
double drei_lang_a = 1.00 ; // Dreieck-Seiten-Länge a
double drei_lang_b = 1.00 ; // Dreieck-Seiten-Länge b
double drei_lang_c = 1.00 ; // Dreieck-Seiten-Länge c

double drei_umfang = drei_lang_a + drei_lang_b + drei_lang_c;
double drei_semip = drei_umfang / 2.00;

double drei_heron = sqrt(
( drei_semip *
( drei_semip - drei_lang_a ) *
( drei_semip - drei_lang_b ) *
( drei_semip - drei_lang_c )));

double drei_hoehe_a = (2 * drei_heron) / drei_lang_a;
double drei_hoehe_b = (2 * drei_heron) / drei_lang_b;
double drei_hoehe_c = (2 * drei_heron) / drei_lang_c;

// zur Probe ...
double drei_winkel_a =
( pow(drei_lang_b, 2) +
pow(drei_lang_c, 2) -
pow(drei_lang_a, 2) )/(2 * (drei_lang_b * drei_lang_c));

double drei_winkel_b =
( pow(drei_lang_a, 2) +
pow(drei_lang_c, 2) -
pow(drei_lang_b, 2) )/(2 * (drei_lang_a * drei_lang_c));

double drei_winkel_acos = acosf(drei_winkel_a) / (PI / 180);
double drei_winkel_bcos = acosf(drei_winkel_b) / (PI / 180);
double drei_winkel_ccos = acosf(drei_winkel_a) / (PI / 180);

double kreis_radius = drei_heron / drei_semip;

fprintf(stdout,"Station: %5d, Radius: %10.5f -> %4d km "
"Entfernung\n",
x.second,
x.first * kreis_radius,
x.first);
} }
return 0;
}


sollte dann folgendes ausgeben:


Station: 1, Radius: 0.28868 -> 1 km Entfernung
Station: 2, Radius: 14.43376 -> 50 km Entfernung
Station: 3, Radius: 28.86751 -> 100 km Entfernung
Station: 4, Radius: 43.30127 -> 150 km Entfernung
Station: 5, Radius: 57.73503 -> 200 km Entfernung
Station: 6, Radius: 72.16878 -> 250 km Entfernung
Station: 7, Radius: 86.60254 -> 300 km Entfernung
Station: 8, Radius: 101.03630 -> 350 km Entfernung
Station: 9, Radius: 115.47005 -> 400 km Entfernung
Station: 10, Radius: 129.90381 -> 450 km Entfernung

Sodele, hoffe das dies nu richtig formatiert wird...
Jens

[Ulrich Diez]

Post by Matthias Frey
ich suche einen Algorithmus. Es soll ein Kreis bestimmt werden, der um alle
gegebenen Punkte geht.
Alle Punkte liegen in einer Ebene. Der Kreis soll kleinstmöglich sein, alle
Punkte sollen auf oder im Kreis liegen.

Gegeben sei eine Zusammenstellung an n verschiedenen Punkten
{P_1, ... , P_n}; n >= 2 , die allesamt in ein- und derselben
Ebene liegen.

Gesucht ist der Kreis mit kleinstem Radius, für den gilt, dass
kein Punkt der Zusammenstellung außerhalb seiner Kreisfläche
liegt.

Funktioniert folgendes? :


Initialisierung
===============
der "Variablen" "bisher berechnete Kreisgleichung"
und der Laufvariablen "k":

- Setze "bisher berechnete Kreisgleichung" := Gleichung des
kleinsten Kreises, auf dessen Kreislinie die Punkte P_1
und P_2 liegen.
(Gerade zwischen P_1 und P_2, halber Abstand der beiden
Punkte, ...)
- Setze k := 2.
- Gehe zu Schritt 1.


Schritt 1 (Fallunterscheidung):
===============================

Wenn k=n, dann gebe "bisher berechnete Kreisgleichung" als
Ergebnis aus.

Wenn k < n: Setze k:=k+1 und gehe zu Schritt 2.


Schritt 2 (P_k außerhalb des bisher berechneten Kreises?):
==========================================================

Wenn P_k auf der Kreislinie oder innerhalb der Kreisfläche des
durch die "bisher berechnete Kreisgleichung" bestimmten Kreises
liegt, gehe zu Schritt 1, ansonsten gehe zu Schritt 3:


Schritt 3 (Neue Kreisgleichung berechnen):
===========================================

Setze "bisher berechnete Kreisgleichung" := Gleichung desjeni-
gen kleinsten Kreises, auf dem die folgenden beiden Punkte
liegen:

1. Der Punkt P_k.
2. Der von P_k weiter entfernt liegende Schnittpunkt der
folgenden beiden Linien:
a) Die durch "bisher berechnete Kreisgleichung" bestimmte
Kreislinie.
b) Die Winkelhalbierende der beiden durch P_k verlaufenden
am durch die "bisher berechnete Kreisgleichung" bestimmten
Kreis anliegenden Tangenten.

Gehe zu Schritt 1.


Ich habe mir das grade eher spontan überlegt.
Und hoffe, auf Denkfehler aufmerksam gemacht zu werden.


Mit freundlichem Gruß

Ulrich

[Ulrich Diez]

Ich schrieb:

[...]

Post by Ulrich Diez
Setze "bisher berechnete Kreisgleichung" := Gleichung desjeni-
gen kleinsten Kreises, auf dem die folgenden beiden Punkte

[...]

Besser ist vielleicht:

[...]
Setze "bisher berechnete Kreisgleichung" := Gleichung desjeni-
gen kleinsten Kreises, auf dessen Kreislinie die folgenden
beiden Punkte liegen:
[...]

[Ulrich Diez]

Control: cancel <dc100129-4ca4-4c8c-b808-***@googlegroups.com>

[Ulrich D i e z]

Post by Ulrich Diez
===========================================

[...]

Post by Ulrich Diez
2. Der von P_k weiter entfernt liegende Schnittpunkt der
a) Die durch "bisher berechnete Kreisgleichung" bestimmte
Kreislinie.
b) Die Winkelhalbierende der beiden durch P_k verlaufenden
am durch die "bisher berechnete Kreisgleichung" bestimmten
Kreis anliegenden Tangenten.

Örks.

b) Die durch P_k und den Mittelpunkt des durch die
"bisher berechnete Kreisgleichung" bestimmten
Kreises verlaufende Gerade.

Ulrich

[Ulrich Diez]

Control: cancel <69cfc654-de9d-45cf-ad60-***@googlegroups.com>

[GGMarco]

Post by Matthias Frey
Hallo,
ich suche einen Algorithmus. Es soll ein Kreis bestimmt werden, der um alle
gegebenen Punkte geht.
Alle Punkte liegen in einer Ebene. Der Kreis soll kleinstmöglich sein, alle
Punkte sollen auf oder im Kreis liegen.
Habe schon etwas gegoogelt, aber alles was ich finde ist ein Kreis
um die Punkte eines Dreiecks
Der Algorithmus sollte ab drei Punkte funktionieren.
Weiss jemand was oder mit welchen Begriffen man suchen könnte?
Danke.
Matthias

Warum nicht den Algorithmus in zwei Schritte aufteilen: 1. Radius berechnen, dann 2. Mittelpunkt.

zu 1. Definiere Funktion als Summe von Deltafunktionen, die ihre Peaks jeweils an den Punkten den Punktemenge haben. Kreis mit variablem Radius so lange drüberfalten, bis der Radius minimal bei maximalem Faltungsmaximum hat. Z.B. über Intervallschachtelung im Radius. --> Radius
2. Position des Faltungsmaximums = Mittelpunkt des Kreises.

Funktioniert übrigens nicht nur bei Punktmengen, sondern kann man sogar bis auf temperierte Distributionen mit kompaktem Träger verallgemeinern.


Gruss, Marco