faster impl of atan2 in java...

[Daniel Pitts]

Specifically, I have an Angle class and a Vector class, and I'd like to
be able to convert between them quickly...

----Context----
The Angle class stores its value as a 8 bit integer value representing
"bygrees" (byte degrees). each "bygree" is 1/256th of a circle, with 0
starting at 12:00 going clockwise.
The Vector class stores its value as a pair of floating (double
precision) values.

After running it through a profiler, I've optimized the angle class to
precompute all 256 possible values, including sine, cosine, radian
conversion, etc...Good speed increase

But, now my application is bottlenecking on an Math.atan2 call,
converting a vector's direction to an Angle object.

----One solution----
I'm trying to think of ways to speed up the conversion of Vectors to
Angles, but the only way I can think to precompute this is to make a 2d
array of Angle objects. and return
angleFor[normalizeForLookup(x)][normalizeForLookup(y)]. Where
normalizeForLookup would handle rounding and bound's checking.

OR, I could use an atan lookup for int((y/x) * k) (k to be determined),
but I would have to find a suitable k, and maybe some other tricks.

On the plus side, I can determine that the largest magnetude of any
vector would be sqrt(2) * 1000, and accuracy isn't extremely important.

The downside to this would be creating an array of approximitly
4,000,000 elements. Although most of those elements point to a subset
of 256 objects, 4 megs of references is non negligible. Not to mention
the init time required.

----Another possible solution----

So, the other alternative I see is to find a faster implementation of
atan2 (or atan), and use it in place of Math.atan2, but I wouldn't know
where to start. a quick search on google returned nothing, but I'm not
very good at finding keywords to search.

Thanks in advance,
Daniel.

 

[Luc The Perverse]

Specifically, I have an Angle class and a Vector class, and I'd like to
be able to convert between them quickly...

----Context----
The Angle class stores its value as a 8 bit integer value representing
"bygrees" (byte degrees). each "bygree" is 1/256th of a circle, with 0
starting at 12:00 going clockwise.
The Vector class stores its value as a pair of floating (double
precision) values.

If you are rounding to the nearest 256th - then just use a modified binary
search algorithm - you don't need the additional precision which comes from
atan2.

 

[Eric Sosman]

Specifically, I have an Angle class and a Vector class, and I'd like to
be able to convert between them quickly...

----Context----
The Angle class stores its value as a 8 bit integer value representing
"bygrees" (byte degrees). each "bygree" is 1/256th of a circle, with 0
starting at 12:00 going clockwise.

Long, long ago I learned of this system as "binary angular
measure," with the smallest angular increment called "one bam."
In my application, one bam was 2*pi/65536.

The Vector class stores its value as a pair of floating (double
precision) values.
>
After running it through a profiler, I've optimized the angle class to
precompute all 256 possible values, including sine, cosine, radian
conversion, etc...Good speed increase

But, now my application is bottlenecking on an Math.atan2 call,
converting a vector's direction to an Angle object.

----One solution----
I'm trying to think of ways to speed up the conversion of Vectors to
Angles, but the only way I can think to precompute this is to make a 2d
array of Angle objects. and return
angleFor[normalizeForLookup(x)][normalizeForLookup(y)]. Where
normalizeForLookup would handle rounding and bound's checking.

OR, I could use an atan lookup for int((y/x) * k) (k to be determined),
but I would have to find a suitable k, and maybe some other tricks.

On the plus side, I can determine that the largest magnetude of any
vector would be sqrt(2) * 1000, and accuracy isn't extremely important.

The downside to this would be creating an array of approximitly
4,000,000 elements. Although most of those elements point to a subset
of 256 objects, 4 megs of references is non negligible. Not to mention
the init time required.

A few random thoughts:

A few comparisons of signs and magnitudes of the vector's
X and Y components would get you to the correct octant, and a
binary search for "closest" could choose among the thirty-two
possible angles in five steps.

As above, but use an interpolation search instead of a
binary search. At a guess this might lose in complication
what it gains in step count, but maybe a hybrid strategy would
help: interpolate to find the first probe position, then go
step-by-step from there on the assumption that you won't need
to take very many steps.

What would happen if you stored rho and theta in your
vectors along with (or even instead of) X and Y? Whether this
is practical probably depends on where these vectors come from
and what gets done to/with them along the way.

 

[Mark Thornton]

Specifically, I have an Angle class and a Vector class, and I'd like to
be able to convert between them quickly...

----Context----
The Angle class stores its value as a 8 bit integer value representing
"bygrees" (byte degrees). each "bygree" is 1/256th of a circle, with 0
starting at 12:00 going clockwise.
The Vector class stores its value as a pair of floating (double
precision) values.

After running it through a profiler, I've optimized the angle class to
precompute all 256 possible values, including sine, cosine, radian
conversion, etc...Good speed increase

But, now my application is bottlenecking on an Math.atan2 call,
converting a vector's direction to an Angle object.

----One solution----
I'm trying to think of ways to speed up the conversion of Vectors to
Angles, but the only way I can think to precompute this is to make a 2d
array of Angle objects. and return
angleFor[normalizeForLookup(x)][normalizeForLookup(y)]. Where
normalizeForLookup would handle rounding and bound's checking.

OR, I could use an atan lookup for int((y/x) * k) (k to be determined),
but I would have to find a suitable k, and maybe some other tricks.

On the plus side, I can determine that the largest magnetude of any
vector would be sqrt(2) * 1000, and accuracy isn't extremely important.

The downside to this would be creating an array of approximitly
4,000,000 elements. Although most of those elements point to a subset
of 256 objects, 4 megs of references is non negligible. Not to mention
the init time required.

----Another possible solution----

So, the other alternative I see is to find a faster implementation of
atan2 (or atan), and use it in place of Math.atan2, but I wouldn't know
where to start. a quick search on google returned nothing, but I'm not
very good at finding keywords to search.

Thanks in advance,
Daniel.

In addition to Eric's suggestions, are you sure that you really need to
convert the vectors into angles? A lot of people do this unnecessarily.

Mark Thornton

 

[Martin Gregorie]

Specifically, I have an Angle class and a Vector class, and I'd like to
be able to convert between them quickly...

----Context----
The Angle class stores its value as a 8 bit integer value representing
"bygrees" (byte degrees). each "bygree" is 1/256th of a circle, with 0
starting at 12:00 going clockwise.
The Vector class stores its value as a pair of floating (double
precision) values.

After running it through a profiler, I've optimized the angle class to
precompute all 256 possible values, including sine, cosine, radian
conversion, etc...Good speed increase

But, now my application is bottlenecking on an Math.atan2 call,
converting a vector's direction to an Angle object.

----One solution----
I'm trying to think of ways to speed up the conversion of Vectors to
Angles, but the only way I can think to precompute this is to make a 2d
array of Angle objects. and return
angleFor[normalizeForLookup(x)][normalizeForLookup(y)]. Where
normalizeForLookup would handle rounding and bound's checking.

OR, I could use an atan lookup for int((y/x) * k) (k to be determined),
but I would have to find a suitable k, and maybe some other tricks.

On the plus side, I can determine that the largest magnetude of any
vector would be sqrt(2) * 1000, and accuracy isn't extremely important.

The downside to this would be creating an array of approximitly
4,000,000 elements. Although most of those elements point to a subset
of 256 objects, 4 megs of references is non negligible. Not to mention
the init time required.

----Another possible solution----

So, the other alternative I see is to find a faster implementation of
atan2 (or atan), and use it in place of Math.atan2, but I wouldn't know
where to start. a quick search on google returned nothing, but I'm not
very good at finding keywords to search.

Thanks in advance,
Daniel.

Have you looked at MathWorld:

http://mathworld.wolfram.com/

which has a large page devoted to the atan function and various ways of
calculating it.

For that matter, have you looked at Knuth, "The Art of Computer
Programming"? Volume 2 may be relevant. I don't have a copy so I can't
check whether an algorithm is given.

As a final place to look, I have dim memories of seeing fast polynomials
that can calculate trig functions in a support library for an ancient
language, PL/9, which supported the 6809 CPU and/or its successor, PLuS,
which was for 68xxx CPUs. That library will be source, and hence easily
readable, because all support code effectively included source code. I
think the trig functions may have also been published in the "'68
MicroJournal" during the early '80s. I know thats not much to go on, but
it may generate a lead.

 

[Daniel Pitts]

Specifically, I have an Angle class and a Vector class, and I'd like to
be able to convert between them quickly...

----Context----
The Angle class stores its value as a 8 bit integer value representing
"bygrees" (byte degrees). each "bygree" is 1/256th of a circle, with 0
starting at 12:00 going clockwise.

Long, long ago I learned of this system as "binary angular
measure," with the smallest angular increment called "one bam."
In my application, one bam was 2*pi/65536.

The Vector class stores its value as a pair of floating (double
precision) values.

After running it through a profiler, I've optimized the angle class to
precompute all 256 possible values, including sine, cosine, radian
conversion, etc...Good speed increase

But, now my application is bottlenecking on an Math.atan2 call,
converting a vector's direction to an Angle object.

----One solution----
I'm trying to think of ways to speed up the conversion of Vectors to
Angles, but the only way I can think to precompute this is to make a 2d
array of Angle objects. and return
angleFor[normalizeForLookup(x)][normalizeForLookup(y)]. Where
normalizeForLookup would handle rounding and bound's checking.

OR, I could use an atan lookup for int((y/x) * k) (k to be determined),
but I would have to find a suitable k, and maybe some other tricks.

On the plus side, I can determine that the largest magnetude of any
vector would be sqrt(2) * 1000, and accuracy isn't extremely important.

The downside to this would be creating an array of approximitly
4,000,000 elements. Although most of those elements point to a subset
of 256 objects, 4 megs of references is non negligible. Not to mention
the init time required.

A few random thoughts:

A few comparisons of signs and magnitudes of the vector's
X and Y components would get you to the correct octant, and a
binary search for "closest" could choose among the thirty-two
possible angles in five steps.

As above, but use an interpolation search instead of a
binary search. At a guess this might lose in complication
what it gains in step count, but maybe a hybrid strategy would
help: interpolate to find the first probe position, then go
step-by-step from there on the assumption that you won't need
to take very many steps.

What would happen if you stored rho and theta in your
vectors along with (or even instead of) X and Y? Whether this
is practical probably depends on where these vectors come from
and what gets done to/with them along the way.

First off, thanks for the replies (everyone).

The vector is often a difference of two position vectors. as in, I'm
trying to find the angle between two points in my grid.

Would a binary search really be faster? I don't know how its
implemented internally, but storing tangent in my precomputed Angle
objects would be trivial.

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.

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?

Thanks again for the suggestions, I appreciate it. If I can minimize
the amount of times atan2 is called, then my original question is
pointless, however, I will look into some sort of binary search.

- Daniel.

 

[Patricia Shanahan]

OR, I could use an atan lookup for int((y/x) * k) (k to be determined),
but I would have to find a suitable k, and maybe some other tricks.

Here's another way of getting an int from a double. It may be useful if
you have a somewhat limited range of magnitudes, but still too wide for
multiplication by a constant to yield good lookup data.

Use Double.doubleBitsToLong to get the bit pattern, and pull out a group
of bits containing the low significance exponent bits and the high
significance mantissa bits.

The exponent bits must include all possibly non-zero bits, and the total
bit pattern width has to be narrow enough for a lookup table index. That
may require some pre-conditioning.

This technique keeps a fixed number of significant bits, regardless of
the magnitude. I don't know whether it will help in your situation or not.

Patricia

 

[Daniel Pitts]

Specifically, I have an Angle class and a Vector class, and I'd like to
be able to convert between them quickly...

----Context----
The Angle class stores its value as a 8 bit integer value representing
"bygrees" (byte degrees). each "bygree" is 1/256th of a circle, with 0
starting at 12:00 going clockwise.
The Vector class stores its value as a pair of floating (double
precision) values.

After running it through a profiler, I've optimized the angle class to
precompute all 256 possible values, including sine, cosine, radian
conversion, etc...Good speed increase

But, now my application is bottlenecking on an Math.atan2 call,
converting a vector's direction to an Angle object.

----One solution----
I'm trying to think of ways to speed up the conversion of Vectors to
Angles, but the only way I can think to precompute this is to make a 2d
array of Angle objects. and return
angleFor[normalizeForLookup(x)][normalizeForLookup(y)]. Where
normalizeForLookup would handle rounding and bound's checking.

OR, I could use an atan lookup for int((y/x) * k) (k to be determined),
but I would have to find a suitable k, and maybe some other tricks.

On the plus side, I can determine that the largest magnetude of any
vector would be sqrt(2) * 1000, and accuracy isn't extremely important.

The downside to this would be creating an array of approximitly
4,000,000 elements. Although most of those elements point to a subset
of 256 objects, 4 megs of references is non negligible. Not to mention
the init time required.

----Another possible solution----

So, the other alternative I see is to find a faster implementation of
atan2 (or atan), and use it in place of Math.atan2, but I wouldn't know
where to start. a quick search on google returned nothing, but I'm not
very good at finding keywords to search.

Thanks in advance,
Daniel.

In addition to Eric's suggestions, are you sure that you really need to
convert the vectors into angles? A lot of people do this unnecessarily.

Mark Thornton

Its quite possible I don't need to, although I believe I do, please see
my reply to Erics post.
Thanks for the reply,
Daniel.

 

[Patricia Shanahan]

Daniel Pitts wrote:
....

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.

Given this problem description, I would think in terms of avoiding
calculating angles at all. Can't you turn this into a comparison of
tans, rather than of angles? Within the primary quadrant, the tan is a
monotonic increasing function of the angle, or monotonic decreasing
function of your Angle.

Note also that the dot product of two unit vectors gives a cheap
representation of the angle between them. If you only need to compare,
you can skip last step.
http://members.tripod.com/~Paul_Kirby/vector/Vdotproduct.html#findangle

Patricia

 

[Red Orchid]

----Another possible solution----

So, the other alternative I see is to find a faster implementation of
atan2 (or atan), and use it in place of Math.atan2, but I wouldn't know
where to start. a quick search on google returned nothing, but I'm not
very good at finding keywords to search.

To my thinking ...

For example,
Suppose that 0 <= Theta < PI / 2 for simplicity of this example.

Where dTheta is 1/256th of a circle,
tan(Theta) is
0, 0.0245486, ... , 40.7355

Therefore, implementation is as follows.

<code>
// Not tested


//
// Choose a proper value for your app.
//

int accuracy_factor = 100;


//
// Pre-calculation.
//

int len = accuracy_factor * 41; // 41 is 40.7355
double[] atan = new double[len];
double dTheta = 2 * Math.PI / 256;

for (int i = 0; i < (256 / 4); i++) {

double theta = i * dTheta;
double tan = Math.tan(theta);

int index = (int) (tan * accuracy_factor);
atan[index] = theta;
}


//
// Fill intermediate values.
// For example, ..
//

for (int i = 1; i < len; i++) {

if (atan == 0) {

atan = atan[i - 1];
}
}



//
// Calculation routine.
//

Where:
int x = ...;
int y = ...;

Theta is:
int m_tan = (int) (accuracy_factor * y / x);

if (m_tan < len) {

theta = atan[m_tan];
}
else {

theta = PI / 2;
}

</code>

 

[Red Orchid]

Theta is:
int m_tan = (int) (accuracy_factor * y / x);

if (m_tan < len) {

theta = atan[m_tan];
}
else {

theta = PI / 2;
}

Sorry, overflow mistake ..

<corrected>

double tan = y / x;

if (tan < 41) {

theta = atan[(int)(accuracy_factor * tan)];
}
else {
..
</corrected>

 

[Mark Thornton]

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.

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?

Thanks again for the suggestions, I appreciate it. If I can minimize
the amount of times atan2 is called, then my original question is
pointless, however, I will look into some sort of binary search.

None of that requires computing angles. You can represent a scan arc
with a pair of intersecting lines. To determine if a point is within the
arc, ask on which side of each line the point lies. Your scan arc is
then the intersection of two half planes. To find the closest, you can
skip the sqrt and just compare the squares of distances. You might find
a book on computational geometry helpful.

Mark Thornton

 

[Ken]

Here is how I would do it... but I am not ceratin if my way or Mark's
way is faster, I might figure it out by the time I finish however....
his way requires each robot to rotate 2 scanner vectors with each
robots motion... or at least generate them from the heading vector.

So to understand the problem
- you have a bunch of Robots that have a specific point: 'point'
- you have the heading of each robot as a vector: 'heading_vector'
- you have a scan arc: 'arc'

FOR(current_robot from all_the_robots)
FOR(comparison_robot from all_the_robots)
direction_vector =
makeDirectionVectorFrom(current_robot.point, comparison_robot.point)
int dot_product =
direction_vector.dot(current_robot.heading_vector)
IFthe dot_product is negative the robot is behind you so...
CONTINUE
ELSE{
angle = arc_cos(dot_product /
getMagnitude(direction_vector) * getMagnitude(heading_vector))
IF 'angle' is less than or equal to 'arc'/2
it is in the arc, remember it
END IF
}END IF
END FOR
END FOR

Now if the range of the scanner is infinite and the direction_vector
and the heading_vector are kept normalized then all you must do is:
make triangle A, B, C where side a = b = 1, and angle C = arc of
scanner, when you find side c, then the difference in vectors must
create a magnitude less than or equal to c and acr_cos can be avoided
altogether.

I must warn you that it was late when I wrote this =) hope it makes
sense to you. Remember the dot product is your friend.

 

[Eric Sosman]

[...]
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.

 

[Chris Uppal]

----One solution----
I'm trying to think of ways to speed up the conversion of Vectors to
Angles, but the only way I can think to precompute this is to make a 2d
array of Angle objects. and return
angleFor[normalizeForLookup(x)][normalizeForLookup(y)]. Where
normalizeForLookup would handle rounding and bound's checking.
[...]
The downside to this would be creating an array of approximitly
4,000,000 elements. Although most of those elements point to a subset
of 256 objects, 4 megs of references is non negligible. Not to mention
the init time required.

Besides the intelligent suggestions you've already had, I just wanted to point
out that if you rerpesent that lookup table as a byte[] array, and exploit the
symmetries, then you can reduce the space it takes very considerably.

For instance: if the arena is a 1000x1000 torus (if it wraps around at the
edges), then the difference in X values between any two points ranges from -500
to +500 (ignoring edge-effects), and the diference in Y values similarly. The
negative X and Y values can be eliminated by symmetry, so you need a 500x500
array. You can further reduce that to half its size by exploing the symmetry
around the 45 degree line, but that means you have to use a triangular array.
There are only 256 distinct values in the array so you can represent it as a
byte[] array (with a secondary lookup into an Angle[255] array). So can
compute the Angle from one robot to another with a lookup in a byte[] array
taking ~0.25 MBytes (or less if you want to be clever) -- which doesn't strike
me as unacceptable.

(BTW, when I say "symmetry" I don't mean that, say, the Angle at (-10, 10) is
/identical/ to that at (10, 10) but it can easily be computed from it.)

-- chris

 

[Ken]

Its quite possible I don't need to, although I believe I do, please see

my reply to Erics post.
Thanks for the reply,
Daniel.

Ok I woke up and I still think I made sense... lets consider the
geometry of the matter, and do it in another way.

Consider the case of two robots in the arena... R1 and R2.
R1 wants to know if R2 is in his scanning arc...
First R1 needs to know what dirrection he is facing, he may keep this
information in an angle like you are currently intent on doing or keep
this information in a dirrection vector (which would simply future
calculations and remove your bottle neck)... f you restrict yoursef to
using vectors then a vector solution will do.

So you need an accuracy of 1/256th of a circle... instead of
precomputing the trig functions why not precompute a table of
normalized direction vectors?
Please bear with me if I go slowly but by slow I hope to be clear.

Calculating your table of normalized direction vectors...
you know that sin(a) = y/r and that cos(a) = x/r
Since the lenth of the vector is to be of unit length (normalized) we
know that r = 1 thus, each vector is defined by:
y = sin(a),
x = cos(a)
where a in your case is the sequence of numbers from 0 - 2pi in 2pi/256
(in radians of course) increments best to precompute these values and
store them as an array of static final floats, i would just make even
the y component and x the cos component.

So now you have a nice table of direction vectors... the robot would
then keep an int that would index into this table
(direction_vector_int). The range of the variable is between 0 and 256
(to find the index in the precomputed direction vectors you would of
course multiply by 2 since the x and y components are side be side)...

Now to find if R2 is in R1 scanner....
The scanner has an angle too, the angle that is may sweep within...
Since the rotation of the robots in your world is restriced to changes
of 1/256 deg why not represent the angle as an int which represents x
number of 1/256 deg increments?

Say: scan_angle_ int = getScanAngleInt(int degrees); //same for all
robots right?
public int getScanAngleInt(int degrees){
return degrees * 256.0f / 360.0f
}

Now why do this? Well the scan_angle_int is the whole angle of the
scanner sweep, you know the direction vector already, well if you
divide the scan angle by two you know that half has to be on either
side of the dirrection vector of the robot, right? So half of the
scan_angle_int added or subtracted from the direction_vector _int of
the robot will give you two new vectors, these vectors are the lines
that define the range of the scanner (you dont need to keep track of
these just the direction_vector_int which will remain constant over the
duration of your program, actually as you'll see this is just an
intermediary value you will not even need to keep).

Next we need to see if the direction vector between R1 and R2 falls
between the range of the scanner... simply normalize the direction
vector between R1 and R2...

now consider this on paper so it is crystal clear:
you have your robot at the center of a circle, the radius of the circle
is 1 unit, from the robot to the diameter extends a direction vector.
Half of the scanner angle to the left is the left scanner vector bound,
half the scanner angle to the right is the right scanner angle bound
(and we know how to find these already).
Some where else there is a direction vector to another robot...
Consider now the x,y values of the direction vector, and the x,y values
of one of the sweep vector bounds... you can see that if you construct
a circle centered on the terminating position of the direction vector
with a radius extending out to the scanner bounding vectors that the
direction vector to the other robot must be inside this circle, right?

So, then find the distance between the Scanner Direction vector (the
way the robot is facing) and the bounding vectors, this is the radius
of that circle (we will call this radius the scan_radius, and it will
be constant for the duration of your program for this robot), next find
the distance from the Scanner Direction vector and the direction vector
to the other robot, if it is less than or equal to the scan_radius
then it is in the scanner sweep.

In summary, setting up your program as discribed will require you to
keep:
- the current heading of the robot (scanner_direction_vector)
- and to find a normalized direction vector to each other robot
(direction_vector)
- the scan_radius (a magic number that will tell you if the distance
between the scanner_direction_vector and the direction_vector places
the robot in the line of sight.

 

[Ken]

Its quite possible I don't need to, although I believe I do, please see
my reply to Erics post.
Thanks for the reply,
Daniel.

I agree with Mark that it is unneeded...

Ok I woke up and I still think I made sense... lets consider the
geometry of the matter.

Consider the case of two robots in the arena... R1 and R2.
R1 wants to know if R2 is in his scanning arc...
First R1 needs to know what direction he is facing, he may keep this
information in an angle like you are currently intent on doing or keep
this information in a direction vector (which would simply future
calculations and remove your bottle neck)... f you restrict yourself
to using vectors then a vector solution will do.

So you need an accuracy of 1/256th of a circle... instead of
precomputing the trig functions why not precompute a table of
normalized direction vectors?
Please bear with me if I go slowly but by slow I hope to be clear.

Calculating your table of normalized direction vectors...
you know that sin(a) = y/r and that cos(a) = x/r
Since the length of the vector is to be of unit length (normalized) we
know that r = 1 thus, each vector is defined by:
y = sin(a),
x = cos(a)
where a in your case is the sequence of numbers from 0 - 2pi in 2pi/256
(in radians of course) increments best to precompute these values and
store them as an array of static final floats, i would just make even
the y component and x the cos component.

So now you have a nice table of direction vectors... the robot would
then keep an int that would index into this table
(direction_vector_int). The range of the variable is between 0 and 256
(to find the index in the precomputed direction vectors you would of
course multiply by 2 since the x and y components are side be side)...

Now to find if R2 is in R1 scanner....
The scanner has an angle too, the angle that is may sweep within...
Since the rotation of the robots in your world is restricted to
changes of 1/256 deg why not represent the angle as an int which
represents x number of 1/256 deg increments?

Say: scan_angle_ int = getScanAngleInt(int degrees); //same for all
robots right?
public int getScanAngleInt(int degrees){
return degrees * 256.0f / 360.0f
}

Now why do this? Well the scan_angle_int is the whole angle of the
scanner sweep, you know the direction vector already, well if you
divide the scan angle by two you know that half has to be on either
side of the direction vector of the robot, right? So half of the
scan_angle_int added or subtracted from the direction_vector _int of
the robot will give you two new vectors, these vectors are the lines
that define the range of the scanner (you don't need to keep track of
these just the direction_vector_int which will remain constant over the
duration of your program, actually as you'll see this is just an
intermediary value you will not even need to keep).

Next we need to see if the direction vector between R1 and R2 falls
between the range of the scanner... simply normalize the direction
vector between R1 and R2...

now consider this on paper so it is crystal clear:
you have your robot at the center of a circle, the radius of the circle
is 1 unit, from the robot to the diameter extends a direction vector.
Half of the scanner angle to the left is the left scanner vector bound,
half the scanner angle to the right is the right scanner angle bound
(and we know how to find these already).
Some where else there is a direction vector to another robot...
Consider now the x,y values of the direction vector, and the x,y values
of one of the sweep vector bounds... you can see that if you construct
a circle centered on the terminating position of the direction vector
with a radius extending out to the scanner bounding vectors that the
direction vector to the other robot must be inside this circle, right?

So, then find the distance between the Scanner Direction vector (the
way the robot is facing) and the bounding vectors, this is the radius
of that circle (we will call this radius the scan_radius, and it will
be constant for the duration of your program for this robot), next find
the distance from the Scanner Direction vector and the direction vector
to the other robot, if it is less than or equal to the scan_radius
then it is in the scanner sweep.

In summary, setting up your program as described will require you to
keep:
- the current heading of the robot (scanner_direction_vector)
- and to find a normalized direction vector to each other robot
(direction_vector)
- the scan_radius (a magic number that will tell you if the distance
between the scanner_direction_vector and the direction_vector places
the robot in the line of sight.

 

[Ken]

Its quite possible I don't need to, although I believe I do, please see
my reply to Erics post.
Thanks for the reply,
Daniel.

Its quite possible I don't need to, although I believe I do, please see
my reply to Erics post.
Thanks for the reply,
Daniel.

I agree with Mark that it is unneeded...

Ok I woke up and I still think I made sense... lets consider the
geometry of the matter, and another way to solve it.

Consider the case of two robots in the arena... R1 and R2.
R1 wants to know if R2 is in his scanning arc...
First R1 needs to know what direction he is facing, he may keep this
information in an angle like you are currently intent on doing or keep
this information in a direction vector (which would simplify future
calculations and remove your bottle neck)... if you restrict yourself
to using vectors then a vector solution will do.

So you need an accuracy of 1/256th of a circle... instead of
precomputing the trig functions why not precompute a table of
normalized direction vectors?
Please bear with me if I go slowly but by slow I hope to be clear.

Calculating your table of normalized direction vectors...
you know that sin(a) = y/r and that cos(a) = x/r
Since the length of the vector is to be of unit length (normalized) we
know that r = 1 thus, each vector is defined by:
y = sin(a),
x = cos(a)
where a in your case is the sequence of numbers from 0 - 2pi in 2pi/256
(in radians of course) increments. It is best to precompute these
values and
store them as an array of static final floats, i would just make the
the y component the even index's and x the odd index's.

So now you have a nice table of direction vectors... the robot would
then keep an int that would index into this table
(direction_vector_int). The range of the variable is between 0 and 256
(to find the index in the precomputed direction vectors you would of
course multiply by 2 since the x and y components are side be side)...

Now to find if R2 is in R1 scanner....
The scanner has an angle too, the angle that is may sweep within...
Since the rotation of the robots in your world is restricted to
changes of 1/256 deg why not represent the angle as an int which
represents x number of 1/256 deg increments?

Say: scan_angle_ int = getScanAngleInt(int degrees); //same for all
robots right?
public int getScanAngleInt(int degrees){
return degrees * 256.0f / 360.0f

}

Now why do this? Well the scan_angle_int is the whole angle of the
scanner sweep, you know the direction vector already, well if you
divide the scan angle by two you know that half has to be on either
side of the direction vector of the robot, right? So half of the
scan_angle_int added or subtracted from the direction_vector _int of
the robot will give you two new vectors, these vectors are the lines
that define the range of the scanner (you don't need to keep track of
these just the direction_vector_int which will remain constant over the
duration of your program, actually as you'll see this is just an
intermediary value you will not even need to keep). You may wish to
note
that due to integer issues you will want to select scan angles that
result in scan_angle_int values which are evenly divisible by two
or you will loose further accuracy.

Next we need to see if the direction vector between R1 and R2 falls
between the range of the scanner... simply normalize the direction
vector between R1 and R2...

Now consider this on paper so it is crystal clear:
you have your robot at the center of a circle, the radius of the circle
is 1 unit, from the robot to the diameter extends a direction vector.
Half of the scanner angle to the left is the left scanner vector bound,
half the scanner angle to the right is the right scanner angle bound
(and we know how to find these already).
Some where else there is a direction vector to another robot...
Consider now the x,y values of the direction vector, and the x,y values
of one of the sweep vector bounds... you can see that if you construct
a circle centered on the terminating position of the direction vector
with a radius extending out to the scanner bounding vectors that the
direction vector to the other robot must be inside this circle, right?

So, then find the distance between the Scanner Direction vector (the
way the robot is facing) and the bounding vectors, this is the radius
of that circle (we will call this radius the scan_radius, and it will
be constant for the duration of your program for this robot), next find
the distance from the Scanner Direction vector and the direction vector
to the other robot, if it is less than or equal to the scan_radius
then it is in the scanner sweep.

In summary, setting up your program as described will require you to
keep:
- the current heading of the robot (scanner_direction_vector)
- and to find a normalized direction vector to each other robot
(direction_vector)
- the scan_radius (a magic number that will tell you if the distance
between the scanner_direction_vector and the direction_vector places
the robot in the line of sight.

This results in the most expensive operations being two square root
calculations when considering a robot relative to another.

Excuse me I did remove this message and reposted it.

 

[Patricia Shanahan]

Daniel Pitts wrote:
....

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.

Here's a different approach.

Your problem would be much easier if the scanning robot were at the
origin, with the right hand edge of its scan arc lying along the X axis.

Fortunately, any combination of rotation, translation, and stretching
can be applied a series of points by calculating one transformation
matrix, and multiplying each point's coordinates by it.

So, calculate a transformation matrix that puts the scanning robot at
the origin, with the right hand edge of the scan arc along the X axis.

Also you will need the slope of the left hand edge of the scan arc in
the same coordinate system, the tan of the scan angle. Call that m.
Since it is a property of the scanner, you can cache it.

Calculating these values involves trig, but it is only done once for
each scan request, and I think it is all simple forwards operations that
you already have cached.

For each other robot R:

1. Do any filtering to ignore robots that have no chance of being visible.

2. Multiply R's coordinates by the transformation matrix, getting xR and
yR, its coordinates in the scanner-centric coordinate system.

3. Robot R is visible to the scanning robot if, and only if:

xR >= 0 && yR >= 0 && m*xR >= yR

[The last test checks whether the left hand edge of the scan arc has a
greater y value than R at R's x coordinate]

4. If R is visible, calculate xR*xR + yR*yR. If R is the first robot to
pass the visibility test during this scan, or if the squared distance is
less than the best previous, record R and its squared distance as the
closest so far.

[Adjust the treatment of equality in the comparisons according to your
rules]

The work that is done for every robot for every scan contains only
multiplications, additions, and comparisons, the fastest floating point
operations. No atan2. No square root. Not even a divide.

Patricia

 

[Ken]

The work that is done for every robot for every scan contains only

multiplications, additions, and comparisons, the fastest floating point
operations. No atan2. No square root. Not even a divide.

Patricia

that is of course if you ignore the sin and cos operation needed for
the rotation matrix to align the robots direction along the x axis, to
set up this condition!