Finden Sie heraus, ob 4 Punkte auf einer Ebene ein Rechteck bilden?

Question 1

Kann mir bitte jemand in Pseudocode im C-Stil zeigen, wie man eine Funktion schreibt (die Punkte beliebig darstellt), die wahr zurückgibt, wenn 4 Punkte (Argumente für die Funktion) ein Rechteck bilden, und andernfalls falsch?

Ich habe mir eine Lösung ausgedacht, die zuerst versucht, 2 verschiedene Punktpaare mit gleichem x-Wert zu finden, und dies dann für die y-Achse tut. Aber der Code ist ziemlich lang. Einfach mal gespannt, was andere sich einfallen lassen.

Question 2

Finden Sie den Massenmittelpunkt der Eckpunkte: cx=(x1+x2+x3+x4)/4, cy=(y1+y2+y3+y4)/4

Testen Sie, ob das Abstandsquadrat vom Massenmittelpunkt zu allen 4 Ecken gleich ist

bool isRectangle(double x1, double y1,
                 double x2, double y2,
                 double x3, double y3,
                 double x4, double y4)
{
  double cx,cy;
  double dd1,dd2,dd3,dd4;

  cx=(x1+x2+x3+x4)/4;
  cy=(y1+y2+y3+y4)/4;

  dd1=sqr(cx-x1)+sqr(cy-y1);
  dd2=sqr(cx-x2)+sqr(cy-y2);
  dd3=sqr(cx-x3)+sqr(cy-y3);
  dd4=sqr(cx-x4)+sqr(cy-y4);
  return dd1==dd2 && dd1==dd3 && dd1==dd4;
}

(Natürlich sollte in der Praxis das Testen auf Gleichheit zweier Fließkommazahlen a und b mit endlicher Genauigkeit durchgeführt werden: zB abs(ab) < 1E-6)

Question 3

struct point
{
    int x, y;
}

// tests if angle abc is a right angle
int IsOrthogonal(point a, point b, point c)
{
    return (b.x - a.x) * (b.x - c.x) + (b.y - a.y) * (b.y - c.y) == 0;
}

int IsRectangle(point a, point b, point c, point d)
{
    return
        IsOrthogonal(a, b, c) &&
        IsOrthogonal(b, c, d) &&
        IsOrthogonal(c, d, a);
}

Wenn die Reihenfolge im Voraus nicht bekannt ist, benötigen wir eine etwas kompliziertere Prüfung:

int IsRectangleAnyOrder(point a, point b, point c, point d)
{
    return IsRectangle(a, b, c, d) ||
           IsRectangle(b, c, a, d) ||
           IsRectangle(c, a, b, d);
}

Question 4

1. Find all possible distances between given 4 points. (we will have 6 distances)
2. XOR all distances found in step #1
3. If the result after XORing is 0 then given 4 points are definitely vertices of a square or a rectangle otherwise, return false (given 4 points do not form a rectangle).
4. Now, to differentiate between square and rectangle 
   a. Find the largest distance out of 4 distances found in step #1. 
   b. Check if the largest distance / Math.sqrt (2) is equal to any other distance.
   c. If answer is No, then given four points form a rectangle otherwise they form a square.

Hier verwenden wir geometrische Eigenschaften von Rechteck/Quadrat und Bit-Magie.

Rechteckeigenschaften im Spiel

Gegenüberliegende Seiten und Diagonalen eines Rechtecks sind gleich lang.
Wenn die diagonale Länge eines Rechtecks sqrt(2) mal seiner Länge ist, dann ist das Rechteck ein Quadrat.

Bit-Magie

Die XOR-Verknüpfung gleicher Zahlen gibt 0 zurück.

Da die Abstände zwischen 4 Ecken eines Rechtecks immer 3 Paare bilden, eines für die Diagonale und zwei für jede Seite unterschiedlicher Länge, ergibt die XOR-Verknüpfung aller Werte 0 für ein Rechteck.

Question 5

Verschieben Sie das Viereck so, dass einer seiner Eckpunkte jetzt im Ursprung liegt
die drei verbleibenden Punkte bilden drei Vektoren vom Ursprung

einer von ihnen muss die Diagonale darstellen
die anderen beiden müssen die Seiten darstellen
bis zum Parallelogrammregel Bilden die Seiten die Diagonale, haben wir ein Parallelogramm

Bilden die Seiten einen rechten Winkel, handelt es sich um ein Parallelogramm mit rechtem Winkel
gegenüberliegende Winkel eines Parallelogramms sind gleich
aufeinanderfolgende Winkel eines Parallelogramms ergänzen sich

daher sind alle Winkel rechte Winkel
es ist ein Rechteck

es ist jedoch viel prägnanter im Code 🙂

static bool IsRectangle(
   int x1, int y1, int x2, int y2, 
   int x3, int y3, int x4, int y4)
{
    x2 -= x1; x3 -= x1; x4 -= x1; y2 -= y1; y3 -= y1; y4 -= y1;
    return
        (x2 + x3 == x4 && y2 + y3 == y4 && x2 * x3 == -y2 * y3) ||
        (x2 + x4 == x3 && y2 + y4 == y3 && x2 * x4 == -y2 * y4) ||
        (x3 + x4 == x2 && y3 + y4 == y2 && x3 * x4 == -y3 * y4);
}

(Wenn Sie möchten, dass es mit Fließkommawerten funktioniert, ersetzen Sie bitte nicht einfach blind die int Erklärungen in den Kopfzeilen. Es ist schlechte Praxis. Sie sind aus einem bestimmten Grund da. Man sollte immer mit einer Obergrenze für den Fehler arbeiten, wenn man Fließkommaergebnisse vergleicht.)

Question 6

Der Abstand von einem Punkt zum anderen 3 sollte ein rechtwinkliges Dreieck bilden:

|   /      /|
|  /      / |
| /      /  |
|/___   /___|

d1 = sqrt( (x2-x1)^2 + (y2-y1)^2 ) 
d2 = sqrt( (x3-x1)^2 + (y3-y1)^2 ) 
d3 = sqrt( (x4-x1)^2 + (y4-y1)^2 ) 
if d1^2 == d2^2 + d3^2 then it's a rectangle

Vereinfachung:

d1 = (x2-x1)^2 + (y2-y1)^2
d2 = (x3-x1)^2 + (y3-y1)^2
d3 = (x4-x1)^2 + (y4-y1)^2
if d1 == d2+d3 or d2 == d1+d3 or d3 == d1+d2 then return true

Question 7

Wenn die Punkte A, B, C & D sind und Sie die Reihenfolge kennen, berechnen Sie die Vektoren:

x=BA, y=CB, z=DC und w=AD

Nimm dann die Punktprodukte (x Punkt y), (y Punkt z), (z Punkt w) und (w Punkt x). Wenn sie alle Null sind, dann haben Sie ein Rechteck.

Question 8

Wir wissen, dass zwei gerade Linien senkrecht sind, wenn das Produkt ihrer Steigungen -1 ist, da eine Ebene gegeben ist, können wir die Steigungen von drei aufeinanderfolgenden Linien finden und sie dann multiplizieren, um zu prüfen, ob sie wirklich senkrecht sind oder nicht. Angenommen, wir haben die Linien L1, L2, L3. Wenn nun L1 senkrecht zu L2 und L2 senkrecht zu L3 ist, dann ist es ein Rechteck und eine Steigung von m(L1)*m(L2)=-1 und m(L2)*m(L3)=-1, dann ist es impliziert, dass es sich um ein Rechteck handelt. Der Code lautet wie folgt

bool isRectangle(double x1,double y1,
        double x2,double y2,
        double x3,double y3,
        double x4,double y4){
    double m1,m2,m3;
    m1 = (y2-y1)/(x2-x1);
    m2 = (y2-y3)/(x2-x3);
    m3 = (y4-y3)/(x4-x3);

    if((m1*m2)==-1 && (m2*m3)==-1)
        return true;
    else
        return false;
}