From: Don Hopkins
Subject: Eliminating divides in quadrantslope comparisons
Date: 11 September 1987 at 11:00:48 CEST
To: pratt%aster@sun.com
Cc: don@brillig.umd.edu
I made the change that you suggested to my pie menu cursor tracking
algorithm  it's working just great now, 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
From: coraki!pratt@Sun.COM (Vaughan Pratt)
Subject: Re: Eliminating divides in quadrantslope comparisons
Date: 11 September 1987 at 19:16:09 CEST
To: Don Hopkins
Great, glad it worked out.
I forwarded your message to Mike Pitteway (the visiting Pommie).
v
From: Don Hopkins
Subject: Eliminating divides during pie menu tracking
Date: 14 September 1987 at 10:03:46 CEST
To: weiser.pa@xerox.com
Cc: don@brillig.umd.edu
Vaughn Pratt suggested an improvement to my quadrantslope algorythm
for pie menu tracking, which eliminates the division done every time
the mouse moves during cursor tracking. You can eliminate the divide
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, do the divisions 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 to get the
cursor slope, and comparing it with the slice edge slopes, you compare
the numerator of the cursor slope with the denominator of the cursor
slope times the slice edge slope.
I put the modification into uwm, and it works fine! I want to fix the
NeWS pie menus to use this scheme, because they're using atan2 now,
and they seem to feel "heavy" when things are going on. Anyway, atan2
loses if you want to have different sized wedges.
Don