1

I have a set of points in a city, each with a maximum distance radius of 0.5 - 1.5 miles. From this set of points, I'd like to create a small number of 'meeting points', i.e. locations that are central to a multiple points while not violating the constraint of <= maximum distance raidus). Those points far away from the others will have a meeting point of 1.

My first attempt was to buffer each point and find the intersection with the highest number of overlaps, but it proved very computationally expensive because I compared each new intersection with all other nearby intersections to determine the points reachable within the area.

My second attempt was to fill each buffer with possible meeting points every 100 meters & run a distance calculation on each one to determine which points they could reach, but again, computationally expensive and prone to miss edge cases.

I'm now thinking of creating a centroid of all points where at least 1 point is within radius(p1)+radius(p2) of all the other points, which would work as is, if they all had the same radius. Since the radii vary, I thought I could adjust the centroid by moving it closer to the mean of the points it doesn't reach until it either fits or not.

Am I overcomplicating this? It seems like there should be a more elegant solution, but I can't think of it. Any pointers in the right direction would be very welcomed.

  • 1
    What software are you using? The radius is a point attribute? I'm thinking the Generate Near Table tool in ArcGIS (required Advanced License) could do this. And if you don't have access to that, a distance matrix or spatial join might do as a workaround. You'd start by getting a list of all points within your maximum radius of each other. Then you could start chopping away at that list a bit - any record whose distance is greater than either max distance attribute in the record could be deleted as not a candidate. The points remaining with the most records are your best servicing points. – Chris W Feb 21 '15 at 21:43
  • Spatial Analyst might also have some tools that could work, such as Grouping. – Chris W Feb 21 '15 at 21:45
  • Yes, the radius is a point attribute. I'm just using javascript + geojson objects, so I'm more interested in the thought process. If I understand your suggestion, you're using the list of points as possible servicing points. My intent is to create new servicing points, (similar to a bunch of kids walking to an undefined school bus stop). For each point i, find all other points j where distance(i,j) <= i.radius + j.radius. Then, pick a points within that span. – Matt K Feb 21 '15 at 22:06
  • Ah, I misunderstood your first sentence - thought you wanted to select points from points. With that alteration I think your first idea is the best start. You must generate the buffers since any point has to fall within them. The computational expense I can't speak to, and I don't know how the method you're using computes things. A Union, Intersect, or spatial join operation could theoretically tell you how many buffers overlap in a given area and thus how many points are serviced by that area. But I'm thinking at a tool level where it sounds you may be working at an individual command level. – Chris W Feb 21 '15 at 22:17
  • Interesting, my finding with the intersection approach was a growing complexity. For example, Pt1_Pt2 = intersection(Pt1,Pt2). To get a 3 way intersection, Pt1_Pt2_Pt3 = intersection(Pt1_Pt2, Pt3). However, I'd also have to consider Pt1_Pt2_Pt4, Pt1_Pt3_Pt4...and you can see the problem grows following a binomial coefficient. – Matt K Feb 21 '15 at 22:34
1

For future readers, I solved this using my 2nd approach, creating a modified "fishnet" as I think it's called in GIS terms. I opted against buffers & intersects because of the "n choose k" exponential explosion of the # of intersections. More than 32 close points & I could crash a browser.

For each point, I calculated the distance to every other point. If it was less than the sum of the 2 radii, I added it to a closePoint array. Cost: O(nlog(n)) using equirectangular distance, which is SUPER cheap, only 1 cosine & 1 sqrt.

If the point had at least 1 closePoint, I started plotting points around it every 200 meters in a sunflower seed distribution (golden ratio). Cost O(n) with 2 sqrts.

For each sunflower "seed", I calculated the distance to the points in the kernel's closePoint array. If the seed reached all the points possible, I have an optimal solution & stop creating seeds for that point.

For each future point, I check to see if their optimal solution was already created & skip it if it was.

With that list, I remove the shorter intersects, leaving me with a few spots that have a bunch of intersects. For remaining overlaps, I assigned each point to the first meeting point it appears in, although optimally I'd treat this as a set cover problem to further reduce count.

Hope it helps someone who's facing this seemingly common problem!

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.