1
$\begingroup$

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:

enter image description here

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: 

Graphics`Mesh`InPolygonQ[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.

|improve this question
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Kuba♦ Jul 31 '13 at 6:55
  • $\begingroup$ @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. $\endgroup$ – Sparse Pine Jul 31 '13 at 6:58
  • $\begingroup$ You want to create a grid and pick points which belongs to each part? Schematic drawing would be helpful :) $\endgroup$ – Kuba♦ Jul 31 '13 at 7:01
  • $\begingroup$ @Kuba Yes - hold on regarding the drawing... $\endgroup$ – Sparse Pine Jul 31 '13 at 7:14
  • $\begingroup$ Have you seen this? If that's what you're after then your question may be a duplicate. $\endgroup$ – gpap Jul 31 '13 at 10:03
1
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ @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 :) $\endgroup$ – Kuba♦ Jul 31 '13 at 8:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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