OOP Mustererkennungs Aufgabe

[dutchman79]

Ich fange gerade an ein Art Mustererkennungsproblem in Java umzusetzen.

Auf einem regelmässigen Gitter ( horz. und vert. gleicher Abstand) gibt es ausgezeichnete Punkte, die mit einem "x" markiert sind.
Wie viele Rechtecke kann man bilden, indem man jeweils vier der x-Punkte als Eckpunkte nimmt und diese durch gerade Strecken verbindet ?
Die Rechtecke dürfen auch "schräg" liegen.
Zusätzlich soll ich ermitteln wieviele der Rechtecke Quadrate sind und eine Flächenstatistik erstellen.

Ein Beispiel der Daten die ich einlese:

*Dies ist ein 4x5 Beispiel mit 2 Rechtecken, davon 2 Quadrate
*1. Zeile: Dimensionen, danach Gitter zeilenweise
*/
4 5
0x0x0
0x000
0x0xx
00x00

Als Ausgabe möchte ich so etwas produzieren wie:

1.Rechteck: (1,2) (1,4) (3,4) (3,2)
2.Rechteck: (1,4) (3,5) (4,3) (2,2)
Insgesamt: 2 Rechtecke davon 2 Quadrate
Anzahl mit Flaeche   4:   1
Anzahl mit Flaeche   5:   1

Ich suche gerade einen möglichst effizienten Algorithmus und habe irgendwie noch keine Ahnung.
Hat jemand eine gute Idee ?

 

[Final_Striker]

Zum Thema Mustererkennung existiert relativ viel Literatur, musst dich da wohl einlesen.

 

[JohannisderKaeufer]

Reicht ein einfacher Algorithmus nicht aus?

Ich würde behaupten das die Daten in Form von
(1,2)
(1,4)
...
(4,3)

besser aufgehoben sind.

 

[dutchman79]

Okay,

Mit dem Algorithmus habe ich gerade meine Schwierigkeiten.

Ich sehe ein dass wenn ich das Feld auslesen und zB in der der selben Zeile in der 2. und 3 .Spalte ein Eckpunkt habe, ich dann nur noch suchen muss in genau diesen Spalten, weil nur dort dann noch ein Rechteck oder Quadrat geformt werden könnte.

Nur um dann irgendwie richtung allgemeiner Fall statt diesen Spezialfällen zu kommen bereitet mir Schwierigkeiten.

 

[MrWhite]

Hmm, ich würde das mit einer Art Scanning Algorithmus machen. Ist nicht ganz naiv, sollte auch ein besseres Laufzeitverhalten als Bruteforce haben.

Nimm einen beliebigen Punkt mit X.
Jetzt lege für jeden Winkel (1°..360° oder wenn schief bedeutet, dass es nur 90° und 45° sein können, dann 45°) eine Gerade durch diesen Punkt, merke dir alle Punkte, die du für einen Winkel triffst. Für diese Punkte musst du jetzt im Prinzip immer nur Lote (als Halbgeraden, potentiell in beide Richtungen) erstellen und dir wiederum merken, welche Punkte die treffen. Wenn du dann vom dritten (Schnitt-)Punkt aus mit einem Lot wieder durch den Ursprungspunkt kommst, hast du ein Rechteck. Counter erhöhen... Jetzt kannst du für das gefunde Rechteck noch die Streckenlängen prüfen und feststellen, ob es ein Quadrat ist.

Bruteforce ist natürlich eazy peazy. Da würde ich dann auch keine Optimierungen mehr durchführen.

Hmm, hab nochmal ein bissal gestöbert: Für Bildverarbeitung (und im Prinzip hast du ein binäres Bild), kannst du so etwas mit der Hough-Transformation lösen.

Hough transform - Wikipedia, the free encyclopedia
Intro

 

[JohannisderKaeufer]

In deinem Beispiel hast du

7 Punkte

Nimm den ersten Punkt (Root) und entferne ihn aus der Liste (Rest)

Nun bildest du Vektoren zu allen Punkten i...n in Rest die ihren Ursprunkg in root haben
vx = rest.x - root.x
vy = rest.y - root.y

Nun berechnest du für alle diese Vektoren ob sie paarweise Orthogonal, (Rechtwinklig zueinander stehen).

Für die verktoren j und k kann das so aussehen.
v[j].x * v[k].x + v[j].y * v[k].y == 0
Beim Skalarprodukt von zwei Vektoren muß 0 herauskommen ansonsten nicht Rechtwinklig.


Hast du einen oder mehrere Treffer z.B Vektor 2 und 3
Dann schaue ob in rest ein Punkt der folgende Kriterien erfüllt existiert, das wäre dann der fehlende Eckpunkt.

x = root.x + v[2].x + v[3].x
und
y = root.y + v[2].y + v[3].y

Wenn ja, Dann hast du ein Rechteck gefunden, wenn nein, Pech gehabt.

Nun hast du erstmal alle Rechtecke gefunden, die root als einen Eckpunkt haben. Gratulation.

Nun entferne root aus deinem Gedächtnis nimm Rest such dir daraus einen neuen Punkt heraus und wiederhole den gesamten Algorithmus, bis in Rest weniger als 3 Elemente vorhanden sind.

Mit den oben berechneten Vektoren, ist es auch ein Kinderspiel herauszubekommen ob es sich um ein Quadrat handelt und wie groß der Flächeninhalt ist.

Also nix Spalten schauen oder Gradzahlen durchgehen, es gibt auch grade zwischen 0 und 1. 0,5 zum Beispiel.

Etwas Algebra und fertig ist die Luzi.

Skalarprodukt ? Wikipedia

Orthogonalität ? Wikipedia

 

[Kaniee]

Hmm...also ich würde die Eckpunkte nehmen und durchgehen. Dabei bei jedem noch die Folgenden durchzählen. Somit hast du jeden Punkt mal mit jedem verbunden. Dann die Steigung zwischen den beiden ausrechnen und sie um 90 Grad drehen. Dann nachschauen ob auf der Steigung in Punkt liegt und abschliesend berrechnen wo der letzte Punkt liegt. Natürlich muss man noch prüfen ob an dem berechneten Punkt wirklich ein Eckpunkt liegt.
Es ist nicht wirklich effizient aber es müsste funktionieren und alles Möglichkeiten abdecken.

Kaniee

Edit: hatte das von JohannisderKaeufer nicht gesehen als ich das geschrieben hab...sieht ähnlich aus

 

[dutchman79]

Danke schonmal für das Mitdenken ...

@JohannisderKauefer: Danke für die gute und verständliche Erklärung.

 

[Threadpool@]

Da mir die Aufgabe bekannt vorkam, such mal nach "Finding squares and rectangles in set of points", da müsste es ein gleichnamiges Paper geben das genau diese Thematik mit relativ effizienten Algorithmen aufgreift.

 

[dutchman79]

So, bin jetzt bei der Implementierung.

Habe das Projekt schon Mal aufgeteilt in 3 packages.
Eins zur Eingabe, eins zur Verarbeitung und eins zur Ausgabe.

Wenn ich es richtig verstanden habe, brauche ich beim Einlesen nur die Dimensionen und die Markierte Punkte zu merken ? Die Letzteren würde ich dann zB in eine ArrayList stecken ?