Identify diagonals in convex quadrilateral
Author
Given four points that define a convex quadrilateral. What is the fastest method to identify the diagonals?
Cheers,
-Dirk
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.
Admiral
[Edited by - TheAdmiral on May 5, 2007 7:54:59 PM]
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.
Admiral
[Edited by - TheAdmiral on May 5, 2007 7:54:59 PM]
Author
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?
Actually my points exist is R3, but I know the plane normal. Do need to project or can this also be solved in 3D?
Quote:Original post by TheAdmiralExcept, of course, when they are AD and BC.
If [...] the diagonals are AC, BD. If not, then they are AB, CD.
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...}Quote:Original post by Christer EricsonQuote:Original post by TheAdmiralExcept, of course, when they are AD and BC.
If [...] the diagonals are AC, BD. If not, then they are AB, CD.
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.
Admiral
Quote:Original post by TheAdmiralFix 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.
[...] Or is that your point?
My point was that your code only distinguished two of these cases, not three. Therefore what you suggested cannot have been a complete solution.
Quote:Original post by Christer EricsonGood call. I think it's fixed now.
My point was that your code only distinguished two of these cases, not three. Therefore what you suggested cannot have been a complete solution.
Admiral
Author
What about this:
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?
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?
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:
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:
Thus, in order to distinguish between the 3 unique cases of different diagonals, we perform the following tests:
If you know the quad cannot be degenerate, you can optimize this to:
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:
The last two versions are about as efficient as this test will ever get.
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---BAssuming 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 |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 CDVector 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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
