2

I have a data set with over 1 million points. I need to find location for polygons (circle) that will maximise the number of points within it.

Requirements:

  • Radius of the circle depends on where the centre of the circle lies (different areas will have different radii)
  • Some points may have over 5000 neighbours within the circle, so solution will need to manage the size of the data (and connections found)

Assumptions:

  • If this makes analysis easier, points in one circle may not lie in another circle (i.e. circles don't overlap)
  • There are no limits on how many circles can be made

I originally tried to centre the circles on the points themselves so I can run it through a loop, but ideally I'd like to maximise the points wherever it lies.

My previous attempt included looking at number of points within radius (relationships) from each point so that I can order them DESC of density, and for the highest density remove its child points from other relationships. Then using the next biggest density and so on.. This seems very inefficient (size of the interim data became too big and slow).

I have a feeling using PostGIS or raster type solutions will be best suited for this? Can anyone please throw some light?

Improve this question
5
  • You want to find the set of non-overlapping circles defined by (x,y,r) that maximises overlap with a set of points with the additional constraint that r is a function of location. Yes?
    – Spacedman
    Commented Sep 21, 2016 at 12:30
  • Yes @Spacedman that is correct. However if it can make the problem simpler, we can relax the constraint of r being function of location. So simply, non overlapping circles that maximises points in it.
    – user82635
    Commented Sep 21, 2016 at 13:29
  • - with a given, fixed radius, yes? Otherwise one circle of radius 100000000 might cover all of them!
    – Spacedman
    Commented Sep 21, 2016 at 14:36
  • Yes with a defined/fixed radius.
    – user82635
    Commented Sep 21, 2016 at 14:46
  • For a fixed radius a simple hexagonal lattice of circles will cover about 90% of the space. So that gives you a benchmark of spatial coverage that might give you 90% point coverage. There's still 3 degrees of freedom with this (x-y translation and rotation) so you could optimise over those and maybe do better....
    – Spacedman
    Commented Sep 21, 2016 at 18:11

1 Answer 1

Reset to default
1

I tested @Spacedman idea, by randomly placing 100 points inside different size circles. I placed hexagons, so that distance between their centres equals to (average radius of circles)*2. Two most crowded hexagons in the picture below are labelled by count of points and smallest of circles is selected.

hexagons

As one can see his approach produces a good estimate of highest density location.

I also tested technique described here where the criteria is count of points inside the group, 100 in this case:

catchments

The group with minimum average distance to their centre is the target. Not sure if this helps, moreover there are complications to overcome for million of points.

NOTE:

I tried raster approach in ArcGIS, using focal statistics /circle, radius= (average radius of circles)/, which is what you truly need, but had to kill the process, it was not going to end with such a big radius. Perhaps working with the larger cell size, will do a trick, but you’ll need a workaround to count points inside same cell.

However the fastest result was produced by using Kernel Density Tool. Picture below shows "topography of result and a peak: enter image description here

Improve this answer
3
  • Could you please elaborate on the kernel density approach? I couldn't replicate this on my data set. Just to clarify -- I have a fixed circle radius, and need to maximise points that lie within it. I can limit the number of circles if that simplifies the problem.
    – user82635
    Commented Sep 26, 2016 at 18:12
  • pro.arcgis.com/en/pro-app/tool-reference/spatial-analyst/… i.e. you have to iterate 1,000,000 times over your points. However the best way forward is 1st approach and kernel on reduced dataset
    – FelixIP
    Commented Sep 26, 2016 at 19:18
  • Would you please be able to point in the right direction to achieve 1)?
    – user82635
    Commented Sep 27, 2016 at 8:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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