savoir si 4 points sur un plan en forme d'un rectangle?

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

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

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

La distance d'un point à l'autre 3 doit avoir la forme d'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

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.

Ici, nous allons utiliser les propriétés géométriques de rectangle/carré et Peu de Magie.

Propriétés du Rectangle dans le jeu

1. En face de côtés et les diagonales d'un rectangle sont de même longueur.
2. Si la longueur de la diagonale d'un rectangle est sqrt(2) fois toute sa longueur, puis le rectangle est un carré.

Peu De Magie

1. XORing l'égalité des numéros de valeur de retour 0.

Depuis les distances entre les 4 coins d'un rectangle sera toujours de 3 paires, une pour la diagonale et deux de chaque côté de longueur différente, XORing toutes les valeurs de retour de 0 pour un rectangle.

en prenant le produit scalaire suggestion un peu plus loin, vérifier si deux des vecteurs faite par 3 points les points sont perpendiculaires et de voir ensuite si x et y correspondent le quatrième point.

Si vous avez des points de [Ax,Ay] [Bx,By] [Cx,Cy] [Dx,Dy]

vecteur v = B-A
vecteur u = C-A

v(dot)u/|v||u| == cos(theta)

donc, si (c. u == 0) il ya un couple de lignes perpendiculaires à droite.

Je n'en connais pas la programmation en C, mais voici quelques "méta" de programmation pour vous 😛

if (v==[0,0] || u==[0,0] || u==v || D==A) {not a rectangle, not even a quadrilateral}

var dot = (v1*u1 + v2*u2); //computes the "top half" of (v.u/|v||u|)
if (dot == 0) { //potentially a rectangle if true

    if (Dy==By && Dx==Cx){
     is a rectangle
    }

    else if (Dx==Bx && Dy==Cy){
     is a rectangle
    }
}
else {not a rectangle}

il n'y a pas de racines carrées dans le présent, et pas de potentiel pour une division par zéro. J'ai remarqué que les gens de mentionner ces questions sur les anciens messages, donc je pensais que je voudrais offrir une alternative.

Donc, par le calcul, vous avez besoin de quatre soustractions pour obtenir v et u, deux multiplications, un plus et vous avez pour vérifier quelque part entre 1 et 7 des égalités.

peut-être que je suis en train de faire cela, mais je me souviens vaguement avoir lu quelque part que les soustractions et les multiplications sont "plus vite" dans les calculs. Je suppose que la déclaration des variables/tableaux et de définir leurs valeurs est également très rapide?

Désolé, je suis assez nouveau à ce genre de chose, alors j'aimerais des commentaires à ce que je viens d'écrire.

Edit: essayez cette fonction sur mon commentaire ci-dessous:

A = [a1,a2];
B = [b1,b2];
C = [c1,c2];
D = [d1,d2];

u = (b1-a1,b2-a2);
v = (c1-a1,c2-a2);

if ( u==0 || v==0 || A==D || u==v)
    {!rectangle} //get the obvious out of the way

var dot = u1*v1 + u2*v2;
var pgram = [a1+u1+v1,a2+u2+v2]
if (dot == 0 && pgram == D) {rectangle} //will be true 50% of the time if rectangle
else if (pgram == D) {
    w = [d1-a1,d2-a2];

    if (w1*u1 + w2*u2 == 0) {rectangle} //25% chance
    else if (w1*v1 + w2*v2 == 0) {rectangle} //25% chance

    else {!rectangle}
}
else {!rectangle}

J'ai récemment été confronté à un problème similaire, mais en Python, c'est ce que j'ai trouvé en Python, peut-être que cette méthode peut être utile. L'idée est qu'il y a six lignes, et si elle est créée dans un ensemble, il devrait être de 3 unique ligne de distances restantes - la longueur, la largeur et diagonale.

def con_rec(a,b,c,d): 
        d1 = a.distanceFromPoint(b)
        d2 = b.distanceFromPoint(c)
        d3 = c.distanceFromPoint(d)
        d4 = d.distanceFromPoint(a)
        d5 = d.distanceFromPoint(b)
        d6 = a.distanceFromPoint(c)
        lst = [d1,d2,d3,d4,d5,d6] # list of all combinations 
        of point to point distances
        if min(lst) * math.sqrt(2) == max(lst): # this confirms a square, not a rectangle
            return False
        z = set(lst) # set of unique values in ck
        if len(lst) == 3: # there should be three values, length, width, diagonal, if a 
        4th, it's not a rectangle
            return True
        else: # not a rectangle
            return False