Trouver si 4 points sur un plan forment un rectangle?

Question

Est-ce que quelqu'un pourrait s'il vous plaît me montrer en pseudocode de style C comment écrire une fonction (représentez les points comme vous le souhaitez) qui renvoie vrai si 4 points (arguments de la fonction) forment un rectangle, et faux sinon ?

J'ai trouvé une solution qui cherche d'abord à trouver 2 paires de points distinctes avec une valeur x égale, puis fait de même pour l'axe des y. Mais le code est plutôt long. Juste curieux de voir ce que les autres proposent.

Answer 1

• trouver le centre de masse des points de coin: cx=(x1+x2+x3+x4)/4, cy=(y1+y2+y3+y4)/4
• tester si le carré des distances du centre de masse à tous les 4 coins sont égales

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;
}

(Bien sûr, en pratique, tester l'égalité de deux nombres à virgule flottante a et b devrait être fait avec une précision finie : par exemple abs(a-b) < 1E-6)

Answer 2

struct point
{
    int x, y;
}

// teste si l'angle abc est un angle droit
int EstOrthogonal(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 EstRectangle(point a, point b, point c, point d)
{
    return
        EstOrthogonal(a, b, c) &&
        EstOrthogonal(b, c, d) &&
        EstOrthogonal(c, d, a);
}

Si l'ordre n'est pas connu à l'avance, nous avons besoin d'une vérification un peu plus compliquée :

int EstRectangleDansNImporteQuelOrdre(point a, point b, point c, point d)
{
    return EstRectangle(a, b, c, d) ||
           EstRectangle(b, c, a, d) ||
           EstRectangle(c, a, b, d);
}

Answer 3

• traduisez le quadrilatère de sorte qu'un de ses sommets se trouve maintenant à l'origine

• les trois points restants forment trois vecteurs à partir de l'origine

• l'un d'eux doit représenter la diagonale

• les deux autres doivent représenter les côtés

• par la règle du parallélogramme si les côtés forment la diagonale, nous avons un parallélogramme

• si les côtés forment un angle droit, c'est un parallélogramme avec un angle droit

• les angles opposés d'un parallélogramme sont égaux

• les angles consécutifs d'un parallélogramme sont supplémentaires

• par conséquent tous les angles sont des angles droits

• c'est un rectangle

• c'est beaucoup plus concis en code, cependant :-)

  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);
  }

• (Si vous souhaitez que cela fonctionne avec des valeurs en virgule flottante, s'il vous plaît, ne remplacez pas aveuglément les déclarations int dans les en-têtes. C'est une mauvaise pratique. Elles sont là pour une raison. On devrait toujours travailler avec une borne supérieure sur l'erreur lors de la comparaison des résultats en virgule flottante.)

Answer 4

Si les points sont A, B, C & D et que vous connaissez l'ordre, alors vous pouvez calculer les vecteurs :

x=B-A, y=C-B, z=D-C et w=A-D

Ensuite, prenez les produits scalaires (x point y), (y point z), (z point w) et (w point x). Si ils sont tous nuls, alors vous avez un rectangle.

Answer 5

La distance d'un point à l'autre 3 devrait former un triangle rectangle :

|   /      /|
|  /      / |
| /      /  |
|/\_\_\_   /\_\_\_|

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

Simplification :

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