Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

OK - so I have an interesting problem I am trying to solve. 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

My question is... 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.

Thanks guys

share|improve this question
5  
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 '11 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 '11 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? –  NetConstructor.com Oct 21 '11 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 '11 at 5:13

1 Answer 1

up vote 7 down vote accepted

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)
Begin
    If (Count(P) > 2*n) then
        {R,S} = Half(P,i)
        Q = Box(R,!i,n) + Box(S,!i,n)
    Else
        Q = {P}
    Endif
    Return Q
End

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.

Example

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.

share|improve this answer
1  
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 '11 at 0:12
1  
@W did you use a lexicographical sort to facilitate the partitioning of the point coordinates? –  Dan Patterson Nov 13 '11 at 4:55
2  
@whuber this is awesome –  dassouki Nov 13 '11 at 12:34
    
@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 '11 at 2:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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