# Partitioning a data set of two-dimensional coordinates into subsets of coordinates underlying non-overlapping tiles of a bounding box

Image I have a list of coordinates of the form:

CoordinateList = {{{107.187, 130.25}, {160.742, 131.872}, {22.1312, 86.4814}}, {{251.357, 47.4634}, {177.773, 223.6}, {251.487, 126.181}}, {{51.1981, 15.1508}, {10.17, 44.4388}, {75.039, 4.44131}}, {{21.6951, 47.7368}, {73.1692, 130.974}, {93.9724, 139.979}}, {{107.914, 237.77}, {139.735, 199.392}, {20.8538, 88.0626}}, {{3.47162, 71.022}, {150.473, 45.0054}, {83.2402, 228.76}}, {{244.43, 156.011}, {126.716, 77.7305}, {247.013, 87.2547}}, {{85.3221, 108.568}, {16.3881, 167.449}, {147.638, 107.363}}, {{135.401, 97.1536}, {210.616, 104.893}, {195.791, 210.578}}, {{95.4441, 115.686}, {236.267, 69.9433}, {160.552, 30.2893}}, {{92.4965, 199.097}, {201.669, 56.4691}, {186.667, 113.938}}, {{98.7167, 45.6133}, {151.794, 88.8944}, {245.539, 177.681}}, {{103.834, 250.27}, {56.5259, 176.679}, {90.3859, 164.626}}, {{64.3762, 197.027}, {78.5971, 216.795}, {52.4567, 200.263}}, {{31.2684, 73.8046}, {12.6404, 246.689}, {3.62497, 177.448}}, {{210.712, 104.823}, {151.347, 13.8795}, {63.3472, 197.042}}, {{92.1903, 12.4941}, {141.632, 112.287}, {221.041, 189.748}}, {{237.627, 76.7537}, {20.2009, 117.81}, {150.973, 110.379}}, {{24.1639, 218.049}, {251.751, 185.44}, {161.526, 231.584}}, {{125.477, 237.408}, {38.6014, 73.5206}, {4.64447, 49.3799}}, {{80.0287, 123.736}, {153.407, 131.396}, {11.0003, 202.104}}, {{250.583, 51.9734}, {69.2102, 89.4853}, {10.0789, 163.632}}, {{96.328, 67.6535}, {210.743, 104.839}, {175.073, 114.937}}, {{136.214, 115.21}, {58.048, 144.602}, {244.051, 57.6266}}, {{60.0216, 18.7106}, {173.178, 177.361}, {87.0396, 112.919}}, {{4.67427, 49.3867}, {60.0381, 18.7024}, {77.1039, 162.763}}, {{134.911, 10.2993}, {79.7796, 61.8847}, {168.708, 104.301}}, {{200.808, 221.631}, {84.5544, 137.876}, {136.434, 150.225}}, {{110.313, 30.4609}, {37.538, 199.435}, {10.6894, 230.592}}, {{132.621, 98.0955}, {213.781, 124.4}, {21.3729, 31.0911}}};


Note that this is a list (length = 30) of subsets of coordinates.

These points fit within a bounding box of dimensions:

BoundingBox = {Min[CoordinateList[[All,1]]], Max[CoordinateList[[All,1]]], Min[CoordinateList[[All,2]]], Max[CoordinateList[[All,2]]]};


I would like to partition this box into the largest possible set of $A \times B$ rectangular tiles - the bounding box for the points can be trimmed as necessary. Call this number of tiles $k$. Then, without disturbing the ordering of the coordinate subsets, I would like to generate a list of $k$ subsets of the CoordinateList consisting of the points that fall in each rectangular region.

Here's a brief illustration (by mouse, so it's inexact!) of how I'd like to partition the points:

Here, we do the best we can to tile a bounding box for the list of points with tiles of some chosen dimension (here - roughly $A=B=50$), and then if a point falls underneath a certain tile, it is assigned to a subset for that tile. The subset must respect the primordial subsets in the original CoordinateList s.t. in each subset we can see while element of CoordinateList a point corresponds to.

Is there a nicer way to proceed than defining a coordinate list for each box, and checking for membership by a few inequality checks, or more compactly, computing a winding number using:

GraphicsMeshInPolygonQ[poly, pt]


Perhaps this could be done via the use of Pick[]? The issue I have is that my CoordinateList is actually quite a bit larger than the example provided, and I need to do this partitioning quickly.

-
Are primordial subsets in CoordinateList important? "partition this box into the largest possible set" - so the largest or set of k parts? also, is k = n^2? –  Kuba Jul 31 at 6:55
@Kuba Fixed the typo - thanks! Primordial subsets in CoordinateList are important to me, which unfortunately complicates things a bit. As for partitioning the box into $k$ parts, I mean that I choose some dimensions for a tile, and I fit as many as I can into the bounding box under the constraint that the tiles are non-overlapping. As long as the approach isn't something like random sequential addition of tiles to the bounding box, I'm ok with doing this in the manner judged to be most convenient. –  Sparse Pine Jul 31 at 6:58
You want to create a grid and pick points which belongs to each part? Schematic drawing would be helpful :) –  Kuba Jul 31 at 7:01
@Kuba Yes - hold on regarding the drawing... –  Sparse Pine Jul 31 at 7:14
Have you seen this? If that's what you're after then your question may be a duplicate. –  gpap Jul 31 at 10:03

Since it has to be a grid maybe this way:

There is some mistake in BoundingBox or I missed something because Min@CoorinatesList[[All,1]] is not the minimal x value for coordinates.

box = {Max@#, Min@#} & /@ (Flatten[CoordinatesList, 1] // Transpose)
k = 5;
div = Subtract @@@ box/k

{{251.751, 3.47162}, {250.27, 4.44131}}
{49.6559, 49.1657}

temp = # - Reverse[div] & /@ Flatten[CoordinatesList, 1];
(IntegerPart[#/div] + 1) & /@ temp

 {{2, 2}, {3, 2}, {1, 1}, {5, 1}, {3, 4}, ...


The result is a list of array indices. Notice that {1, 1} is the bottom left part. It can be easily changed if you want.

-
@SparesPine but is this what you are looking for? Maybe you do not want indices but a number from 1 to k^2 or you want to restructureize CoordinatesList at the end :) –  Kuba Jul 31 at 8:02