One possible solution to implement Picking: 2D trees
Most Computer Aided Design applications (like Microsoft Office Visio 2003) present users with a design surface where various objects can be dragged and dropped. When the user clicks on the graphical of an object on the screen, the application has to locate the internal representation of the object that was clicked knowing only the (x, y) coordinates of the mouse pointer at the time of the click. This process is also known as “Picking”.
Picking can be seen as a special case of a more general problem: Range searching. Assuming we have a set of records with certain attributes, a range searching algorithm finds all the records satisfying specified range restrictions on a specified set of attributes. This is an important and complex problem.
Most of the time, range searching algorithms split problems into two phases: a preprocessing phase where adequate data structures are built and a searching phase where the aforementioned data structures are searched for matching records.
To simplify this post, we will assume that we have a set of points in the plane (these are our records) and the attributes are the coordinates of the points (x, y). We are trying to answer the following question: given a rectangle rect, what are the points that are inside this rectangle?
A brute force solution would be to test every single point against the rectangle’s coordinate. However, this method is sub-optimal since it performs a lot of un-needed comparisons. It turns out that we can solve this problem in a better way by using two-dimensional trees. Those trees are very similar to binary search trees but divide up the geometric space in a manner that is convenient for range searching.
A 2D binary tree is built almost like a binary search tree. The only difference is that we use the y and x coordinates of the points as keys in a strictly alternating sequence. At the root, we use the y coordinate (if the point to be inserted as a smaller y coordinate than the point at the current node, go left otherwise go right). At the next level we use x as the key. Basically, we start by using y as the key for the root and alternate between y and x for every level in the tree.
At the root, we divide the plane in two regions: the region of all the points below the point at the root on the left and all those above go on the right subtree then all the points above the point at the root and to the left of the point in the right subtree go in the left subtree of the right subtree of the root. The process goes on recursively and it creates vertical and horizontal dividing lines. An horizontal diving line is created at level y for all points above coordinate y and a vertical dividing line is created at level x for all the points on the right of a given value x. With this technique, we can quickly eliminate a lot of points from the possible set of points to test.
The search phase takes advantage of the previously built 2D tree. We test the point at each node against the range along the dimension used to divide the plane for that node. There is one interesting special case: searching should be allowed to analyze both subtrees (right and left) if a dividing line cuts the rectangle being considered. Note that the searching code and the tree construction code should be synchronized: the search code should not be able to look for x coordinates at a level where the tree was built using y as a key.
Now, here is my implementation. Each node in the tree will be represented by the node class below. The class holds a reference to the right and left child and the point coordinates. This is pretty standard:
class Node
{
private Point point;
private Node left;
private Node right;
/// <summary>
/// Construct a node with the given point.
/// </summary>
/// <param name="p">Point.</param>
public Node(Point p)
{
Point = p;
}
/// <summary>
/// Get/Set the point associated with the node.
/// </summary>
/// <value></value>
public Point Point
{
get { return point; }
set { point = value; }
}
/// <summary>
/// Get/Set the right child of this node.
/// </summary>
/// <value>Node.</value>
public Node Right
{
get { return right; }
set { right = value; }
}
/// <summary>
/// Get/Set the left child of this node.
/// </summary>
/// <value></value>
public Node Left
{
get { return left; }
set { left = value; }
}
}
Our 2D trees are implemented by the following Tree2D class. The class maintains one private member rootNode which is the root of the tree. The constructor is pretty straightforward: it simply inserts all the points into the tree.
The Insert and Pick method implement the algorithm as previously described. Pick simply adds any matching point to the end of an ArrayList.
class Tree2D
{
/// <summary>
/// Root node of the 2D tree.
/// </summary>
private Node rootNode = null;
/// <summary>
/// Constructor with an array of points.
/// </summary>
/// <param name="points">
/// Array of points to insert into the tree.
/// </param>
public Tree2D(Point[] points)
{
if (points != null)
{
foreach (Point p in points)
Insert(p);
}
}
/// <summary>
/// Inserts a point into the 2D tree.
/// </summary>
/// <param name="p">Point to insert.</param>
public void Insert(Point p)
{
Node current = rootNode;
Node previous = null;
bool useX = false;
bool useLeftSubtree = false;
while (current != null)
{
// Should we explore the right subtree or the left subtree ?
useLeftSubtree = useX ? (p.X < current.Point.X) : (p.Y < current.Point.Y);
previous = current;
current = useLeftSubtree ? current.Left : current.Right;
useX = !useX;
}
// Insert the node
if (rootNode == null)
rootNode = new Node(p);
else
{
if (useLeftSubtree)
previous.Left = new Node(p);
else
previous.Right = new Node(p);
}
}
/// <summary>
/// Get the set of points which are in the given rectangle.
/// </summary>
/// <param name="rect">Rectangle to test points against.</param>
/// <returns>ArrayList of points within that rectangle if any, null if none.</returns>
public ArrayList Pick(Rectangle rect)
{
ArrayList pointsFound = new ArrayList();
RecursivePick(rootNode, rect, false, pointsFound);
return pointsFound;
}
/// <summary>
/// Traverses the 2D tree to find which points are in the given rectangle.
/// </summary>
/// <param name="rootNode">Root node of the tree to observe.</param>
/// <param name="rect">Rectangle to test points against.</param>
/// <param name="useX">
/// true if we should use the X coordinate at this level or the Y coordinate.
/// </param>
/// <param name="pointsFound">ArrayList collecting all the points found.</param>
private void RecursivePick(Node rootNode, Rectangle rect, bool useX, ArrayList pointsFound)
{
if (rootNode == null)
return;
// Should we analyze the left subtree and/or the right subtree ?
bool analyzeLeftSubTree = useX ? (rect.Left < rootNode.Point.X) :
(rect.Top < rootNode.Point.Y);
bool analyzeRightSubTree = useX ? (rootNode.Point.X <= rect.Right) :
(rootNode.Point.Y <= rect.Bottom);
// Analyze the left subtree
if (analyzeLeftSubTree)
RecursivePick(rootNode.Left, rect, !useX, pointsFound);
// If the point is inside the rectangle, add it to the result list
if (rect.Contains(rootNode.Point))
pointsFound.Add(rootNode.Point);
// Analyze the right subtree
if (analyzeRightSubTree)
RecursivePick(rootNode.Right, rect, !useX, pointsFound);
}
}
The previous class can be used with some equivalent of the following code, where points is an array of Point and pickRadius is the tolerance of picking (i.e. the region around the mouse pointer that is considered large enough to match a point and makes picking easier to use for the user).
Tree2D tree2D = new Tree2D(points);
ArrayList pointsFound = tree2D.Pick(new Rectangle(e.X - pickRadius,
e.Y - pickRadius,
2 * pickRadius,
2 * pickRadius));
By inspecting the algorithm, it is possible to see that the construction of a 2D tree with N random points takes 2N ln N comparisons on average. Range searching with a 2D tree seems to take about R + log N to find R points in reasonable ranges in a region containing N points. However, I have not analyzed precisely the complexity of search yet so I may be wrong. Any feedback is greatly appreciated. Observe that this method is optimized for situations where the number of points found R is relatively small.
It is possible to extend this method to three (or more) dimensions in a straightforward way: simply cycle through dimensions like we did for x and y while going down the tree.
Comments
- Anonymous
June 06, 2004
Your tree is called a kD tree, and is very hard to balance.
Another solution, assuming you are working with integeres, is to interleave the bits of your x and y values, and insert the resulting value into a normal, possibly balanced, 1D tree.
You can then range search on the resulting tree by interleaving your upper-left point and your lower-right point. - Anonymous
June 07, 2004
The comment has been removed - Anonymous
June 07, 2004
This is great feedback. Thanks!
Yes, balancing should be taken into account here, I totally agree.
Michael:
I was considering the simple problem of picking points and it is indeed true that real world CAD applications deal with shapes that are more complex points.
As far as adding points one at the time goes, yes, it does not guarantee any kind of balance, I totally agree.
However, it seems that rebuilding the whole tree every time a new point is created by a user may have performance consequences. This approach may or may not be worth it in practice (i.e. the time to rebuild the tree might be equal or larger than just paying for a search in the unbalanced tree). I would prefer a "balance on insertion/deletion" kind of approach if possible since this seems to match the use patern a little better: users add/remove points incrementally. However, such an algorithm may be more expensive to run than to just rebuild the tree.
One possible way to alleviate balancing issues can be to always use the dimension that best divide the space instead of cycling through the dimensions. This approach is not perfect since it requires to quickly decide which dimension best divides the space and assumes that we can come up with a reasonably efficient algorithm for this. I have not found such an algorithm.
I have not yet read the references you mention but I will as soon as possible. - Anonymous
June 07, 2004
The comment has been removed