<div dir="ltr"><span style="font-family:arial,sans-serif;font-size:13px">I can't help much, though I'd be interested to know if you find a solution to this.</span><div style="font-family:arial,sans-serif;font-size:13px">
<br></div><div style="font-family:arial,sans-serif;font-size:13px">With only 100 points you may be able to solve it by brute force, at least near-enough.</div><div style="font-family:arial,sans-serif;font-size:13px"><br></div>
<div style="font-family:arial,sans-serif;font-size:13px">If you can visually identify 10 "clusters" of points in the dataset, consider using a clustering algorithm. The difficult part is forcing them to all be 10 points; most clustering algorithms I've seen will give you 10 clusters, but won't guarantee anything about the size of each cluster.</div>
<div style="font-family:arial,sans-serif;font-size:13px"><br></div><div style="font-family:arial,sans-serif;font-size:13px">We had a similar problem with a much, much larger dataset (~30 million points.) where the objective was simply to divide the points spatially into N equal buckets. We ended up using a clustering algorithm (<a href="https://github.com/craigds/pygvm" target="_blank">GVM</a>, to be specific) followed by a re-balancing step (pushing points out of each cluster into the nearest other cluster until all clusters contained the same number of points).</div>
<div style="font-family:arial,sans-serif;font-size:13px"><br></div><div style="font-family:arial,sans-serif;font-size:13px">It wasn't the best solution. Clustering algorithms generally try to match clumps of points into the same bucket. Here we were trying to divide the dataset into chunks with equal numbers of members, rather than divide the dataset into clusters. So using a clustering algorithm isn't really the right approach. Certain datasets ended up with some clusters much larger than other clusters.</div>
<div style="font-family:arial,sans-serif;font-size:13px"><br></div><div style="font-family:arial,sans-serif;font-size:13px">In one case we built 4 clusters from millions of points, and 3 of the clusters just had 1 point because there were three points on islands, far from the rest of the points on the mainland. Then we had to run a rebalancing step for hours/days afterwards to push most of the points into the smaller clusters.</div>
<div style="font-family:arial,sans-serif;font-size:13px"><br></div><div style="font-family:arial,sans-serif;font-size:13px">We haven't been able to find a better solution thus far; it's on the TODO list but if anyone does have suggestions we'd be interested in hearing them.</div>
<div style="font-family:arial,sans-serif;font-size:13px"><span class=""><font color="#888888"><div class="gmail_extra"><br></div><div class="gmail_extra"><br class="">Craig de Stigter</div><div class="gmail_extra">Software Engineer</div>
</font></span><div class="gmail_extra"><span class=""><font color="#888888">Koordinates</font></span></div></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">On Mon, Nov 11, 2013 at 2:50 PM, BladeOfLight16 <span dir="ltr"><<a href="mailto:bladeoflight16@gmail.com" target="_blank">bladeoflight16@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div class="im">On Sun, Nov 10, 2013 at 8:25 AM, Carsten Hogertz <span dir="ltr"><<a href="mailto:carsten.hogertz@gmail.com" target="_blank">carsten.hogertz@gmail.com</a>></span> wrote:<br>


<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hello,<br>
<br>
I've got the following task to solve:<br>
<br>
There's a table containing a set of 100 site points spread over a city.<br>
These 100 points have to be visited 10 groups where each group has to visit 10 sites.<br>
<br>
My question is how can I divide this 100 points into 10 groups where the points of each group are grouped by nearest distance?<br></blockquote><div><br></div></div><div>You're trying to find groups of 10 where you minimize distance between all points in each group. I suspect it's an NP-hard problem. I seem to recall a similar problem being NP-hard, although I couldn't identify it off-hand. You might be able to glean something by looking into other NP-hard problems. In these class of problems, something you need to determine is what constitutes "good enough." Unless you can find an existing solution to a similar problem, your best bet is to accept a suboptimal solution that provides "good enough" results.<br>


<br></div><div>If you're willing to accept near-optimal results instead of truly optimal, I have an idea you could try out. Take the bounding box of all the points. Then use a binary-search-like algorithm to find a vertical or horizontal line that splits the box into two boxes each containing 50 points. (By "binary-search-like", I mean start with the center line, and then check how many points each box contains, and then move your line into the half that contains more points. Keep doing this until you find a line that works.) Then do something similar that splits the new divided boxes into 2 more boxes where one contains 10*CEIL((n/10)/2). (That's the multiple of 10 nearest to half the number of points the box contains.) Keep doing that until you end up with a set of boxes that contain 10 points.<br>


<br></div><div>There are a couple of details to worry about here. You'll have to worry about having a bunch of points being colinear with your dividing line. That could pose a problem finding a good dividing line. You should also have something in place to choose whether to use a horizontal or vertical line. My first guess about doing that would be to use horizontal if the box is taller than it is wide; otherwise, use vertical. That would keep you from ending up with a bunch of really thin and long boxes. There's probably other issues that haven't occurred to me, too.<br>


</div><div><br></div><div>Basically, this is gonna be tough to work out. Good luck.<br></div></div></div></div>
<br>_______________________________________________<br>
postgis-users mailing list<br>
<a href="mailto:postgis-users@lists.osgeo.org">postgis-users@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users" target="_blank">http://lists.osgeo.org/cgi-bin/mailman/listinfo/postgis-users</a><br></blockquote></div><br></div>