Algorithmus zur Abdeckung der maximalen Anzahl der Punkte mit einem Kreis von gegebenem radius

Stellen wir uns vor, wir haben ein Flugzeug mit einige Punkte auf.
Wir haben auch einen Kreis von gegebenem radius.

Brauche ich einen Algorithmus, der bestimmt, wie die position des Kreises, es deckt die maximal mögliche Anzahl von Punkten. Natürlich gibt es viele solcher Positionen, so sollte der Algorithmus Rückkehr einer von Ihnen.

Genauigkeit ist nicht wichtig, und der Algorithmus kann kleine Fehler.

Hier ist ein Beispiel Bild:

Algorithmus zur Abdeckung der maximalen Anzahl der Punkte mit einem Kreis von gegebenem radius

Eingang:

  int n (n<=50) – Anzahl der Punkte;

  float x[n] und float y[n] – arrays mit Punkten' in der X-und Y-Koordinaten;

  float r – radius des Kreises.

Ausgabe:

float cx und float cy – Koordinaten der Mitte des Kreises

Blitz Geschwindigkeit des Algorithmus ist nicht erforderlich, aber es sollte nicht zu langsam sein (weil ich weiß, dass ein paar langsame Lösungen für diese situation).

C++ - code ist bevorzugt, aber nicht obligatorisch.

Sie haben keine Einschränkungen bei der Verteilung der Punkte?
Das klingt wie ein großer codegolf
Ich weiß wirklich nicht so denken. Ziemlich langweilig, keine genaue Bedingungen zum Gewinn... Aber fühlen Sie sich frei, um eine solche Frage.

InformationsquelleAutor Oleh Prypin | 2010-07-12

algorithm c++geometry points

19

Bearbeitet werden, um eine bessere Formulierung, wie vorgeschlagen :

Grundlegenden Beobachtungen :
- Ich nehme an, der radius ist, da es nicht irgendetwas zu ändern.
- gegeben zwei beliebige Punkte, gibt es bei den meisten zwei-Einheit Kreise, auf denen Sie liegen.
- gegeben, eine Lösung Kreis zu Ihrem problem, Sie können es verschieben, bis es enthält zwei Punkte von Ihren Satz, während die gleiche Anzahl an Punkten von deinem set drin.
Des Algorithmus ist dann:
- Für jedes paar von Punkten, wenn Ihr Abstand ist < 2, Berechnung der zwei-Einheit Kreise C1 und C2, die durch Sie hindurchgehen.
- Berechnen Sie die Anzahl der Punkte von Ihr ein Satz in C1 und C2
- Nehmen die max.
- Ich mag diese Lösung. Kann es sein, den ich brauche... Aber ich bin mir nicht sicher, ob es immer richtig
- Können Sie erklären, die Gründe, die Alex?
- Es ist O(n^3) die Anzahl der Punkte. Sie können überprüfen, ob C im Innern des Kreises vom radius 1 die übergabe durch A und B (mit einer vorgeschriebenen Orientierung) durch berechnen einer Determinante, denke ich. Aber bitte hüten Sie sich vor roundoff Fehler, können Sie wirklich verwöhnen diese Art von algorithmen.
- Ich habe nicht bemerkt, Ihre Antwort :(, schrieb ganz das gleiche mit wenig Erklärungen.
- Sie können bewegen Sie die Festplatte ein wenig, bis es berührt zwei Punkte ohne änderung der Anzahl der Punkte im inneren.
- +1 Es ist offensichtlich wahre Lösung. O(n^3) ist nicht gut, aber es ist mathematisch wahre Lösung.
- es ist nicht wirklich n^3, da eine Menge von Paaren verworfen werden, solange Ihr Abstand ist > 2, so ist es eher O(n^2) im Durchschnitt.
- Akzeptiert. Gründe: Diese Lösung scheint richtig zu sein. Die anderen, die schwierig sind, oder ich einfach nicht verstehen
- Ich wirklich nicht bekommen, es. Was bedeutet das sogar bedeuten? Take two points, you have (at most) two unit circles that pass through it? Was it? Warum sind Sie Kommissionierung Einheit Kreise? Dies sollte wirklich besser erklärt.
- ok, ich umformulieren meinen schnell eine schriftliche Antwort.
- given a solution circle to your problem, you can move it until it contains two points of your set while keeping the same number of points of your set inside it. - Ich glaube nicht, dass dies wahr ist. Sowieso, ignoriert, dass, betrachten ein Dreieck, das (kaum) passt in einen Kreis mit radius r. Der Abstand zwischen je zwei Punkten des Dreiecks ist > 2. Betrachten wir zwei Punkte sehr, sehr weit Weg von dem Dreieck mit den gegenseitigen Abstand < 2. Ich denke, dein Algorithmus würde nur die 2 Punkte als Lösung. Ihr Algorithmus ist falsch, meiner Meinung nach, es gar nicht verwenden r überall.
- IVlad: Für jede zwei Punkte, die < 2r abgesehen, gibt es zwei Kreise mit dem radius r, die passieren könnte, durch diese beiden Punkte. (Wenn zwei Punkte sind genau 2r abgesehen, es gibt nur einen Kreis.) Mit Bezug auf die beiden Punkte, diese Kreise sind "optimal": Da die Punkte auf der Grenze des Kreises, der Kreis umfasst eine maximale zusätzlicher Raum (und ggf. weitere Punkte). Iteration über alle Punkt paar gibt Sie alle möglichen Kreise mit >= 2 Punkte in Ihnen. Überprüfen Sie diese Kreise für die Anzahl der Punkte, die Sie enthalten, und wählen Sie einen Kreis mit der höchsten Nummer.
- und wenn es keine Punkte mit gegenseitigem Abstand < 2?
- IVlad: Angenommen, Sie meinte <= 2, dann ist jeder Punkt eines Kreises von radius r um ihn herum, die nur enthält diesen Punkt.
- IVlad: "ich glaube nicht, dass dies wahr ist." - es ist. Bewegen Sie den Kreis in eine beliebige Richtung, bis der erste Punkt ist auf seiner Linie. Dann sind Sie im "swing" der Kreis um diesen Punkt, bis der zweite Punkt ist auf seiner Linie. Sie haben nun einen Kreis berührt zwei Punkte, ohne Niederlage keine Punkte. (Ziemlich offensichtlich, denke ich. Es sei denn, der Kreis nicht enthalten, 2+ Punkte, um mit zu beginnen.)
- einen richtigen Nachweis würde bedeuten, Topologie und die "Maut-passing-lemma". Das argument beruht auf der Tatsache, dass die Funktion "Mittelpunkt von Kreis -> Anzahl der Punkte" ist integer-Wert.
- Ich denke, meine Verwirrung rührt von der Tatsache, dass Sie verwendet werden 2 deine Antwort. Sollte es nicht 2*r?
- Umm.. eigentlich war es die einzige Antwort, die ich voll verstanden.
- Aber gibt es da nicht tatsächlich einige Punkte, die außerhalb der "Einheit" Kreis, der bedeckt wird von einem großen Kreis?
- doc: Die Radien aller Kreise in der Lösung identisch ist (r). @ IVlad: ja, die "2" in der Antwort sollte das Lesen "2r".
- naja, +1 ist, dann. Ich glaube wirklich, dass sollte gemacht werden klarer, Sie hatte wirklich mich meinen Kopf kratzen, als ich sah, keine Erwähnung von r überall.
- OK dann. Es sollte nicht aufgerufen werden, eine Einheit, Kreis, sondern ein Kreis mit dem radius r. Es ist eine gute Lösung, aber es ist geschrieben in der schrecklichen Art und Weise. "Sie können es verschieben, bis es enthält zwei Punkte von Ihren Satz, während die gleiche Anzahl an Punkten von deinem set drin." - bis finden Sie zwei Punkte auf seinem Rand, während die gleiche Anzahl von Punkten drin ;/
- bearbeitet, bin ich davon ausgegangen, r = 1, ohne es zu sagen.
- Dies würde eine große LINQ-Projekts.
- Dies könnte reduziert werden, die aus O(n^3) auf O(n^2 * mlogn) (m ist die Durchschnittliche Anzahl der Punkte in jedem Kreis getestet). Wenn man alle Punkte in einem quad-tree und verwenden Sie, dass bei der Prüfung jeder Kreis, um tally die anderen Punkte, die es enthält. Die big-O Mathe bekommen würde chaotisch, aber es könnte noch weiter reduziert werden durch Verwendung der quad-tree zu identifizieren, die Kandidaten-Paare von Punkten, die nahe genug, um Wert getestet zu werden.
- Es ist schon weniger als O(n^3), da im Durchschnitt nur O(n) Paare von Punkten sind innerhalb 2r (unter der Annahme gleichmäßige Verteilung). So erhalten Sie tatsächlich etwas, das O(n^2)-ish.
- Ich Frage mich, was passiert, wenn Sie eine floating-point-Ungenauigkeiten berücksichtigt werden.
- guter Punkt. Der test, ob ein Punkt liegt innerhalb eines gegebenen Kreises ist in der Tat ein harter Brocken numerisch. Sie können die Verwendung beliebiger Genauigkeit arithmetische, für diese.
InformationsquelleAutor Alexandre C.
6

Dies ist die "disk teilverkleidungen problem" in die Literatur-das sollte Ihnen ein guter Ort, um zu starten googeln. Hier ist ein Papier abdecken eine mögliche Lösung, aber es ist ein wenig intensiver mathematisch: http://www.utdallas.edu/~edsha/papers/bin/ISPAN04_cover.pdf

Als eine Angelegenheit von Tatsache, diese fällt in den Bereich der "computational geometry", das ist faszinierend, aber kann hart sein, um einen Brückenkopf in. Gibt es eine gute übersicht von deBerg auf verschiedenen algorithmen, im Zusammenhang mit dem Thema.
- Ich glaube nicht, dass der Algorithmus, der verwendet werden kann, in dieser situation, denn ich habe nur ein Kreis
- In Ihrem Fall, das Papier ist "k" ist 1.
InformationsquelleAutor Joel
5

Wenn Sie etwas einfaches möchten, nehmen Sie zufällige position (x,y), berechnen Sie die Anzahl der Punkte im Kreis und vergleichen mit vorherigen position. Nehmen Sie die maximale. Wiederholen Sie den Vorgang jedes mal, die Sie wollen.

Warum zum Teufel downvote? Jemals gehört, über Monte-Carlo-Methoden? Eigentlich für eine riesige Menge von Punkten, deterministischen Algorithmus kann nicht Ziel in angemessener Zeit.
- Nicht die downvoter, aber OP: "brauche ich einen Algorithmus, der bestimmt...."
- ist nicht wichtig und Algorithmus machen kann, kleine Fehler"
- Angemessene Zeit, auch ausgedrückt in einer Beziehung mit der Anzahl der Punkte gegeben. Zum Beispiel, O(n^3) bedeutet, dass der Algorithmus endet in der Zeit, die proportional zu der Dritten Potenz der Anzahl der Punkte. Oft "angemessene" Zeit für ein Algorithmus ist: Polynom (n^3, n^8 n^k): OK, linearen (n, 3n, (1/9)n, kn, alle sind n): große, logarithmisch: genial.
- Fair genug, und ich denke, Ihr Punkt ist gültig, so dass ich nicht downvote. Cheers.
- Für meine situation, diese Lösung ist nicht zu schlecht
- Eine gute Monte-Carlo-Algorithmus können gebunden die Fehler-Wahrscheinlichkeit als Funktion der parameter (z.B. Anzahl der Iterationen, die in Ihrem Fall). Ich sehe keine solche Analyse in Ihre Lösung.
- Ich gab nur eine Allgemeine Idee. Es ist einfach zur Verbesserung des Algorithmus auszuwerten, um MC-Ansatz mit den bisherigen Antworten. Zum Beispiel für die Kreise, die ich wählen würde, Positionen, die nicht völlig zufällig, sondern diejenigen, für die es-Häufigkeit zwischen Kreis-Rand und zwei Punkte. Wenn Sie zusätzlich eine Möglichkeit bieten, zu nutzen paar mal (zum Beispiel an Sie erinnern), dann kann man schätzen, dass die Wahrscheinlichkeit für Fehler verringert sich asymptotisch auf null für die Anzahl der Iterationen gleich der Anzahl aller Paare, die auf der Ebene, für die Kreis konstruiert werden kann.
InformationsquelleAutor doc
2

Das problem kehrt zurück zu finden, die globalen optimale Funktion f :R x R -> N. Der Eingang für f ist der Mittelpunkt des Kreises, und der Wert, natürlich, ist die Anzahl der enthaltenen Punkte aus dem set. Der graph der Funktion wird unterbrochen, staircase-like.

Könnten Sie beginnen und testen Sie die Funktion in jedem Punkt entspricht einem Punkt in der Menge, um die Punkte durch eine Verringerung der Werte von f, dann verstärken suchen, um diese Punkte (zum Beispiel bewegen sich entlang einer Spirale).

Weitere option ist zu prüfen alle Schnittpunkte der Segmente verbinden alle Paare von Punkten im set. Ihre optimale Punkt an einer dieser Kreuzungen, die ich denke, aber Ihre Zahl ist wahrscheinlich zu groß, zu berücksichtigen.

Können Sie auch hybridisieren die Optionen 1 und 2, und betrachten die Schnittpunkte der Segmente generiert aus Punkten, um 'gute Punkte'.

Jedenfalls, es sei denn, die Anzahl der gesetzten Punkte ist gering (so dass Sie überprüfen alle Kreuzungen), ich weiß nicht denke können Sie garantieren ein optimum zu finden (eine gute Lösung).
- Ich kann sehen, dass die gleiche Antwort gepostet wird insgesamt drei mal - vermutlich versehentlich. Können Sie löschen die zwei Instanzen?
- Getan. ALSO technische Probleme 🙂
- Die Anzahl der Punkte gering ist (ich habe gerade bearbeitete Frage). Aber ich verstehe nicht, ein paar Dinge, wie... wie können Sie ein Diagramm der 2-parameter-Funktion?
- Minimierung von diskret-wertige Funktionen ist sehr hart.
- Nun, Sie müssen nicht zeichnen Sie die Kurve, ich war gerade Malte es in meinem Kopf... wie diese sowieso: soft.proindependent.com/doc/manual-en/pics/...
- In diesem Fall ist aber die Menge der Punkte zu berücksichtigen, ist endlich.
- Die Menge der Punkte ist immer endlich, weil Computer nicht umgehen können unendliche Mengen. Dennoch ist es eine nicht-lineare diskrete Optimierung problem, das ist die härteste Klasse der Optimierungsprobleme. Es gibt keine bekannten gute generische algorithmen für diese Klasse von Problemen ist, im Gegensatz zu linearen oder kontinuierlichen Optimierungsproblemen.
- Naja, ich denke, wirklich nur die lineare (nicht-ganzzahlige) sind lenkbar im Allgemeinen Fall. Aber wir schweifen vom Thema ab 🙂
InformationsquelleAutor Mau
1

Auf den ersten Blick würde ich sagen, eine quad-tree-Lösung.

Auch, es ist ein Informations-Visualisierung/Data-mining-Methode aufgerufen, K-Mittel, die macht, Cluster von bestimmten Daten. Es kann verwendet werden, mit zusätzlicher Funktionalität in das Ende passen Ihren Zweck.

Der grundlegende Algorithmus für K-Means ist:
1. Ort K Punkte in den Raum, dargestellt durch die Elemente
  das sind geclustert - Diese Punkte repräsentieren die erste Gruppe centroide
2. Zuweisen jedes Datenelement, das die Gruppe, die am nächsten
  Schwerpunkt
3. Wenn alle Elemente zugeordnet wurden, eine Neuberechnung der
  Positionen der K centroide durch Berechnung der mittleren position des dots
4. Wiederholen Sie die Schritte 2 und 3, bis sich die centroide nicht mehr bewegen, oder bewegen sich sehr wenig
Die zusätzliche Funktionalität wäre dann:
1. Berechnung der Anzahl der Punkte, die innerhalb Ihres Kreises positioniert, an der K centroide
2. Wählen Sie die eins, die Ihnen am meisten ZUSAGT 😉
Quellen:

K-means-Algorithmus - Linköping University

Quadtree - en.wikipedia.org/wiki/Quadtree

Eine schnelle Suche auf wikipedia und finden Sie die Quelle code: en.wikipedia.org/wiki/K-means_clustering

InformationsquelleAutor user389609
1

Hier sind zwei Ideen: eine O(n) - approximation algorithm und einen O(n^2 log n) exakt (nicht ungefähr) Algorithmus:

Schnelle Annäherung

Verwenden locality-sensitive-hashing. Im Grunde, hash-jeder Punkt zu einem hash-bucket enthält Punkte in der Nähe. Die Eimer sind so aufgebaut, dass Kollisionen nur geschehen zwischen nahen Punkte - im Gegensatz zu den ähnlich benannten hash-Tabellen-Kollisionen sind hier nützlich. Halten Sie eine laufende Zählung der Anzahl der Kollisionen in einen Eimer, und verwenden Sie dann die Mitte der Eimer, als die Mitte Ihres Kreises.

Ich zugeben, dass dies eine schnelle Erklärung für ein Konzept, das ist nicht super-offensichtlich, wenn Sie das erste mal hören. Eine Analogie wäre zu Fragen, eine Reihe von Menschen, welche Ihre Postleitzahl, und die meisten zip-code zum bestimmen der bevölkerungsreichste Kreis. Es ist nicht perfekt, aber eine gute schnelle Heuristik.

Es ist im Grunde die lineare Zeit in der Anzahl der Punkte, und Sie können Ihre Daten aktualisieren, legen Sie "on the fly" inkrementell neue Antworten in konstanter Zeit pro Punkt (Konstante mit Bezug auf n = Anzahl der Punkte).

Mehr über locality-sensitive-hashes im Allgemeinen oder über meine persönlichen Lieblings-version, die funktionieren würde, in diesem Fall.

Besser als brute-force-deterministischen Ansatz

Ist die Idee: für jeden Punkt, platzieren Sie den Rand des Kreises auf, dass Punkt, und fegen Sie den Kreis, um zu sehen, in welche Richtung enthält die meisten Punkte. Tun Sie dies für alle Punkte, und wir finden die globalen max.

Den Schwung um einen Punkt p kann man in n log n Zeit durch: (a) die Suche nach der Winkel-Intervall je einem anderen Punkt q, so dass, wenn wir den Kreis in Winkel theta, dann enthält q; und (b) Sortieren Sie die Intervalle so, dass wir März/kehren um p in linearer Zeit.

So dauert es O(n log n) Zeit zu finden, die am besten Kreis berühren einen festen Punkt p, und dann multiplizieren, dass durch O(n), um die Kontrollkästchen für alle Punkte. Die Gesamtzeit ist O(n^2 log n).

InformationsquelleAutor Tyler
0

Wenn es wahr ist, dass die Präzision nicht wichtig ist und Algorithmus machen kann, kleine Fehler, dann denke ich, die folgenden.

Lassen f(x,y) ist eine Funktion, die hat ein maximum an der Stelle (0,0) und ist nur signifikant auf die inneren Punkte des Kreises mit radius R. Zum Beispiel f(x,y) = e^{(x^2 + y^2)/(2 * R^2)}.

Lassen (x_i,y_i) Punkte und E_i(x,y) = f(x - x_i, y - y_i).

Ihr problem zu finden, die maximal \sum_i E_i(x,y) .

Können Sie eine Gradienten-Abstieg starten Sie es von jedem Punkt.
- Ich bin 15 Jahre alten Kind. Ich Liebe Programmieren und ich weiß nicht wie Mathematik. So habe ich oft nicht verstehen, diese smart math Dinge 🙂
- Sie können viel erreichen, indem Sie Programmieren, wenn Sie nicht wissen, Mathematik, eine Menge. Aber um effektiv zu lösen--und verstehen, Lösungen von--Aufgaben wie die, die Sie veröffentlicht, sollten Sie besser in Mathe zu werden. (Übrigens, Alexey ist auch mit Hilfe von LaTeX-notation von mathematischen Funktionen, die es nicht mit Mathematik, sondern eines dieser Dinge, die Sie besser lernen)
- es wäre absolut korrekt, wenn f war 1 inside the circle, and 0 outside. 🙂
- gradient descent funktioniert nicht korrekt für den Fall Ihrer nondifferentiable Funktion.
- genau, aber sonst riskieren Sie, um einen Punkt zu finden, dass ist keine Lösung. In der Tat, ich bin mir sicher (obwohl ich nicht versuchen zu beweisen), dass für jede stetige Funktion, es ist möglich, konstruieren Sie eine Eingabe, für die der Algorithmus nicht als schlecht, wie wir wollen.
- Ich bin sicher, auch. Ich begann meine Antwort mit If it is true that precision is not important....
- ok, vielleicht habe ich es nicht. Sorry für irrelevante Kommentare.
InformationsquelleAutor Alexey Malistov
0

Könnte ich schlage vor, eine Dichte Karte? Finden Sie die min-und max-Grenzen für die x und y. Teilen Sie den Bereich der x-und y-Grenzen in bins mit Breite gleich dem Durchmesser deines Kreises. Die Anzahl der Punkte in jeder Klasse für die x-und y separat. Nun finden Sie die Kreuzung auf Ihre Dichte Karte zwischen dem höchsten Rang x bin mit dem höchsten y bin.

Dies ist ein SEHR schneller Algorithmus, um schnell zu verallgemeinern großen Daten-sets, aber es ist nicht immer richtig, um Genauigkeit zu verbessern, können Sie schneiden Sie die Behälter in kleinere und kleinere Stücke oder Verschiebung der bin-Positionen nach Links oder rechts n-mal und verwenden Sie ein voting-system wählen Sie die Antwort, dass tritt am häufigsten zwischen Studien.
- "nicht immer korrekt": "imagebin.org/105002
- Anstelle von großen Daten-sets, ich habe sehr kleine Datenmengen. Also das ist falsch hier
InformationsquelleAutor Peter Hanneman
0

Könnten Sie Verpixeln das ganze Gebiet, dann gehen Sie zu jedem Punkt, und erhöhen Sie den Wert für alle Pixel innerhalb des Kreises, der den radius um diesen Punkt. Die Pixel mit der höchsten Summe, sind gute Kandidaten.

Natürlich, verlieren Sie möglicherweise einige gute Bereiche oder "halluzinieren" guten Gebieten aufgrund von Rundungsfehlern. Vielleicht könnten Sie versuchen, eine grobe pixellation zuerst, dann verfeinern Sie die zukunftsträchtigen Bereichen.

InformationsquelleAutor Svante
0

Dies ist die berühmte K-closest-point-Algorithmus. Hier beschrieben: http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf
- Nein ist es nicht. Sie könnte eine der besten Kreis zentriert auf einen Punkt, ist nicht Teil des Satzes.
- Dies ist nicht die richtige Antwort
- wenn es ist nicht richtig, es downvote
- Nicht genug Ruf
- Sie jetzt tun 🙂 immer wieder Fragen, interessante Fragen!
- wenn die Antwort nicht korrekt ist, dann bitte deaktivieren Sie als die akzeptierte Lösung.
- O_o Wie konnte das passieren!?
InformationsquelleAutor Jack

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.