Up  Home


Wann bilden 4 Punkte ein Rechteck? (und die Antwort auf ein Quizfrage)

Bei der Inspektion der Daten zu einer Diskretisierung (FEM, FVM) stellte sich die Frage, ob es möglich ist aus vier gegebenen Punkten der Ebene ein Rechteck bzw. ein Quadrat mit mathematisch positiver Orientierung zu konstruieren.

Der nachfolgende Algorithmus liefert eine Antwort. Dazu seien die Punkte A,B,C und D (in dieser Reihenfolge) gegeben.

  1. Datenaufbereitung

    Sind die Punkte verschieden, so liefert dieser erste Schritt einen mathematisch positiv orientierten Polygonzug.

  2. Überprüfe die Innenwinkel (und ggf. die Seitenlängen).

 


Will man nur überprüfen, ob vier Punkte (A,B,C,D) in dieser Reihenfolge ein positiv orientiertes Rechteck bilden, so bietet sich das folgende Vorgehen an.

Sind x, y und z drei verschiedene Punkte der Ebene E, so teilt die durch x und y induzierte Gerade g die Ebene E in zwei Halbebenen. Die Halbebene in die der Normalenvektor n von g "zeigt" wird mit a+ und die andere mit a- bezeichnet.



Liegt der dritte Punkt z nun

Rechnerisch wird die Orientierung der Punkte (x,y,z) über das Vorzeichen der Determinate |y-x, z-x| bestimmt: det(y-x,z-x) > 0 (< 0), dann ist (x,y,z) positiv (negativ) orientiert. Ist det(y-x,z-x)=0, so sind die Punkte kollinear.

Die 4 Punkte (A,B,C,D) formen ein positiv orientiertes Rechteck, falls (A,B,C) und (B,C,D) jeweils einen leftturn bilden und drei Innenwinkel gleich 90° sind.

Gegeben sei nun eine Punktmenge P= {Pi = (xi,yi) X R2: i=0,...,n-1}.

(Quiz-) Frage: Wie viele (verschiedene) Quadrate Q=(A,B,C,D) mit A,B,C,D X P können gebildet werden?

Das naive Verfahren (die brute force Methode, Komplexität O(n4)) lautet: teste alle vierelementigen Teilmengen von P.

                int anz =0;
                for (i=0; i < n; i++){
                  A = Pi;
                  for (j=0; j < n; j++){
                    B = Pj;
                    for (k=0; k < n; k++){
                      C = Pk;
                      for (l=0; l < n; l++){
                        D = Pl;
                        Q.Initialize(A,B,C,D);
                        if ( IsQuadart (Q) ) {Quadrate.pushback(Q);anz++;}
                      }
                    }
                  }
               }
                     Algorithmus (1)

Je nach der Formulierung des Testes IsQuadrat(A,B,C,D) werden evtl. Quadrate mehrfach gezählt: liefert IsQuadrat (A,B,C,D) true falls

Der Algorithmus inspiziert alle möglichen Lösungen (Enumeration) und ist dadurch "teuer". Jedoch liefert der Test (c) eine Möglichkeit den Rechenaufwand erheblich zu reduzieren: eine Lösungszweig wird nur dann weiter verfolgt, falls

  1. A lexikographisch kleinste Punkt ist und
  2. der Polygonzug positv orientiert ist.

Also:

               	int anz =0;
 		for (i=0; i < n; i++){
		  A = Pi;
 		  for (j=0; j < n; j++){
		    B = Pj;
		    if (B < A) continue;
		    for (k=0; k < n; k++){
		      C = Pk;
		      if (( C < A) and !(leftturn(A,B,C))) continue;
		      for (l=0; l < n; l++){
		      D = Pl;
		      if (D< A and !(leftturn(B,C,D))) continue;
		      Q.Initialize(A,B,C,D);
		      // prüfe nur noch die Innenwinkel und Seitenlängen
		      // (auch diese Tests können noch "vorgezogen" werden)
		      if ( IsQuadart (Q) ) {Quadrate.pushback(Q); anz++;}
 		      }
		    }
		  }
                 }
                    Algorithmus (2)

Werden für die Punkte C und D nur solche Punkte zugelassen, die den Abstand a=|A-B| zu ihren Vorgänger haben, ergibt sich aus (2) ein drittes Verfahren. Die Rechenzeiten in der Tabelle beziehen sich auf eine Delphi-Implementierung der Algorithmen (PIII mit 800Mhz). Wie erwartet zeigt sich, dass durch Ausnutzung der Struktur des Problems, eine große Beschleunigung des Verfahrens möglich ist.

n2 #Quadrate Zeit [s] Algorithmus (1) Zeit [s] Algorithmus (2) Zeit [s] Algorithmus (3)
52 50 0.16 0.06 0
82 336 3.73 1.21 0.22
102 825 21.26 5.5 0.61
122 1716 88.3 21.42 1.32
142 3185 312.4 71.4 2.96
162

182

202

5440

8712

13300

861

2174

5046

185.9

478.4

1314

4.9

8.6

14.4

 


 

Anleitung zum Java-Applet: