Find Denser Areas

Replies to This Discussion

Permalink Reply by David Rutten on June 6, 2017 at 5:26pm

I'm afraid even your current approach will not necessarily give you the correct answer. Even if your area is a fixed sized circle, there's no guarantee that the circle will be centred on one of the points, it may well be in between two points.

If you don't care that much about accuracy, you could divide up your area into a coarser grid of -say- a couple of hundred circle centre points. That will reduce the number of branches. Another possibility is to use Galapagos to find such a circle, but there's no mathematical guarantee that you'll actually end up with the best solution.

If you can upload some of your data (or made up data if you're not allowed to share what you have) I can try and come up with a Galapagos approach.

I do think that if your point density and integer values conspire to counter-act each other you may be in for a rough ride though. In the end some sort of hard core brute force approach may be your only option. If push comes to shove though you can always resort to some C# scripting, which would at least allow you to immediately discard bad areas without having to accumulate them all into memory.

Permalink Reply by David Rutten on June 7, 2017 at 1:32pm

Galapagos is not a good tool to try and find the N best solutions. Still, it's probably the easiest place to start.

I do not know what "the code must be able to listen to completion and only transmit" means.

Permalink Reply by David Rutten on June 7, 2017 at 1:58pm

I rescaled the point coordinates to a more sensible numeric range (the coordinates are now only a thousandth of what they used to be, and moved on top of the origin). Computers in general do not like dealing with huge numbers. Integer math tends to overflow and floating point math tends to be a lot less accurate far away from zero.

The attached file uses Galapagos to try and find the densest circle with a fixed radius. I do not believe that this approach can be easily extended to instead find the N densest circles including a separation constraint.

Attachments:

• FindDensestCircle_Galapagos.gh, 449 KB

Permalink Reply by David Rutten on June 8, 2017 at 12:39pm

Here's a C# script that does it all. It is rather complicated, and to be honest I did not test it very intensely. Also, I'm not quite sure how to figure out whether the results are correct.

The script outputs the most dense H circles (plus associated total weights) in the order (densest to least dense). It does not include any circles which would overlap with a denser circle. It does not (yet) take in an additional collision factor into account, at the moment it's just pure circle/circle overlap, not with an additional radius factor.

It's not exactly fast since the circle inclusion/exclusion computation is completely brute force. There's room to speed that up though using a search tree (even more complicated code).

Let me know if this is something worth exploring further.

Attachments:

• FindDensestCircle_CS.gh, 441 KB

Permalink Reply by David Rutten on June 8, 2017 at 12:43pm

Oh to explain, the Accuracy input specifies how far apart adjacent circles are sampled. Up this number and the time to completion for this algorithm goes down by the square of that increased accuracy. So, careful, use the highest number here (i.e. lowest accuracy) you're willing to settle for to keep things spiffy.

The Hits input is not particularly time sensitive, a large number here will not retard the script too severely.