Tacet.Discipulus
Tacet.Discipulus

Reputation: 1

How to define the boundary conditions of a rectangle being used in a quadtree to hold points in R^2

I am trying to implement a quadtree to store points in R2. My project requires a square centered at (0,0) with side lengths l, so the quadtree must be able to store all points in the closed rectangle [ -l , l ] x [ -l , l ].

I have read the implementations of a few quadtrees used for similar purposes and I am having trouble understanding how to implement the quadtree so that all points that lie on the boundary of the square are can be stored (points inside the boundaries i have no trouble with).

As I understand there should be only one implementation for a node, so the NE, NW, SW, and SE nodes are all instantiations of the same class. So that there is no ambiguity to which quadrant a point properly belongs half open intervals must be used. So a quadrant with boundaries [ -w , w ) x ( -h , h ] gets subdivided into [ 0 , w ) x ( 0 , h ] , [ -w , 0 ) x ( 0 , h ] , [ -w , 0 ) x ( -h , 0 ] , [ 0 , w ) x ( -h , 0 ] . This makes perfect mathematical sense, the original set (quadrant) has been subdivided into four disjoint sets (quadrants) and there is no ambiguity as to which subset (quadrant) a point properly belongs. Now every node and subnode contain their north and west boundaries but do not include their south and east boundaries as they are contained in a neighboring node.

If however quadrants are subdivided using closed intervals instead of half open intervals it becomes ambiguous to which quadrant points that lie on the boundaries between them properly belong.

So i can implement a quadtree to store all points in [ -l , l ) x ( -l , l ] with no problem. This however means I cannot store points that lie on the south and east boundaries as they are not included when using half open intervals.

Am I failing to understand how to subdivide a quadrant into four subquadrants? Is there a way that I can include points that lie on the south and east boundaries of my initial square?

I am using C# right now but I am open to moving to C++ if anyone can point me to an implementation I can read that solves my problem.

Thanks

EDIT: I am editing this to give a more concrete example of my problem in response to Matt Timmermans comment. I really am trying not be repeat myself and beat a dead horse.

Assume I have a class Rectangle that is used in the class QuadtreeNode that has a method Bool Contatins(double x, double y) (x and y are normal Cartesian coordinates) to determine if ( x , y ) is contained in the rectangle. In order for this to work I am forced to decide which quadrant a point that lies on a boundary must belong, I have decided that a rectangle will include all interior points and include its North and West boundaries, leaving the South and East boundaries to be included in the appropriate neighboring quadrants. So Contains(double x, double y) looks like

Bool Contains(double x, double y) {
    if( (X_min <= x < X_max) && (Y_min <= y < Y_max) ) {
        return true;
    }
    return false;
}

The above check works perfectly for bounds checking any Rectangle created when a quadrant also defined with half open intervals is subdivided into four subquadrants each containing a instance of Rectangle with appropriately calculated X_min, X_max, Y_min, and Y_max. My Problem however is that by making the binary choice as to which quadrant a point that lies on a boundary belongs means that any node with a Rectangle that shares a South or East boundary with my initial Rectangle defined by [ -l , l ] x [ -l , l ] do not include their South or East borders, thus the initial Rectangle cannot include its South or East borders as that Rectangle is the union of the subrecctangles defined with half open intervals.

The rectangle [ -l , l ] x [ -l , l ] is a closed and bounded (compact) set, when subdividing into subquadrants (subsets) as above, the subrectangles are defined by half open intervals and thus not compact. The desire for every rectangle be an instantiation of the same Rectangle class where NE, NW, SE, and SW are not individually subclassed (I don't even fully see if could resolve this) requires this. So essentially I am attempting to use a finite subcover to cover a compact set that by the way the subset boundaries are defined cannot actually be a finite subcover.

Am I being overly concerned with the my mathematical desire for the subquadrants to be disjoint sets? What if all Rectangles contained their boundaries and a point lying on a boundary is simply added to the first subquadrant that can contain it. I can do this by changing the above Contains(double x, double y) to

Bool Contains(double x, double y) {
    if( (X_min <= x <= X_max) && (Y_min <= y <= Y_max) ) {
        return true;
    }
    return false;
}

Apologies in advance if I'm repeated myself needlessly, I am just trying to be a concrete as possible. I suspect my desire for tidy set-theory notions is causing a mental block here and causing me to grossly overthink this.

Thanks

Upvotes: 0

Views: 151

Answers (0)

Related Questions