Breaking down Amazon's mega dropdown

Re:Breaking down Amazon's mega dropdown by moron4hire on Wednesday March 06, 2013 @09:52AM (#5331395)

It's not magic, it's just math. The cross product [1] between the vector of the mouse movement and the vector of the mouse's location to the menu's top left corner tells you the relative orientation of the two vectors. Compare that to cross product in regards to the menu's bottom left corner and you can easily figure out that the mouse must be moving towards the menu. This is much easier than figuring out the bounding triangle that the person drew in this article and then figuring out if the mouse is inside of it.

[1] http://en.wikipedia.org/wiki/Cross_product

[ Parent | on HN ]

Re:Breaking down Amazon's mega dropdown by Dn_Ab on Wednesday March 06, 2013 @10:28AM (#5331588)

Are you sure about that? The dot product gives a measure of the orientation between two vectors, the cross product gives perpendicularity and is vector valued (kind of, the distinction matters more for physics than graphics). It also only makes sense in 3 and 7 dimensions without generalizing the concept of vector.

[ Parent | on HN ]

Re:Breaking down Amazon's mega dropdown by moron4hire on Wednesday March 06, 2013 @11:08AM (#5331822)

Balls, you are correct, dot product is the correct operation, not cross product. Been a while since graphics ops were on my table.

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".

[ Parent | on HN ]

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.

[ Parent | on HN ]

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 ;)

[ Parent | on HN ]

Re:Breaking down Amazon's mega dropdown by Dn_Ab on Wednesday March 06, 2013 @11:41AM (#5332039)

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.

[ Parent | on HN ]

Re:Breaking down Amazon's mega dropdown by gbhn on Wednesday March 06, 2013 @12:17PM (#5332271)

You need cross product if you want to know sign. Dot product won't tell you which side of the line you're on, and that sounded like a big part of the algorithm.

[ Parent | on HN ]

Re:Breaking down Amazon's mega dropdown by munchbunny on Wednesday March 06, 2013 @05:08PM (#5334355)

No, the dot product won't work in this case. Take the two edges of the triangle as vectors. You want the mouse vector to fall in between. The dot product can't tell you which side of the two edge vectors your mouse vector falls on, but the cross product can if you look at the component of the cross product that points in/out of the screen.

Actually, you can make the dot product give you that answer, but you would need use the dot product of the mouse vector and two vectors normal to the edge vectors, which is really just a roundabout way of using the cross product.

[ Parent | on HN ]