Quadtree bulk loading point

Question

I applied the group loading method of the dot quadrant. But for some inputs, this does not work correctly, for example, if there are many points that have the same x or y coordinate. Sample data set:

test = [(3, 1), (16, 1), (11, 4), (5, 4), (9, 6), (5, 10), (1, 15), (11, 5), (11, 15), (12, 16), (19, 17)] tree = create(test) 

The problem arises at the points: (11,4),(11,5),(11,15) and (5,10),(5,4) .

This is the create function:

 def create(point_list, presorted=False): if not point_list: return QuadNode() if not presorted: point_list.sort(key=lambda p: [p[0],p[1]]) median = len(point_list) >> 1 relevantPoint = point_list[median] relevantYCoordinate = relevantPoint[1] node = QuadNode(data=relevantPoint) leftBins = point_list[:median] rightBins = point_list[median + 1:] nwBins = [bin for bin in leftBins if bin[1] >= relevantYCoordinate] swBins = [bin for bin in leftBins if bin[1] < relevantYCoordinate] neBins = [bin for bin in rightBins if bin[1] >= relevantYCoordinate] seBins = [bin for bin in rightBins if bin[1] < relevantYCoordinate] node.nwNode = create(nwBins, presorted=True) node.swNode = create(swBins, presorted=True) node.neNode = create(neBins, presorted=True) node.seNode = create(seBins, presorted=True) return node 

and QuadNode :

 class QuadNode(object): def __init__(self, data=None, nwNode=None, neNode=None, swNode=None, seNode=None): self.data = data self.nwNode = nwNode self.neNode = neNode self.swNode = swNode self.seNode = seNode 

I want to follow the rule for insert, delete, etc .:

• swNode point.x < parent.x and point.y < parent.y
• seNode point.x >= parent.x and point.y < parent.y
• nwNode point.x < parent.x and point.y >= parent.y
• neNode point.x >= parent.x and point.y >= parent.y

Answer 1

Your method of choosing the middle is the right one (as explained in the Finkel source article of Quadtris: data structure for extracting on composite keys), but the way to create subcategories for subtrees is incorrect.

For example, in this sorted list:

[(1, 1), (1, 2), (1, 3)]

median 1, 2 and, given your boundary rules, 1,1 should be in SE and 1,3 in NE.
In the original article, SE and NW are “open” and NW and SE are closed: 1,1 is in NW and 1,3 in SE. As you can see with this definition of boundaries, all elements before the median will be in SE or NW, and all elements after the median will be in SW or NE. But this does not meet the definition of boundaries.

So, there is something wrong with defining your boundaries, or you should check each element of the list to make sure that it falls into the right area. For eaxmple:

 relevantPoint = point_list[median] node = QuadNode(data=relevantPoint) del point_list[median] nwBins = [(x,y) for x,y in point_list if x < relevantPoint[0] and y >= relevantPoint[1]] swBins = [(x,y) for x,y in point_list if x < relevantPoint[0] and y < relevantPoint[1]] seBins = [(x,y) for x,y in point_list if x >= relevantPoint[0] and y <= relevantPoint[1]] neBins = [(x,y) for x,y in point_list if x <= relevantPoint[0] and y > relevantPoint[1]] 

However, this is rather ugly and does not guarantee that the tree will be balanced. I would rather check the definition of boundaries ....