Find if 4 points form a four-sided

Question

Can someone please show me an algorithm for writing a function that returns true if 4 points form a quadrangle, and false otherwise? Glasses have no order.

I tried to check all the permutations of 4 points and see if there are 3 points that form a straight line. If there are 3 points that form a straight line, not a quadrangular. But then I understand that there is no way to tell the order. And then I fight for hours of thinking and searching on Google to no avail :(

I read the following questions:

• find if 4 points on a plane form a rectangle?
• Determining the ordering of vertices with the formation of a quadrangle

But do not find a solution. In case 1, he cannot detect another kind of quadrangle, and in 2 he assumes that the points are already quadratheral. Is there any other way to know if 4 points form a quadrangular?

Thanks before.

EDIT FOR CLARIFICATION:

I define a quadrangle as a simple quadrangle, basically all the shapes shown in this picture:

except for the shape labeled "quadrangle" and "complex."

As for the problems with the “collinear triplet check” approach, I tried to check the vertical, horizontal and diagonal lines 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 understand that the rectangle and square will be considered linear, since the slope of the points will be the same. Hope this clarifies the situation.

Answer 1

This means that the quadrangle is convex. Not if it's a simple quadrangle.

I liked this at 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; } } 

Answer 2

It is not possible to determine the order of the vertices and the presence of a quadrangle in the same operation unless you use operations that are much more expensive than what you are already doing.

Answer 3

Checking collinear triplets (like you) excludes cases when four points form triangles or lines.

To exclude also a complex quadrilateral (with intersecting edges):

A quadrangle formed by points A, B, C, and D is complex if the intersection of AB and CD (if there is one) lies between points A and B and the same applies to BC and DA.

Answer 4

Do you have more input than 4 points? because if 4 points succeed in your test, they can always form 3 different quadrangles, sometimes from different families. For example, take a square, add 2 diagonals and remove the side.

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

Answer 5

Let A, B, C, and D be four points. You must assume that the edges are AB, BC, CD, and DA. If you cannot make this assumption, four points will always form a quadrangle.

 if (AB intersects CD) return false if (BC intersects AD) return false return true