To: pratt%aster@sun.com Cc: don@brillig.umd.edu Subject: Eliminating divides in quadrant-slope comparisons --text follows this line-- I made the change that you suggested to my pie menu cursor tracking algorithm -- it's working just great, and saving zillions of divisions! Here is a description of the algorithm, on a much more convenient medium than Two Guys from Italy napkins: When tracking the cursor in a pie menu, every time the cursor moves, a check is made to see if it has moved into a different slice of the menu. This is done by comparing the angles of the slice edges with the angle from the menu center to the cursor. Instead of representing the angles as degrees or radians, and using atan2 to get the cursor angle during tracking, an angle is encoded as a quadrant and a slope. The quadrant and slope are defined such that as the angle around the circle increases, the quadrant and (always positive) slope increase. The quadrant and slope may be defined thusly: Y ^ s=-x/y | s=y/x | quad 1 | quad 0 x<=0,y>0 | x>0,y>=0 X ----------+----------> quad 2 | quad 3 x<0,y<=0 | x>=0,y<0 | s=-y/-x | s=x/-y | (However, in my X pie menu implementation, from which I removed the division, everything's upside down and inside out, due to the screen coordinate system. I'll get it right when I put quadrant-slope tracking into NeWS pie menus.) The case of x=0,y=0 is never encountered, because the center of the menu (inside a certain radius, or a square if you want to be quick&tacky) is an inactive region, which makes no selection from the menu. The case of no selection is the first things tested for. Another thing I still need to teach it to do is to check against the edges of the current slice first, then the neighboring slices, and finally the rest of the slices. That will handle most cases with only a few comparisons. As you suggested, I eliminate the divide that was used to calculate the cursor slope, by multiplying both sides of the slope comparison by the denominator of the cursor slope. i.e. as before, I do cos, sin, and division to calculate the slopes of the slice edges when laying out the menu, but when tracking the cursor, and comparing its slope with the slice edge slopes, instead of dividing the (x,y) cursor offset to get the cursor slope, I now compare the numerator of the cursor slope with the denominator of the cursor slope times the slice edge slope. i.e.: numerator / denominator < slice.leftedge.slope is the same as numerator < denominator * slice.leftedge.slope (Given numerator >= 0, denominator > 0) Thanks a lot for the suggestion! I don't remember the name of the chap with the beard who was visiting from England, but if you think he'd be interested, you can forward him this. -Don