Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Agile forum!

# Different Colour for different group of overlapping circles.

Rose Jac
Ranch Hand
Posts: 33
HI.
I have displayed circles on a JPanel, and the total number of circles (say n) to be displayed is set by user along with the radius and their center coordinates.
When any of the circle overlap with another one, both are displayed in red colour, else they are drawn in blue colour.
i.e all circles that overlap with each other get drawn in red and all circles that are completely isolated are drawn in blue.
Now, there can be different groups of overlapping circles, I need each group of such overlapping circles to be displayed in different colour.i.e all overlapping circles of one group should be displayed in the same group should be displayed in the same colour (which in turn should be different from the all other group colour).
Can anyone help me do that? I am not able to do so.
I guess this should be a logic question.

Do Help !

Paul Clapham
Sheriff
Posts: 20750
30
So tell us more about these groups. Does somebody say in advance what the groups are, or do we have to figure out what they are based on some rules about overlappingness, or what?

Rose Jac
Ranch Hand
Posts: 33
Hi,

Well, the overlapping is based on the radius of the circle. Say, if circle1 has radius large enough to overlap circle2, and circle2's radius overlaps circle3 but circle3's radius is not large enough to overlap any part of circle1, then:
circl1, circle2 and circle3 are all in one group (as circle1 is connected to circle 2 and circle3 (via circle2), circle2 is directly connected to circle1and3, and circle3 is directly connected to circle2 and indirectly to circle1 (via circle2) ).

Its like- the olympics rings all belong to one group as they are either directly or indirectly connected to each other.

Any circle is indirectly connected to another circle (say A) if any of its immediate adjacent circle or another indirectly connected circle is connected to this another circle (A).

Any ideas?

Paul Clapham
Sheriff
Posts: 20750
30
I think I get it. So when you display all of the circles, they are going to look like a certain number of connected blobs. You want each blob to be a different colour and so you want to figure out what the blobs are and which circles are in which blobs.

Is that right?

Rose Jac
Ranch Hand
Posts: 33
Exactly!
i want to knwo which circle belongs to which group. And if it helps, each cricle has a unique ID.
Any idea on the same?

Darryl Burke
Bartender
Posts: 5125
11
• 1
Off the top of my head --

I would have the Circle class extend Ellipse2D.Double, with an overloaded intersects(Circle) method and a field of type Set<Circle> to contain circles that are intersected.

The application would contain a List<Circle>. Iterate over the List and update the Set<Circle> of each.

Iterate over the List a second time and draw each Circle along with the intersected Circles from the Set<Circle>. On drawing each Circle, remove it from the List. On moving on to the next Circle remaining in the List, change the Color.

Of course, you would have to carefully program the removing of Circles from the List while iterating over it.

-------------------------------

There may be a better/more efficient way which saves iterating over the List twice, but I can't see it.

edit It's a bit more complicated than that, considering the 1-connects-to-2 and 2-connects-to-3 thing

Nearly 3 am and NOT a good time for me to even try to get my head around that

Paul Clapham
Sheriff
Posts: 20750
30
Darryl Burke wrote:Iterate over the List and update the Set<Circle> of each.

This is the hard part. Suppose you have a series of circles where 1 overlaps 2, 2 overlaps 3, 3 overlaps 4, 4 overlaps 5, and so on, but there aren't any other overlaps. You want 1 to be in the same set as 5, but you have to do four separate overlap tests before you can find that out.

(From the graph theory point of view: the problem is to decompose a graph into its connected components. I googled for this but I couldn't find anything which specifically discussed that problem. Apparently the graph theorists must think it's too trivial to bother with because everything I did find was for more complicated problems.)

Here's my rough cut at the problem:

1. Start with the first circle. (This assumes you have the circles in an ordered list.) Assign it a colour (say red).

2. Next see which other circles overlap the circles which have already been assigned that colour. Assign them the same colour, and keep track of whether this changes anything. Repeat that until it doesn't change anything, after which you have identified all the circles in the red blob.

3. Now get the next circle which doesn't have a colour yet. (If there isn't any such circle then you're finished.) Assign it a different colour and repeat step 2 for that colour. Repeat this until you're finished.

This should turn into a loop inside a loop once you notice that step 3 is the same as step 1, just a special case.

I'm sure it isn't the fastest way to solve the problem, but the other one I have in mind involves recursive processing and would be harder to explain. A slow method is probably good enough if you don't have thousands of circles to deal with.

Darryl Burke
Bartender
Posts: 5125
11
Yeah, before I fell asleep I realized the recursive approach would probably work.

Now it's time for Rose to churn out some code,in the form of an SSCCE andif it doesn't work there'll be a specific problem we can address!

Rose Jac
Ranch Hand
Posts: 33
ok. So, this is a basic program that reflects mine somwhat.
I want (x,y) center coordinates to be retreived from any array only. This is because i , in my application, am trying to get the "nodes" or circles from the database.
I have also kept a constant radius = 50.
I tried the list and set thing, though i have have not got it right. NullPointerException present.
I have been on this since 2days ...getting

Do help

Darryl Burke
Bartender
Posts: 5125
11
It was suggested that you create a Circle class. I think you should start with that.

Once you have a Circle class, the rest will be so much easier.

Rose Jac
Ranch Hand
Posts: 33
Hey, thanks.
I just had to use an ArrayList of Set. and it worked!
ArrayList to store the circles and each set to store a group of circles.

Thanks.

Darryl Burke
Bartender
Posts: 5125
11
I'm glad you solved your problem. Would you like to post the working code? (a) for benefit of those who have a similar problem and find this thread (b) for review so experienced coders can see if there's room for improvement.