postgis - Nearest Neighbor Grouped Selection in QGIS

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.

Answer

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.

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.