Problem
Ich möchte alle Pixel erhalten, die sich innerhalb eines Kreises eines bestimmten Radius um einen bestimmten Punkt befinden, wobei Punkte nur ganzzahlige Koordinaten haben können , dh Pixel in einer Leinwand.
Also möchte ich alle Punkte im gelben Bereich erhalten (x, y)
und r
.
Nähert sich
Der effizienteste Weg, den ich mir vorstellen kann, besteht darin, ein Quadrat zu durchlaufen (x, y)
und den euklidischen Abstand für jeden Punkt zu überprüfen :
for (int px = x - r; px <= x + r; px++) {
for (int py = y - r; py <= y + r; py++) {
int dx = x - px, dy = y - py;
if (dx * dx + dy * dy <= r * r) {
// Point is part of the circle.
}
}
}
Dies bedeutet jedoch, dass dieser Algorithmus (r * 2)^2 * (4 - pi) / 4
Pixel überprüft , die nicht Teil des Kreises sind. dx * dx + dy * dy <= r * r
, was ziemlich teuer erscheint, wird fast immer redundant genannt 1 / 4
.
Die Integration von etwas wie dem, was hier vorgeschlagen wurde, könnte die Leistung verbessern:
for (int px = x - r; px <= x + r; px++) {
for (int py = y - r; py <= y + r; py++) {
int dx = abs(x - px), dy = abs(y - py);
if (dx + dy <= r || (!(dx > r || dy > r) && (dx * dx + dy * dy <= r * r))) {
// Point is part of the circle.
}
}
}
Wie der Autor selbst betonte, wird dies wahrscheinlich nicht schneller sein, wenn sich die meisten Punkte innerhalb des Kreises befinden (insbesondere wegen abs
), was pi / 4
in diesem Fall der Fall ist.
Ich konnte zu dieser Frage keine Ressourcen finden. Ich suche speziell nach einer Lösung in C ++ und nicht nach etwas in SQL .
Antworten:
Okay, hier sind die Benchmarks, die ich versprochen habe.
Installieren
Ich habe Google Benchmark verwendet und die Aufgabe bestand darin, alle Punkte innerhalb des Umfangs des Kreises in a einzufügen
std::vector<point>
. Ich vergleiche für eine Reihe von Radien und ein konstantes Zentrum:Die Ergebnisse jedes Algorithmus werden auf Richtigkeit geprüft (verglichen mit der Ausgabe des OP-Algorithmus).
Bisher werden folgende Algorithmen verglichen:
enclosing_square
.containing_square
.edge_walking
.binary_search
.Ergebnisse
Code
Der vollständige Testcode ist unten aufgeführt. Sie können ihn kopieren, einfügen und selbst testen.
fill_circle.cpp
enthält die Implementierung der verschiedenen Algorithmen.main.cpp
fill_circle.hpp
fill_circle.cpp
quelle
Um eine wiederholte Erzeugung von Pixeln an Achsen zu vermeiden, sollten Schleifen von 1 gestartet und Mittellinien (ix == 0 oder Linie == 0) in einer separaten Schleife gezeichnet werden.
Beachten Sie, dass es auch einen reinen ganzzahligen Bresenham-Algorithmus zum Erzeugen von Umfangspunkten gibt.
quelle
Okay, zuerst berechnen wir das innere Quadrat des Kreises. Die Formel dafür ist einfach:
Nun liegt jeder Punkt zwischen
(-h, -h)
und(+h, +h)
innerhalb des Kreises. Hier ist ein Bild von dem, was ich meine:Der verbleibende blaue Teil ist etwas knifflig, aber auch nicht zu kompliziert. Wir beginnen ganz oben im blauen Kreis
(x = 0, y = -radius)
. Als nächstes gehen wir nach rechts (x++
), bis wir den Kreisperimiter verlassen (bisx²+y² < r²
nicht mehr gilt). Alles zwischen (0, y) und (x, y) liegt innerhalb des Kreises. Aufgrund der Symmetrie können wir diese 8-fach erweiternJetzt gehen wir 1 Zeile nach unten (
y--
) und wiederholen die obigen Schritte (wobei wir den neuesten Wert von beibehaltenx
). Fügen Sie jedem Punkt den Mittelpunkt des Kreises hinzu, und fertig.Hier ist eine Visualisierung. Aufgrund der Hochskalierung gibt es einige Artefakte. Der rote Punkt zeigt, was wir bei jeder Iteration testen:
Hier ist der vollständige Code (mit opencv zeichnen Sie das Zeug):
quelle
Dies ist eine Optimierung, die die Suchdimension um 1/4 reduziert:
oder besser, Verbesserung der Leistung der Iteration des zweiten Kreises unter
for
Vermeidung derif
BedingungNun, ich denke, dass eine andere Option eine binäre Suche nach der Obergrenze ist:
Die Idee der binären Suche besteht darin, die Obergrenze optimal zu finden und die
if
Bedingungen und Berechnungen innerhalb desfor
Zyklus zu vermeiden . Dazu wird geprüft, welche die größte Ganzzahl ist, die den Abstand zwischen dem aktuellen Punkt und dem Radius innerhalb des Kreises ergibt.PD: Entschuldigung mein Englisch.
quelle
Code
Basierend auf der Idee von @ScottHunter habe ich den folgenden Algorithmus entwickelt:
Algorithmus erklärt
Dieser Algorithmus führt eine winzige Anzahl von Überprüfungen durch. Insbesondere wird nur in jeder Zeile geprüft, bis der erste Punkt erreicht ist, der Teil des Kreises ist. Außerdem werden Punkte links vom zuvor identifizierten Punkt in der nächsten Zeile übersprungen. Zusätzlich wird durch Verwendung von Symmetrie nur die Hälfte der Zeilen (
n/2 + 1/2
wie wir bei 0 beginnen) überprüft.Dies ist eine Visualisierung des von mir erstellten Algorithmus. Der rote Umriss zeigt das Quadrat an, das zuvor überprüft worden wäre, und die schwarzen Pixel geben den realen Kreis an (wobei das rote Pixel in der Mitte die Mitte ist). Der Algorithmus überprüft Punkte (blau markiert) und durchläuft gültige Punkte (grün markiert).
Wie Sie sehen können, ist die Anzahl der blauen Pixel am Ende winzig, dh es werden nur wenige Punkte durchlaufen, die nicht Teil des Kreises sind. Beachten Sie außerdem, dass jedes Mal nur das erste grüne Pixel überprüft werden muss. Die anderen Pixel werden nur durchlaufen, weshalb sie sofort angezeigt werden.
Anmerkungen
Die Achsen könnten natürlich leicht umgekehrt werden.
Dies könnte optimiert werden, indem die Symmetrie noch stärker ausgenutzt wird, dh dass die Zeilen mit den Spalten identisch sind (das Durchlaufen aller Zeilen entspricht dem Durchlaufen aller Spalten von links nach rechts, von oben nach unten, umgekehrt, umgekehrt). vise vera) und nur ein Viertel der Reihen von der Mitte nach unten zu gehen, würde ausreichen, um genau zu bestimmen, welche Punkte Teil des Kreises sein werden. Ich bin jedoch der Meinung, dass die geringfügige Leistungssteigerung, die dies verursachen wird, den zusätzlichen Code nicht wert ist.
Wenn jemand es codieren möchte, schlagen Sie eine Bearbeitung dieser Antwort vor.
Code mit Kommentaren
quelle
Das Problem hat eine feste Komplexität von O (n ^ 2), wobei n der Radius des Kreises ist. Die gleiche Komplexität wie ein Quadrat oder eine normale 2D-Form
Es kommt nicht daran vorbei, dass Sie die Anzahl der Pixel in einem Kreis nicht reduzieren können, auch wenn Sie die Symmetrie ausnutzen, bleibt die Komplexität gleich.
Ignorieren Sie also die Komplexität und suchen Sie nach Optimierung.
In Ihrer Frage geben Sie an, dass das
abs
pro Pixel (oder 4. Pixel) etwas zu teuer ist.Einmal pro Zeile ist besser als einmal pro Pixel
Sie können es auf 1 Quadratwurzel pro Zeile reduzieren. Für einen Kreisradius 256 sind das 128 Quadratwurzeln
Um mehr daraus zu machen, können Sie eine Nachschlagetabelle für die SQL-Root-Berechnungen erstellen.
Alles ganzzahlig
Alternativ können Sie die Variation der Bresenham-Linie verwenden , die die Quadratwurzel durch alle ganzzahligen Berechnungen ersetzt. Es ist jedoch ein Chaos und würde keinen Nutzen bringen, wenn das Gerät keine Gleitkommaeinheit hat.
quelle
Sie können ein Quadrat zeichnen, das in den Kreis passt, und es ist ziemlich einfach festzustellen, ob der Punkt hineinfällt.
Dadurch werden die meisten Punkte (2 * r ^ 2) in O (1) -Zeit gelöst, anstatt alle (4 * r ^ 2) Punkte zu durchsuchen.
Bearbeiten: Für den Rest der Punkte müssen Sie nicht alle anderen Pixel schleifen. Sie müssen die 4 Rechtecke mit den Abmessungen [(2r / sqrt (2)), r- (r / sqrt (2))] auf den 4 Seiten (Nord, Ost, Süd, West) des Quadrats schleifen Innerhalb. Es bedeutet, dass Sie nie nach den Quadraten an den Ecken suchen müssen. Da es vollständig symmetrisch ist, können wir die absoluten Werte der Eingabepunkte nehmen und suchen, ob der Punkt innerhalb von Halbquadraten auf der positiven Seite der Koordinatenebene liegt. Das heißt, wir schleifen nur einmal statt 4.
Die Gesamtkomplexität des Codes beträgt O ((rr / sqrt (2)) * (r / sqrt (2))). Dies ist nur eine Schleife für die Hälfte eines einzelnen Rechtecks (8-Wege-Symmetrie), das sich zwischen dem inneren Quadrat und dem äußeren Rand des Kreises befindet.
quelle
O(n^2)
nicht darin, dassO((r-r/sqrt(2))* (r/sqrt(2)))
Sie eine quadratische und große O-Notation angeben. Sie sollte die Koeffizienten nicht enthalten und alle außer der höchsten Potenz müssen ignoriert werden. Dieses Problem kann unten nicht vereinfacht werdenO(n^2)