Closest point which is within an pie-slice (2d).
Daniel Pitts
seem to have this kind of knowledge ;-)
I have a simulation where once in a while, I need to find the closest
object within a particular arc. For example:
-----------------
| |
| _,.-.,_ |
| \ o o / x |
| \* / |
| x \ / |
| v x |
| x |
-----------------
where "o" are misses (because they aren't the closest) and "x" are
misses because they are outside the arc. "*" is the hit, because it is
the closest within the arc.
I don't have any kind of tree, although sometime in the future I may
implement one.
I have a working algorithm, but I'm not convinced its the best. Are
there any easy way to improve this?
My current algorithm is:
/* the pie slice were looking at is defined by a position (center), an
angleBracket (range of angles), and a maxDistance (radius) */
ScanResult calculateResult(Position position,
AngleBracket angleBracket,
double maxDistance) {
final double maxDistanceSquared = maxDistance * maxDistance;
Vector vectorToClosest = null;
double closestDistanceSquared = maxDistanceSquared;
Thing closest = null;
for (Thing thing : allThings) {
final Vector vector = thing.getPosition().getVectorTo(position);
final double distanceSquared = vector.getMagnitudeSquared();
if (distanceSquared < closestDistanceSquared) {
if (angleBracket.contains(vector.getAngle())) {
closest = thing;
closestDistanceSquared = distanceSquared;
vectorToClosest = vector;
}
}
}
return new ScanResult(vectorToClosest,
Math.sqrt(closestDistanceSquared),
closest) ;
}
Thanks,
Daniel.
--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
Kaba
> This isn't *exactly* a graphics question, but regulars of this group
> seem to have this kind of knowledge ;-)
>
> I have a simulation where once in a while, I need to find the closest
> object within a particular arc. For example:
>
> -----------------
> | |
> | _,.-.,_ |
> | \ o o / x |
> | \* / |
> | x \ / |
> | v x |
> | x |
> -----------------
> where "o" are misses (because they aren't the closest) and "x" are
> misses because they are outside the arc. "*" is the hit, because it is
> the closest within the arc.
>
> I don't have any kind of tree, although sometime in the future I may
> implement one.
>
> I have a working algorithm, but I'm not convinced its the best. Are
> there any easy way to improve this?
Hi Daniel,
the algorithm you outline is similar to a linear search through the
points. It probably can be improved: this just requires that there are
enough points so that a more advanced search can outperform a
straighforward solution. Profiling will show.
Important questions are:
- How many points do you have?
- Is the same point-set searched multiple times or just once?
- Is your point-set changing w.r.t. time? If yes, how?
Let us assume that you have lots of those points. Then the fastest
solution that I can think of is to use a point kd-tree to store the
points and do nearest neighbor searching using it. Your shape is only a
part of sphere (a spherical cone). This could help further if you
modified the search algorithm rather than just filtered the points found
from a full sphere search. But even if you did the latter you should
improve performance dramatically.
Note that the problem and the solution are trivially extended to
arbitrary dimensions (you could also generalize your current solution to
work with any dimension).
If your point-set changes w.r.t. time, I might have a different solution
to your problem (a somewhat different kd-tree), but this depends on the
way the point-set changes.
Happy new year:)
Daniel Pitts
> - Is the same point-set searched multiple times or just once?
> - Is your point-set changing w.r.t. time? If yes, how?
robots, which can move.
>
> Let us assume that you have lots of those points. Then the fastest
> solution that I can think of is to use a point kd-tree to store the
> points and do nearest neighbor searching using it. Your shape is only a
> part of sphere (a spherical cone). This could help further if you
> modified the search algorithm rather than just filtered the points found
> from a full sphere search. But even if you did the latter you should
> improve performance dramatically.
>
> Note that the problem and the solution are trivially extended to
> arbitrary dimensions (you could also generalize your current solution to
> work with any dimension).
>
> If your point-set changes w.r.t. time, I might have a different solution
> to your problem (a somewhat different kd-tree), but this depends on the
> way the point-set changes.
use-cases should probably be accounted for:
* "Scanning" (the use-case above)
* "Nearest Neighbor" (finding the nearest robot,
regardless of direction)
* "Collision" Finding a whether a robot collides with:
* Another robot. (2-50 robots)
* A "mine" (0-300 mines)
* A "missile" (0-300 missiles)
* "All within circle" (finding all robots within a radius
of an explosion)
Missiles, Mines, and Robots can only collide with one Robot. For the
sake of collisions, mines have a radius, where the center of the robot
must be within that radius to detonate. Robots colliding with other
robots are treated like two solid circles of a specific radius. Missiles
(moving line segments) will detonate when they intersect the line
perpendicular to there direction of travel which goes through the center
of the robot, if it is within a particular distance of that robot.
Robots and Missiles can also both collide with the bounding wall.
Mines are stationary, and missiles move fairly quickly (compared to
robots).
Oh, and the typical set-up is on an arena which is considered to be
1000x1000 meters. The robots and other objects are nearly as likely to
exist at all points equally (there may be some biases, but I don't think
they're worth worrying about). Given that, I'm thinking it might be
worth setting up a static kd-tree at start-up. I have never implemented
nor used a kd-tree before, so I'm not sure the best approach.
>
> Happy new year:)
Happy New Year to you too!
Thanks
Hans-Bernhard Bröker
> I have a simulation where once in a while, I need to find the closest
> object within a particular arc.
You seem to have forgotten one crucial aspect: closest to ... _what_?
Kaba
> Oh, and the typical set-up is on an arena which is considered to be
> 1000x1000 meters. The robots and other objects are nearly as likely to
> exist at all points equally (there may be some biases, but I don't think
> they're worth worrying about). Given that, I'm thinking it might be
> worth setting up a static kd-tree at start-up. I have never implemented
> nor used a kd-tree before, so I'm not sure the best approach.
> >
> > Happy new year:)
>
> Happy New Year to you too!
>
> Thanks
> Daniel.
Given this extra information, I'd change the strategy to using a simple
grid instead. This is because you have a lot of dynamic action. For each
time-step you run an update step for those objects which move, removing
an object from the grid and then re-inserting it. The point being: you
probably have an upper bound to the grid resolution you need, so it
shouldn't happen that a lot of stuff is concentrated in a single grid
cell. Implementing nn-searches etc. for a grid is easy.
For the other kind of a kd-tree I mentioned it requires a different kind
of definition for a time-changing point-set. Namely, that:
1) There is a (finite) set of all possible points P which can exist and
at a given time instant a subset S of P is stored in the tree.
2) There is coherence in the way the subsets change over the time steps.
..Such a point-set is called a semi-dynamic point-set.
Daniel Pitts
specific one :-) Closest to the vertex. I would have thought the
diagram would have helped reduce the ambiguity.
Anyway, Kaba has given me a lot of good suggestions.
Hans-Bernhard Bröker
> That's what I get for trying to make a generic question out of a
> specific one :-) Closest to the vertex. I would have thought the
> diagram would have helped reduce the ambiguity.
Not really. Three example points don't really make a stringent definition.
So it's basically just a normal nearest-neighbor problem, with the
little twist that all solutions are required to lie to the left of one
straight line, and to the right of another. That would mean just about
all the usual algorithms will still work without major structural
modifications.