Find longest string of overlapping circles

cs75

Hi everyone, total P5.js newbie here so be gentle!

I've written a basic script (with some serious help from TheCodingTrain's youtube videos) to draw x number of circles from an array, distributed randomly in the canvas. Whenever two circles overlap they turn red.

Does anyone know how I could modify this script so that only the longest string of continuously overlapping circles is highlighted? There are always multiple discreet groups of overlapping circles which don't interact with each other. I'm trying to simulate the spread of a proximity based worm for my dissertation, so I don't need to see if there are two overlapping circles which don't link to any other circles in the array etc.

I hope that's kind of a clear explanation of what I'd like to achieve.

The script can be found at the dropbox link below.

https://www.dropbox.com/sh/6njxm1qik2nbcqo/AAB5M42mdMpufvjzl43iYmJCa?dl=0

Thanks

koogs

How many circles, roughly?

The obvious way is:

Pick one. Put it in a list. Iterate through the others, if they intersect anything in the list then add them to the list. Repeat until there's nothing more to add.

Pick another, not already in the list. Do the same with that.

Continue until everything is in a list.

But that's not going to work if you have a million circles...

cs75

Anywhere between 1000 and 4000 depending on the area I'm simulating

jeremydouglass

Do you mean "longest string" or "largest cluster"? Longest is harder.

Collision detection returns graph data -- in that a list of collisions is a list of every circle and which ones each overlaps.

The bad news -- your graph is cyclic, so longest path is NP-hard.

https://en.m.wikipedia.org/wiki/Longest_path_problem

Chrisir

I suggest instead of looking for long chains at the end of generating all circles look throughout.

You wrote: Whenever two circles overlap they turn red.....

At this point in your code when circle is a class it could hold an ArrayList of its touching circles and their number. Thus you just have to monitor the chains during setting up the circle array

After setting up you are done in knowing the longest chain

You can even monitor this when you use two variables throughout setting up your circles: maxChainLength to monitor what is currently the length of the longest chain and maxChainCircleIndex to know the index of the circle of it

jeremydouglass

@Chris -- the problem is that at each step, adding a single circle can change everything -- for example, suddenly linking a chain of 3 and 4 into a chain of 8, when the previous longest chain was 7. Plus a new circle could join multiple chains (cross shapes) or introduce cycles (venn diagram overlaps). I don't think you can save any effort by reanalyzing each step.

Chrisir

Not sure