To: pratt%aster@sun.com
Cc: don@brillig.umd.edu
Subject: Eliminating divides in quadrantslope 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 quadrantslope
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