find if 4 points on a plane form a rectangle?_问答_开发者

Can somebody please show me in C-style pseudocode how to write a function (represent the points however you like) that returns true 开发者_JAVA百科if 4-points (args to the function) form a rectangle, and false otherwise?

I came up with a solution that first tries to find 2 distinct pairs of points with equal x-value, then does this for the y-axis. But the code is rather long. Just curious to see what others come up with.

find the center of mass of corner points: cx=(x1+x2+x3+x4)/4, cy=(y1+y2+y3+y4)/4
test if square of distances from center of mass to all 4 corners are equal

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

(Of course in practice testing for equality of two floating point numbers a and b should be done with finite accuracy: e.g. abs(a-b) < 1E-6)

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

If the order is not known in advance, we need a slightly more complicated check:

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

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.

Here, we are using geometric properties of rectangle/square and Bit Magic.

Rectangle properties in play

Opposite sides and diagonals of a rectangle are of equal length.
If the diagonal length of a rectangle is sqrt(2) times any of its length, then the rectangle is a square.

Bit Magic

XORing equal value numbers return 0.

Since distances between 4 corners of a rectangle will always form 3 pairs, one for diagonal and two for each side of different length, XORing all the values will return 0 for a rectangle.

translate the quadrilateral so that one of its vertices now lies at the origin
the three remaining points form three vectors from the origin
one of them must represent the diagonal
the other two must represent the sides
by the parallelogram rule if the sides form the diagonal, we have a parallelogram
if the sides form a right angle, it is a parallelogram with a right angle
opposite angles of a parallelogram are equal
consecutive angles of a parallelogram are supplementary
therefore all angles are right angles
it is a rectangle

it is much more concise in code, though :-)

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

(If you want to make it work with floating point values, please, do not just blindly replace the int declarations in the headers. It is bad practice. They are there for a reason. One should always work with some upper bound on the error when comparing floating point results.)

The distance from one point to the other 3 should form a right triangle:

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

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

Simplifying:

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

If the points are A, B, C & D and you know the order then you calculate the vectors:

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

Then take the dot products (x dot y), (y dot z), (z dot w) and (w dot x). If they are all zero then you have a rectangle.

We know that two staright lines are perpendicular if product of their slopes is -1,since a plane is given we can find the slopes of three consecutive lines and then multiply them to check if they are really perpendicular or not. Suppose we have lines L1,L2,L3. Now if L1 is perpendicular to L2 and L2 perpendicular to L3, then it is a rectangle and slope of the m(L1)*m(L2)=-1 and m(L2)*m(L3)=-1, then it implies it is a rectangle. The code is as follows

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

taking the dot product suggestion a step further, check if two of the vectors made by any 3 of the points of the points are perpendicular and then see if the x and y match the fourth point.

If you have points [Ax,Ay] [Bx,By] [Cx,Cy] [Dx,Dy]

vector v = B-A vector u = C-A

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

so if (v.u == 0) there's a couple of perpendicular lines right there.

I actually don't know C programming, but here's some "meta" programming for you :P

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}

there's no square roots in this, and no potential for a divide by zero. I noticed people mentioning these issues on earlier posts so I thought I'd offer an alternative.

So, computationally, you need four subtractions to get v and u, two multiplications, one addition and you have to check somewhere between 1 and 7 equalities.

maybe I'm making this up, but i vaguely remember reading somewhere that subtractions and multiplications are "faster" calculations. I assume that declaring variables/arrays and setting their values is also quite fast?

Sorry, I'm quite new to this kind of thing, so I'd love some feedback to what I just wrote.

Edit: try this based on my comment below:

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}

I recently faced a similar challenge, but in Python, this is what I came up with in Python, perhaps this method may be valuable. The idea is that there are six lines, and if created into a set, there should be 3 unique line distances remaining - the length, width, and diagonal.

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

How about to verify those 4 points could form a parallelogram first, then finding out if there exists one right angle.
1. verify parallelogram

input 4 points A, B, C, D;

if(A, B, C, D are the same points), exit;// not a rectangle;

else form 3 vectors, AB, AC, AD, verify(AB=AC+AD || AC=AB+AD || AD=AB+AC), \\if one of them satisfied, this is a parallelogram;

2.verify a right angle

through the last step, we could find which two points are the adjacent points of A;

We need to find out if angle A is a right angle, if it is, then rectangle.

I did not know if there exist bugs. Please figure it out if there is.

Here is my algorithm proposal, for an axis-aligned rectangle test, but in Python.

The idea is to grab the first point as a pivot, and that all the other points must conform to the same width and height, and checks that all points are distinct, via a set, to account for cases such as (1, 2), (1, 2), (10, 30), (10, 30).

from collections import namedtuple

Point = namedtuple('Point', ('x', 'y'))

def is_rectangle(p1, p2, p3, p4) -> bool:
    width = None
    height = None

    # All must be distinct
    if (len(set((p1, p2, p3, p4))) < 4):
        return False

    pivot = p1

    for point in (p2, p3, p4):
        candidate_width = point.x - pivot.x
        candidate_height = point.y - pivot.y

        if (candidate_width != 0):
            if (width is None):
                width = candidate_width
            elif (width != candidate_width):
                return False

        if (candidate_height != 0):
            if (height is None):
                height = candidate_height
            elif (height != candidate_height):
                return False

    return width is not None and height is not None

# Some Examples
print(is_rectangle(Point(10, 50), Point(20, 50), Point(10, 40), Point(20, 40)))
print(is_rectangle(Point(100, 50), Point(20, 50), Point(10, 40), Point(20, 40)))
print(is_rectangle(Point(10, 10), Point(20, 50), Point(10, 40), Point(20, 40)))
print(is_rectangle(Point(10, 30), Point(20, 30), Point(10, 30), Point(20, 30)))
print(is_rectangle(Point(10, 30), Point(10, 30), Point(10, 30), Point(10, 30)))
print(is_rectangle(Point(1, 2), Point(10, 30), Point(1, 2), Point(10, 30)))
print(is_rectangle(Point(10, 50), Point(80, 50), Point(10, 40), Point(80, 40)))