Kleinsten Kreis einer Punktmenge bestimmen

C

CodeIt

Aktives Mitglied
Hallo, ich möchte ein Programm schreiben, welches zu einer Punktmenge im 2D-Raum, den kleinsten Kreis berechnet, der diese Punktmenge enthält.
Ich weiß bisher nur von einem ziemlich komplexen Algorithmus, welcher in http://inrg.csie.ntu.edu.tw/algorithm2014/homework/P&S Megiddo-83.pdf auf Seite 10 beschrieben wird, diesen finde ich für den Anfang aber doch ziemlich kompliziert.
Deshalb meine Frage, gibt es in Java Bibliotheken welche solche Methoden zur Verfügung stellen, und dies auch wie im o.g. Algorithmus in O(n) Zeit lösen?
 
JCODA

JCODA

Top Contributor
Sehr interessant!
Ich habe mich damals für das gleiche Problem, also dem "Smallest Enclosing Circle"-Problem, interessiert.
Auf der Wiki-Seite https://en.wikipedia.org/wiki/Smallest-circle_problem wird ein probabilistischer Algorithmus (Welzl's algorithm) vorgestellt.
Der benötigt ebenfalls nur lineare Zeit, ist allerdings rekursiv. Sollte aber denke ich kein Problem sein, oder?
Soweit ich weiß ist er auch nicht kompliziert zu implementieren. Falls du dennoch eine Bib benutzen willst, solltest du unter dem obigen Namen schon etwas finden.
Mich würde interessieren für welche Lösung Du Dich entscheidest und ggf. falls du den Algo selbst implementierst, ihn mal sehen. :)
 
C

CodeIt

Aktives Mitglied
JCODA hat gesagt.:
Sehr interessant!
Ich habe mich damals für das gleiche Problem, also dem "Smallest Enclosing Circle"-Problem, interessiert.
Auf der Wiki-Seite https://en.wikipedia.org/wiki/Smallest-circle_problem wird ein probabilistischer Algorithmus (Welzl's algorithm) vorgestellt.
Der benötigt ebenfalls nur lineare Zeit, ist allerdings rekursiv. Sollte aber denke ich kein Problem sein, oder?
Soweit ich weiß ist er auch nicht kompliziert zu implementieren. Falls du dennoch eine Bib benutzen willst, solltest du unter dem obigen Namen schon etwas finden.
Mich würde interessieren für welche Lösung Du Dich entscheidest und ggf. falls du den Algo selbst implementierst, ihn mal sehen. :)
Zum Vergrößern anklicken....

Danke. Der implementierte Algorithmus soll in ein anderes Programm eingebaut werden und dort lediglich eine Funktion erfüllen. Ich programmiere nicht soviel in Java, deshalb wollte ich erstmal ein paar Versuche mit einer möglichst bereits implementierte Variante machen. Der Algo von Welzl sieht einfacher aus als der von Megiddo. Kann aber sein, dass ich den Algo von Megiddo verwenden muss, falls es das Lehrgebiet verlangt. Habe gesehen das Du Nachhilfe anbietest, vielleicht kann ich ja auch Dich zurückkommen?
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
G Größten und kleinsten Wert im Array ermitteln? Java Basics - Anfänger-Themen 7
B zeichen eines String mit der kleinsten Frequenz zurückgeben Java Basics - Anfänger-Themen 25
M Kleinsten Index in Array finden Java Basics - Anfänger-Themen 6
D Ermitteln des kleinsten Messwertes von jedem Tag Java Basics - Anfänger-Themen 15
P Rueckgabe des kleinsten Wertes Java Basics - Anfänger-Themen 9
B Hilfe! Kleinsten Wert aus Array finden? Java Basics - Anfänger-Themen 3
G BST Suchbäume kleinsten Wert suchen Java Basics - Anfänger-Themen 3
G Größten u. kleinsten Wert ermitteln Java Basics - Anfänger-Themen 14
M den kleinsten und größten Wert aus einer Datei finden! Java Basics - Anfänger-Themen 4
YAZZ BlueJ Bewegung einer Figur im Kreis Java Basics - Anfänger-Themen 4
J Kreis soll die gleiche Fläche wie das Rechteck haben wie mache ich das? Java Basics - Anfänger-Themen 3
N Kreismuster auf Bestehendem Kreis erstellen Java Basics - Anfänger-Themen 10
E Kreis soll eine Raupe darstellen Java Basics - Anfänger-Themen 37
CptK Interface Kleine Kreise in großem Kreis anordnen Java Basics - Anfänger-Themen 3
Y Kreis auf einer Kreisbahn bewegen Java Basics - Anfänger-Themen 5
P Erste Schritte Kreis animieren Java Basics - Anfänger-Themen 2
A Kreisumfang/-Fläche vom Kreis berechnen Java Basics - Anfänger-Themen 39
H Kreis verschieben Java Basics - Anfänger-Themen 10
Z Object Kreis am Frame abprallen lassen! Java Basics - Anfänger-Themen 12
X Kreis/Linie Programmieren Java Basics - Anfänger-Themen 1
D Algorithmus für Punkte auf einem Kreis Java Basics - Anfänger-Themen 0
L Dreieck Kreis Java Basics - Anfänger-Themen 12
A Kreis,Radius Programm Java Basics - Anfänger-Themen 3
N Per Button Kreis zeichnen Java Basics - Anfänger-Themen 8
C Kreis nach Mausklick zeichnen Java Basics - Anfänger-Themen 5
A wie Kreis mit Schleife versetzten? Java Basics - Anfänger-Themen 25
O Punkte auf einem Kreis "wandern" lassen Java Basics - Anfänger-Themen 3
U Kreis um Textfelder zeichnen Java Basics - Anfänger-Themen 4
D Kreis mit Pfeiltaste bewegen Java Basics - Anfänger-Themen 3
K Bild auf Kreis packen Java Basics - Anfänger-Themen 2
E Kreis erstellen Java Basics - Anfänger-Themen 10
B Einen Kreis erzeugen Java Basics - Anfänger-Themen 3
S Erzeuge einen Kreis Java Basics - Anfänger-Themen 16
B Kreis,Punkt,Zylinder Java Basics - Anfänger-Themen 6
D Punktberechnung im Kreis Java Basics - Anfänger-Themen 15
TheKing Bild nur in Kreis sichtbar machen Java Basics - Anfänger-Themen 6
K Kreis mit neuer Position zeichnen Java Basics - Anfänger-Themen 3
M Umfang von Rechteck oder Kreis anhand der Parameter Java Basics - Anfänger-Themen 2
L Klickbarer Bereich in einem Kreis Java Basics - Anfänger-Themen 13
D kreis gelb gefüllt aber schwarzer rand. Java Basics - Anfänger-Themen 2
K Kreis Zeichnen ? Code Richtig aber keine Zeichung Java Basics - Anfänger-Themen 8
L Kreis der sich bewegt Java Basics - Anfänger-Themen 11
G Kreis auf JComponent zeichnen Java Basics - Anfänger-Themen 8
0 Klasse Kreis Java Basics - Anfänger-Themen 4
P Java-Applet, Kreis zeichnen Java Basics - Anfänger-Themen 4
E Kreis in Frame ,den man mit der Maus versetzen kann? Java Basics - Anfänger-Themen 2
7 Kreis zeichnen Java Basics - Anfänger-Themen 4
J Kreis herumfliegen & abprallen von Rändern Java Basics - Anfänger-Themen 7
G contains - Punkt in Kreis enthalten? Java Basics - Anfänger-Themen 6
A Kreis mit gedrückter Maustaste bewegen. Java Basics - Anfänger-Themen 2
S Thread - Kugel im Kreis hin-und herflitzen lassen Java Basics - Anfänger-Themen 3
M Ausgabe einer ArrayList ensteht nur als Hashcode, nicht als Objekt Java Basics - Anfänger-Themen 16
D 2 ArrayListen gleich sortieren bzw. eine Liste anhand einer anderen Sortieren Java Basics - Anfänger-Themen 6
ixChronos Letzten 4 Ziffern einer großen Zahl ausgeben Java Basics - Anfänger-Themen 3
P Objekt einer Methode eines anderen Objektes übergeben Java Basics - Anfänger-Themen 5
L Variablenwerte aus einer Methode übergeben Java Basics - Anfänger-Themen 2
E Arrays in einer ArrayList miteinander vergleichen Java Basics - Anfänger-Themen 12
Simon16 Java ArrayListe von einer Klasse sortieren Java Basics - Anfänger-Themen 2
Shadowrunner Variablen Gibt es eine Möglichkeit die Ziffern/Stellen einer Zahl fest zu legen? Java Basics - Anfänger-Themen 3
D remove Object von einer Liste von Obejcts Java Basics - Anfänger-Themen 3
FunkyPhil94 Wert in einer Lambda Funktion erhöhen Java Basics - Anfänger-Themen 3
T Aufruf der Methode einer Oberklasse, wenn sie in der Unterklasse überschrieben ist. Polymorphie. Java Basics - Anfänger-Themen 2
B Kommunikation mit Seriellen Schnittstellen + Integration einer lib Java Basics - Anfänger-Themen 1
A Daten aus einer HashMap aus einer DB speichern und mit neuen Werten vergleichen Java Basics - Anfänger-Themen 8
P Welches SDK für das erstellen einer ausführbaren Datei? Java Basics - Anfänger-Themen 4
D Länge einer Liste aufrufen. Java Basics - Anfänger-Themen 19
J Klassen Instanzen einer Klasse in einer anderen unabhängigen Klasse nutzen Java Basics - Anfänger-Themen 4
B Alle Strings bis zu einer Maimallänge aufzählen, die Bedingung erfüllen Java Basics - Anfänger-Themen 13
marcelnedza Finde meinen Fehler in einer Methode nicht, Java Karol Java Basics - Anfänger-Themen 15
Soranix Erste Schritte Struktur als Anfänger // Von einer Klasse auf ein Objekt einer anderen Klasse zugreifen. Java Basics - Anfänger-Themen 6
MoxMorris Wie macht man String[] = String[] aus einer anderer Methode? Java Basics - Anfänger-Themen 18
T Fibonacci mit einer Hilfsmethode berechnen Java Basics - Anfänger-Themen 10
S Hilfe zu einer Aufgabe Java Basics - Anfänger-Themen 5
M Radius von einer ellipse bestimmen Java Basics - Anfänger-Themen 7
Say Fehlenden Code finden in einer while-Schleife? Java Basics - Anfänger-Themen 11
M Zufallszahl generieren mit einer linken und rechten Grenze Java Basics - Anfänger-Themen 3
N Was Passiert mit dem Namen einer Variable, wenn man diese einer Liste Hinzufügt Java Basics - Anfänger-Themen 16
_user_q Wie eine Methode/Funktion aus einer Klasse mit Constructor aufrufen? Java Basics - Anfänger-Themen 20
W String einer Textdatei in einzelne Stringobjekte pro Zeile aufteilen Java Basics - Anfänger-Themen 14
W Objekte einer ArrayList in txt-datei schreiben mit Paths? Java Basics - Anfänger-Themen 2
S Best Practice Fragen zu Projektstruktur einer Datenbank-Abfrage-App (MVC) Java Basics - Anfänger-Themen 13
T Variable von Objekten in einer Methode überprüfen Java Basics - Anfänger-Themen 26
nelsonmandela Problem bei Ausgabe einer Switch - Case Funktion Java Basics - Anfänger-Themen 5
S Textausgabe in einer For-Schleife Java Basics - Anfänger-Themen 12
M Spezifischen Wert einer Zeile aus .txt Datei entnehmen Java Basics - Anfänger-Themen 15
B Popups mit Klicksabfangen zumAusfüllen einer .ods Datei Java Basics - Anfänger-Themen 0
M RandomAccessFile int und String gleichzeitig in einer Datei Java Basics - Anfänger-Themen 49
E Suchfunktion in einer Liste Java Basics - Anfänger-Themen 39
T ungeordnete Werte-Paare in einer Liste Java Basics - Anfänger-Themen 7
FireHorses Einen Command erst nach einer Chateingabe aktivieren Java Basics - Anfänger-Themen 1
frager2345 Singleton-Muster Java ->Nur eine Instanz einer Klasse erzeugen können Java Basics - Anfänger-Themen 45
F wie kann ich die Position des letzten Vokals innerhalb einer Zeichenkette ermitteln? Java Basics - Anfänger-Themen 5
H Kapselung protected aber in einer Kindklasse nicht zugänglich Java Basics - Anfänger-Themen 5
R Methoden Werte einer ArrayList als Parameter übergeben. Java Basics - Anfänger-Themen 4
B Den Dateipfad einer Java Datei durch Code in Selbiger finden? Java Basics - Anfänger-Themen 10
LilliCherry Array in einer Zeile ausgeben Java Basics - Anfänger-Themen 6
B Attribute eines Objekts einer Klasse durch statische Methode einer 2. Klasse ändern? Java Basics - Anfänger-Themen 32
L Dauerhaftes Speichern einer Eingabe bei einer ArrayList Java Basics - Anfänger-Themen 26
V Hilfe bei Implementierung einer boolean Methode Java Basics - Anfänger-Themen 6
G Position einer unbekannten 3-stelligen-Zahl in einem String finden Java Basics - Anfänger-Themen 15

Ähnliche Java Themen

Aktuelle Jobs

Neue Themen


Oben