# Identify diagonals in convex quadrilateral

This topic is 4082 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Given four points that define a convex quadrilateral. What is the fastest method to identify the diagonals? Cheers, -Dirk

##### Share on other sites
I don't know about fastest, but here's a method. At worst, it takes 12 24 additions, 8 16 multiplications and up to four signed comparisons (this can be improved upon slightly at the cost of readability):

Arbitrarily label the vertices A, B, C, D (assumed to be in the x-y plane).
Calculate the edge vectors AB, BC, CD, DA.
Calculate the cross-products

c1 = AB × BC
c2 = BC × CD
c3 = CD × DA
c4 = DA × AB

If all of {c1.z, c2.z, c3.z, c4.z} have the same sign, then you 'guessed' the edges right and the diagonals are AC, BD.

Edit: If not, then they are either AB, CD; or AD, BC. In this case, you'll need to switch two vertices (say, A and B) and repeat the calculation.

My intuition tells me that it's impossible to work this out without performing four calculations, but its altogether possible that they could be made simpler than this.

[Edited by - TheAdmiral on May 5, 2007 7:54:59 PM]

##### Share on other sites
Cool, many thanks!

Actually my points exist is R3, but I know the plane normal. Do need to project or can this also be solved in 3D?

##### Share on other sites
Quote:
 Original post by TheAdmiralIf [...] the diagonals are AC, BD. If not, then they are AB, CD.
Except, of course, when they are AD and BC.

##### Share on other sites
I'm sure this is wrong and that I've missed some case or another (don't have time to double-check at the moment), but I'll go ahead and post it just to contribute something to the discussion:
vector3 c1 = ABxBCvector3 c2 = BCxCDvector3 c3 = CDxDAint s1 = sign(dot(c1,c2))int s2 = sign(dot(c1,c3))int s3 = sign(dot(c2,c3))if (s1 == s2) {    if (s1 == s3) {        ...diagonals are AC and BD...    } else {        ...diagonals are AD and BC...    }} else {    ...diagonals are AB and CD...}

##### Share on other sites
Quote:
Original post by Christer Ericson
Quote:
 Original post by TheAdmiralIf [...] the diagonals are AC, BD. If not, then they are AB, CD.
Except, of course, when they are AD and BC.

I must admit I'm a little confuddled right now (read: drunk), but if the diagonals were AD and BC, wouldn't the test still come out negative, only with the values having the opposite sign? Or is that your point?
As far as I can tell, there's only one way to get the order wrong under isomorphism.

Quote:
 Actually my points exist is R3, but I know the plane normal. Do need to project or can this also be solved in 3D?
It works just fine in 3D, but you'd need to project the cross-products to the normal's vector before comparing. In this case, I suspect there's a more efficient method.

##### Share on other sites
Quote:
Fix one vertex of the convex quad and call it A. Arbitrarily labeling the remaining three vertices then gives six different labelings, with three unique pairs of diagonals: AB+CD, AC+BD, and AD+BC.

My point was that your code only distinguished two of these cases, not three. Therefore what you suggested cannot have been a complete solution.

##### Share on other sites
Quote:
 Original post by Christer EricsonMy point was that your code only distinguished two of these cases, not three. Therefore what you suggested cannot have been a complete solution.
Good call. I think it's fixed now.

##### Share on other sites

Label vertices arbitrary as A,B,C and D. Additionaly to the vertices I have the plane normal n. Now I simply test three edges AB, AC and AD and test the if the other two vertices are on opposite sides where I use the plane through A with the normal direction n_i = n x AX (X = B,C,D) to define the test plane.

Anything that could go wrong with this? It is similar to jyk's test though I need the normal while he gets along with the edges...? Aren't in his example

vector3 c1 = ABxBC
vector3 c2 = BCxCD
vector3 c3 = CDxDA

c1, c2 and c3 parallel since all edges lie in the same plane?

##### Share on other sites
While I didn't verify the details of what jyk posted, his basic approach is correct. Here's a full description (albeit using different vector cross products).

In the plane of ABCD, fix A. That leaves six different configurations:
A---B  A---B  A---C  A---C  A---D  A---D| 1 |  | 2 |  | 3 |  | 4 |  | 5 |  | 6 |C---D  D---C  B---D  D---B  B---C  C---B
(1 and 3, 2 and 5, and 4 and 6 have the same diagonals, so we really only have three different cases, as I pointed out earlier.) Now pick three different edge pairs and perform cross products between them. I picked ABxAC, ABxAD, and ACxAD.

Assuming a vantage point looking into the screen you're reading this on, these cross products result in vectors that point in or out of the screen, like so:
         1     2     3     4     5     6ABxAC | in  | in  | out | out | out | in  |ABxAD | in  | in  | out | in  | out | out |ACxAD | out | in  | in  | in  | out | out |
Of course, we don't actually know from which side we will be looking at the quad, so "in" and "out" could be swapped. Neatly though, if you look at the pairs that have the same diagonals (1 and 3, 2 and 5, and 4 and 6) you see they are each others opposites.

Thus, in order to distinguish between the 3 unique cases of different diagonals, we perform the following tests:
// Cases 1 and 3:if SameDirection(ABxAC, ABxAD) && !SameDirection(ABxAC, ACxAD)    then diagonals are AD and BC// Cases 2 and 5:if SameDirection(ABxAC, ABxAD) && SameDirection(ABxAC, ACxAD)    then diagonals are AC and BD// Cases 4 and 6:if !SameDirection(ABxAC, ABxAD) && !SameDirection(ABxAC, ACxAD)    then diagonals are AB and CD
The SameDirection() tests are done with signs of dot products which results in code similar to what jyk posted:

Vector u = Cross(ab, ac), v = Cross(ab, ad), w = Cross(ac, ad);float s = Dot(u, v), t = Dot(u, w);if (s > 0.0f && t < 0.0f) return DIAGONALS_ARE_AD_AND_BC;if (s > 0.0f && t > 0.0f) return DIAGONALS_ARE_AC_AND_BD;if (s < 0.0f && t < 0.0f) return DIAGONALS_ARE_AB_AND_CD;return QUAD_IS_DEGENERATE;

If you know the quad cannot be degenerate, you can optimize this to:

Vector u = Cross(ab, ac), v = Cross(ab, ad), w = Cross(ac, ad);float s = Dot(u, v), t = Dot(u, w);if (s * t < 0.0f) return DIAGONALS_ARE_AD_AND_BC;if (s > 0.0f) return DIAGONALS_ARE_AC_AND_BD;return DIAGONALS_ARE_AB_AND_CD;

If cross products are more expensive than dot products (which isn't necessarily true on all platform) this can be rewritten through two applications of Lagrange's identity into:

float e = Dot(ab, ab), f = Dot(ab, ac), g = Dot(ab, ad), h = Dot(ac, ac), i = Dot(ac, ad);float s = e * i - f * g, t = f * i - h * g;if (s * t < 0.0f) return DIAGONALS_ARE_AD_AND_BC;if (s > 0.0f) return DIAGONALS_ARE_AC_AND_BD;return DIAGONALS_ARE_AB_AND_CD;

The last two versions are about as efficient as this test will ever get.

1. 1
Rutin
25
2. 2
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 14
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631757
• Total Posts
3002141
×