Mal mein Brainstorming-Senf dazu, weil mir gerade danach war:
Voraussetzung:
1. Alle grafischen Objekte sind komplett freigestellt. D.h.: keine Berührungen oder Überschneidungen der Objekte.
2. Es soll eine Positiv-Erkennung geben. Also nicht prüfen, ob ein Objekt kein Kreis ist. Es könnte ja sein, dass später noch andere Objekte dazu kommen (Dreiecke, Polyeder, etc.)
Das Problem würde ich in 2 Schritten angehen.
1. Alle Objekte (farbige, zusammenhängende Bereiche) ermitteln
2. Die Objekte prüfen
zu 1:
Die Grafik nach Pixeln untersuchen, die nicht mit der Hintergrundfarbe übereinstimmen. Zusammenhängende Bereiche bestimmen und diese in einer Objekt-Liste speichern.
zu 2:
Vorüberlegung:
Was sind Kreise? Es sind Objekte, die durch ihren Radius/Durchmesser bestimmt sind. Also genügt es, diesen zu bestimmen. Für die weiteren Prüfungen wird der Durchmesser verwendet. Der Radius (also Durchmesser durch 2) könnte in weiteren Prüfungen Rundungsfehler verursachen. Da es potentiell noch mehr Rundungsprobleme geben kann, sollten diese sich nicht akkumulieren.
Bei der Prüfung der Objekt kann man einfach den obersten Punkt bestimmen. Dazu wird der tiefste senkrecht darunter liegende bestimmt. Die Länge ergibt den Durchmesser, falls es ein Kreis ist.
Erste Prüfung (kann auch entfallen):
Analog zum senkrechten Durchmesser kann der horizontale Durchmesser bestimmt werden. Diese müssen gleich sein. Vorsicht: Auch bei einem Quadrat ist das so. Bei einer Ellipse allerdings nicht, es sei denn es ist eine gedrehte Ellipse. Zumindest dient es als erste einfache Prüfung. Den Sonderfall, dass die Grafik auf einem 4:3-Monitor erstellt wurde und jetzt auf einen 16:10-Monitor dargestellt wird (Verzerrung) ignoriere ich mal.
Zweite Prüfung (nur, falls erste Prüfung erfolgreich):
Jetzt muss der Mittelpunkt bestimmt werden. Dies klingt erstmal einfach, ist aber es nicht. Bei sehr großen Kreisen hat man auch an den äußersten Punkten mehrere Pixel auf der selben Linie liegen. Also muss man das zusätzlich prüfen und dort die Mitte finden. Bei gerader Anzahl von Pixeln sind jetzt schon Probleme abzusehen, da bei allen weiteren Prüfungen geringfügige Abweichungen/Rundungsfehler berücksichtigt werden müssen.
Es steht jetzt alles zur Verfügung, um einen Kreis zu definieren (Mittelpunkt und Durchmesser). Auf dieser Basis wird nun ein Kreis "erzeugt", der im Idealfall deckungsgleich mit dem Prüfobjekt ist. Es sollte genügen, den Kreisrand zu prüfen.
Allerdings darf man die Rundungsprobleme nicht außer acht lassen und muss entsprechende Toleranzen einplanen.
Besondere Probleme:
- Rundungsfehler
- besonders große Kreise (wie weiter oben schon angedeutet)
- besonders kleine Kreise: Ist ein einzelnes Pixel eine Kreis oder ein Quadrat?
