Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a four points in plane and need to test (based on point coordinates) whether they are able to form a convex quadrilateral:

convex quadrilateral

Of course, the test should avoid configurations like these:

concave quadrilateral 1

concave quadrilateral 2

Given the diagonals, I can check whether the quadrilateral is convex (simply checking whether the intersection of diagonals is between both ends of both diagonals).

The real problem is how to label the four points and filter out all concave and degenerate configurations (like, for example: $A=B$).

If the labeling is possible (convex case found), the four points should be labeled such that $AC$ and $BD$ are diagonals of a convex quadrialteral.

I wonder if there is an elegant solution (rather than testing every possible permutation of $A, B, C$ and $D$).

share|improve this question

2 Answers 2

up vote 1 down vote accepted

You want to know whether all four points are vertices of their convex hull. So find the convex hull using say Jarvis's march and check whether it has four vertices. You'll have to decide what to do when three points are collinear.

share|improve this answer
    
Thanks. In my original problem, I have a transform that maps 4-points to another 4-points (i.e. planar homography that maps e.g. perspectively distorted view to an undistored one). I found one implementation, where they check whether any three points are colinear. However, what if the points form a deltoid? Then no three points are colinear and still the quadrilateral is concave. –  Libor Apr 10 '12 at 1:36

Maybe a simpler way to solve this problem would be to write down the four vectors which describe the sides of the polygon, and calculate at each vertex the angle between these vectors. If this angle is ever obtuse, then you don't have a convex polygon. This procedure would only require going through 4 calculations.

share|improve this answer
    
There is no polygon. Only the points are given. –  lhf Apr 10 '12 at 2:12
    
So is the problem to construct a convex polygon from those points? Just given 4 points, most polygons formed from those points are not convex. –  Eric Haengel Apr 10 '12 at 2:15
    
@EricHaengel: I don't understand your answer. Most convex quadrilaterals have obtuse angles -- in fact, because the interior angle sum of every quadrilateral is $360^\circ$, the only convex quadrilaterals that don't have obtuse angles are rectangles. –  Jack Lee Apr 10 '12 at 17:35
    
oh ha I'm sorry Jack you're right, I mixed up my words. I meant check whether the angles are greater than 180 degrees instead of obtuse. –  Eric Haengel Apr 11 '12 at 4:37
    
Oh, I see. That seems as if it would be a difficult algorithm to implement -- any three noncollinear points taken in some order form one angle with measure less than $180^\circ$ and another with measure greater than $180^\circ$. If you don't already know where the polygon is, how can you tell which one of those angles to use? –  Jack Lee Apr 11 '12 at 5:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.