I have a list containing over 100,000 points in lat/long format which I have imported into qgis.

Now, what I am trying to do here is group all of these points into box groups and by that I essentially mean that I want to split up the map into bounding boxes.

My requirements are are follows:

  • no boxed group should have LESS THAN 100 and NO MORE THAN 200 points
  • no point should be located in more than one group
  • all points should be be based on their nearest neighbor

How could I achieve this through qgis?

I am assuming that one can pass some custom query code and save the results or the boxes created as a shapefile correct? Could someone please explain how this could be done and what the code would look like?

As mentioned, my objective is to have a bunch of square boxes displayed as a shapefile layer where within each box there are no less than 100 properties and no more than 200.

  • 6
    To everyone who marked this question a "favorite": Why not upvote it too? One would think that your favorite question should be a good question.
    – underdark
    Oct 19, 2011 at 12:07
  • 1
    Why do you need boxing? If you create boxes based on count, they will be of different sizes anyway so tiling is out of the question. It's probably easier to group into polygons (i.e. convex hull).
    – diciu
    Oct 19, 2011 at 15:36
  • @diciu thanks for the response. Yes I guess a convex hull would be fine as I could turn those into boxes thereafter. What code would I have to use to do it using the convex hull approach? Oct 21, 2011 at 4:15
  • 2
    If you do use convex hulls your bounding boxes (enclosing the hulls) will overlap and your requirement for a point to be in a single BBOX is no longer satisfied. Convex hulls doesn't work as an intermediate step towards BBOX but rather as a replacement. And even then, creating a generic solution will be rather involved.
    – diciu
    Oct 21, 2011 at 5:13

1 Answer 1


I can get you part of the way there by assuming you have figured out how to request (a) the easternmost half of a set of points and (b) the northernmost half of a set of points. From these you can, of course, easily obtain (c) the westernmost half or (d) the southernmost half. (I don't know QGIS, but one way to do (a) in general is to request the median x-coordinate and then fetch all points whose x-coordinates exceed that. The solutions for (b) - (d) are similar.)

Using this capability, the solution is obtained with an easy recursion. To describe it, let's assume there is a procedure Half, implementing the preceding operations, which takes two arguments: the first is a set of points and the second is a code equal to true when east-west partitioning is desired and equal to false otherwise. It returns two subsets of its input which partition it as requested.

Procedure Box(P: set of points, i: boolean, n: integer)
    If (Count(P) > 2*n) then
        {R,S} = Half(P,i)
        Q = Box(R,!i,n) + Box(S,!i,n)
        Q = {P}
    Return Q

In this pseudocode, R and S partition P; Box(R,!i,n) is a partition of R in the orthogonal direction, Box(S,!i,n) is a partition of S in the orthogonal direction, "+" means form the set-theoretic union, and {} designates a set. (Alternating the splitting direction creates boxes rather than strips.) The parameter n specifies the minimum size of a group in the partition; the maximum size is 2 n.


Here, as an illustration, is a set P of 12,891 random points partitioned by Box(P,true,100) into groups between 100 and 200 in size. The algorithm creates 128 boxes of which 37 have 100 points and 91 have 101 points.

  • 2
    The algorithm is efficient. Running on a single core, it processed ten times as many points (128,910) in 18 seconds. It scales as O(n log(n) log(n)) for n points. (It could be improved to remove one of those factors of log(n), but the effort is unlikely to be worthwhile.)
    – whuber
    Nov 13, 2011 at 0:12
  • 1
    @W did you use a lexicographical sort to facilitate the partitioning of the point coordinates?
    – user681
    Nov 13, 2011 at 4:55
  • 2
    @whuber this is awesome
    – dassouki
    Nov 13, 2011 at 12:34
  • 1
    @Dan A lexical sort would help but is not necessary. Note that a median of n values can be found in O(n) time (not O(n log(n)) time), so the partitioning of points into east-west halves or north-south halves is asymptotically a O(n) computation.
    – whuber
    Nov 14, 2011 at 2:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.