Find If 4 Points Form a Quadrilateral

Question

Can someone please show me an algorithm to write a function that returns true if 4 points form a quadrilateral, and false otherwise? The points do not come with any order.

I've tried to check all permutations of the 4 points and see if there's 3 points that forms a straight line. If there's 3 points that forms a straight line than it's not quadrilateral. But then I realize that there's no way to tell the order. And then I struggle for several hours of thinking and googling with no result :(

I've read these questions:

But still find no solution. In the case of 1, it can't detect another kind of quadrilateral, and in 2 it assumes that the points are quadirateral already. Are there any other way to find out if 4 points form a quadirateral?

Thanks before.

EDIT FOR CLARIFICATION:

I define quadrilateral as simple quadrilateral, basically all shapes shown in this picture: Quadirateral

except the shape with "quadrilateral" and "complex" caption.

As for problems with the "checking for collinear triplets" approach, I tried to check the vertical, horizontal, and diagonal lines with something like this:

def is_linear_line(pt1, pt2, pt3):
    return (pt1[x] == pt2[x] == pt3[x] ||
            pt1[y] == pt2[y] == pt3[y] ||
            slope(pt1, pt2) == slope(pt2, pt3))

And realize that rectangle and square will count as linear line since the slope of the points will be all the same. Hope this clears things out.

How do you define a quadrilateral? And please explain what's wrong with checking for collinear triplets in more detail. — tom, Mar 01 '12 at 09:14
@tom: I've edited the question for clarifications. Please tell me if something's still unclear. Thanks. — bertzzie, Mar 01 '12 at 09:26
Thank you. According do this definition, any four points form a quadrilateral if you can choose the edges. — tom, Mar 01 '12 at 10:24
@tom is right. The question should be "if 4 points **can** form a quadrilateral". — karatedog, Mar 01 '12 at 15:38

hfossli · Accepted Answer · 2013-03-20T20:29:58.057

This is for checking if a quadrilateral is convex. Not if it is a simple quadrilateral.

I did like this in objective-c https://github.com/hfossli/AGGeometryKit/

extern BOOL AGQuadIsConvex(AGQuad q)
{
    BOOL isConvex = AGLineIntersection(AGLineMake(q.bl, q.tr), AGLineMake(q.br, q.tl), NULL);
    return isConvex;
}

BOOL AGLineIntersection(AGLine l1, AGLine l2, AGPoint *out_pointOfIntersection)
{
    // http://stackoverflow.com/a/565282/202451

    AGPoint p = l1.start;
    AGPoint q = l2.start;
    AGPoint r = AGPointSubtract(l1.end, l1.start);
    AGPoint s = AGPointSubtract(l2.end, l2.start);

    double s_r_crossProduct = AGPointCrossProduct(r, s);
    double t = AGPointCrossProduct(AGPointSubtract(q, p), s) / s_r_crossProduct;
    double u = AGPointCrossProduct(AGPointSubtract(q, p), r) / s_r_crossProduct;

    if(t < 0 || t > 1.0 || u < 0 || u > 1.0)
    {
        if(out_pointOfIntersection != NULL)
        {
            *out_pointOfIntersection = AGPointZero;
        }
        return NO;
    }
    else
    {
        if(out_pointOfIntersection != NULL)
        {
            AGPoint i = AGPointAdd(p, AGPointMultiply(r, t));
            *out_pointOfIntersection = i;
        }
        return YES;
    }
}

score 1 · Answer 2 · answered Mar 01 '12 at 08:50

1

There is no way to determine both vertex order and presence of a quadrilateral in the same operation unless you use operations that are far more expensive than what you're already performing.

answered Mar 01 '12 at 08:50

Ignacio Vazquez-Abrams

776,304
153
1,341
1,358

the expensiveness of the operation is not a concern. Is there a way for that? – bertzzie Mar 01 '12 at 08:58

score 1 · Answer 3 · answered Mar 01 '12 at 09:47

Checking for collinear triplets (like you did) will exclude cases where the four points form triangles or straight lines.

To exclude also the complex quadrilateral (with crossing edges):

A quadrilateral formed by the points A, B, C and D is complex, if the intersection of AB and CD (if any) lies between the points A and B, and the same applies for BC and DA.

score 0 · Answer 4 · edited Jun 10 '23 at 16:48

First, find all side and diagonal sizes using the distance formula: This.

Next, find all angles using this formula: This

reference from: https://algorithmdotcpp.blogspot.com/2022/01/find-type-of-quadrilateral-with-given-points.html

Code in python:

    # array
    # read 8 number
    points = list(map(int,input().split()))    

    # create separate variable for coordinates
    xa = points[0]
    ya = points[1]
    xb = points[2]
    yb = points[3]
    xc = points[4]
    yc = points[5]
    xd = points[6]
    yd = points[7]

    # edge of quadrilateral using edge formula
    # finding edge using distance formula.
    a = math.sqrt((xb - xa) * (xb - xa) + (yb - ya) * (yb - ya))
    b = math.sqrt((xc - xb) * (xc - xb) + (yc - yb) * (yc - yb))
    c = math.sqrt((xd - xc) * (xd - xc) + (yd - yc) * (yd - yc))
    d = math.sqrt((xa - xd) * (xa - xd) + (ya - yd) * (ya - yd))

    # diagonal of quadrilateral
    # find diagonals.
    diagonal_ac = math.sqrt((xc - xa) * (xc - xa) + (yc - ya) * (yc - ya))
    diagonal_bd = math.sqrt((xd - xb) * (xd - xb) + (yd - yb) * (yd - yb))

    # angles
    # angles of quadrilateral
    # find angle using angle formula.
    A = math.acos((a * a + d * d - diagonal_bd * diagonal_bd) / (2 * a * d))
    B = math.acos((b * b + a * a - diagonal_ac * diagonal_ac) / (2 * b * a))
    C = math.acos((c * c + b * b - diagonal_bd * diagonal_bd) / (2 * c * b))
    D = math.acos((d * d + c * c - diagonal_ac * diagonal_ac) / (2 * d * c))

Now we can determine whether the type of quadrilateral or quadrilateral is not found using if-else conditions.

    # if angles are equal means(90*)
    if (A == B and A == C and A == D):
    
        # if edge size are equal
        if (a == b and a == c and a == d):
            # square
            print("Quadrilateral is square...\n")
            print("area of square :", a * a)
        
        # else
        else:
            # rectangular
            print("Quadrilateral is rectangular...\n")
            print("area of square :", a * b)
        
    
    # angles are not equal but edges are equal
    elif (a == b and a == c and a == d):
        # diamond
        print("Quadrilateral is diamond(Rhombus)...\n")
    
    # opposite edges(sides) are equal
    elif (a == c and b == d):
        # parallelogram
        print("Quadrilateral is parallelogram...")
    
    else:
        print("Quadrilateral is just a quadrilateral...\n")

score 0 · Answer 5 · answered Mar 01 '12 at 09:34

0

Do you have any more inputs than the 4 points? because if 4 points succeed to your test, they can always form 3 different quadrilaterals, sometime of different family. For example, Take a square, add 2 diagonal and remove the side.

So with only 4 points as input, you cannot do better than what you are already doing.

answered Mar 01 '12 at 09:34

UmNyobe

22,539
9
61
90

Nope, there's only 4 inputs. There's no more way to improve it then? – bertzzie Mar 01 '12 at 09:37
Although I am a decade late, but any progress? – Soham Mafidar Aug 17 '21 at 16:39

score 0 · Answer 6 · answered Mar 01 '12 at 09:46

Let A, B, C and D be the four points. You have to assume that the edges are A-B, B-C, C-D, and D-A. If you can't make that assumption, the four points will always form a quadrilateral.

if (A-B intersects C-D) return false
if (B-C intersects A-D) return false
return true

Find If 4 Points Form a Quadrilateral

6 Answers6