Re:Breaking down Amazon's mega dropdown
by moron4hire on Wednesday March 06, 2013 @03:05PM
(#5333457)
After some playing around, dot product won't do it. You can get close with dot product, but it really only gives you the general direction. Cross product (and really, only calculating the Z component of the cross product of coplanar 3D vectors) will get it exactly right every time.
So basically, for a moving between two mouse points (Ix, Iy) and (Ax, Ay), and a top left menu corner (Bx, By) and bottom left (Cx, Cy), then:
DAx = Ax - Ix
DAy = Ay - Iy
DBx = Bx - Ix
DBy = By - Iy
DCx = Cx - Ix
DCy = Cy - Iy
Z1 = DBx * DAy - DAx * DBy
Z2 = DCx * DAy - DAx * DCy
Then, you know you're headed towards that menu if Z1 < 0 and Z2 > 0.
Could be simplified a little if you assume the X component of the top left corner of the menu will be the same as the X component of the bottom left corner, but the math was clearer to keep them separate.
Re:Breaking down Amazon's mega dropdown
by moron4hire on Wednesday March 06, 2013 @03:29PM
(#5333644)
And if you have any convex polygon as an ordered, circular list of points proceeding clockwise, then you can easily loop around the points checking your cross product values making sure they are all greater than 0 to determine if the point is in the polygon. You'll have to tessalate concave polygons into a list of convex polygons, but that's eaaaaaasy ;)
Right and excellent explanation. I was more disagreeing with your definition than saying it could not be done with "cross products" (although it's still bad terminology, biased to people that already know the concepts). That's why I couldn't say you were wrong. Intuitively, a measure of how parallel two vectors of arbitrary dimensions are, is a better default when talking about orientation of vectors.
EDIT: Well, cross product would work, too, if you extended the 2D vectors into 3D vectors, coplanar in the screen. The orientation of the cross product into or out of the screen would also tell you the relative orientation of the two vectors. So then, you'd be looking for the two cross products with differing signs on the Z component to tell you if it's "in the triangle".