Re: faster impl of atan2 in java...
Daniel Pitts wrote:
[...]
A little more context might help.
Basically, I have an "Arena" with many "Robots", each robot has (at
least) a location "Vector" and a "Scanner". The Scanner has a heading
"Angle", and an arcWidth (int, but same scale as Angle, and probably
should be an angle, but thats a later refactoring).
When the robots program requests a scan, the scanner (asks the arena)
for the closest robot that is within the scan arc. The scan arc has
the same location as the scanning robot, and the heading of the
Scanner.
So, the approach I'm taking is to go through every robot in the arena,
check to see if it in the scan arc (this is where the atan2 comes in),
and if it is closer than any previous match.
For an arena with 30 robots, each scanning a few times a second, that
translates into a lot of scans.
An important technique for problems of this general flavor
is to recognize that the information developed during one scan
may be helpful in speeding up subsequent scans. For example,
if your Robots are not moving at high speed, the result of two
consecutive scans by the same Robot in the same arc are likely
to be identical: If Fred and Ginger are close at time t0, they
are probably also close at time t0+0.1 second. Similarly, if
Fred is close to Ginger at 30 degrees, then at the same time
Ginger is close to Fred at 210 degrees.
How might you exploit this sort of knowledge? Depends on how
your application is organized, of course. Maybe each Robot could
keep a record of the closest neighbor as of the last time each
arc was scanned, and begin a new scan by asking "Is that neighbor
still in the scan arc, and is there any closer neighbor (in any
direction at all)?" If the answers are Yes and No, then that
neighbor is still the closest in the chosen direction and you
needn't bother figuring out the angles of the others.
Although, I'm wondering if there isn't some algorithm that will help me
reduce the number of robots I need to select through, something like
quadrant reduction, or maybe first ordering the robots from closest to
farthest, and then finding the first robot in that list which is withen
the scan arc. I would think that Math.atan2 is slower that Math.hypot.
Am I wrong?
You'd need to measure, and to realize that the measurement
might come out differently on different machines. Comparing
squared distances is likely to be faster than comparing distances.
Noticing that the distance from Robot r1 to r2 is the same as the
distance from r2 to r1 has the potential to cut the work in half.
The big wins will probably come from finding ways to avoid
the O(N^2) search. Exploiting spatial and temporal continuity
("The situation doesn't change much over a short time interval")
may be a way to do this; you're betting that a quick search will
suffice most of the time, with a full-scale rummaging needed only
every now and then.
You may even be able to forecast the time at which the situation
will change. For example, if you know something about the motions
of the Robots you may be able to solve an equation and say "The
angle from r0 to r1 will remain in its current arc until time t"
and thus completely avoid any angle calculations until that time.
Even if the Robots occasionally maneuver and change course, forcing
you to discard the predictions already made, it may turn out that
they save enough work to justify making them.
--
Eric Sosman
esosman@acm-dot-org.invalid