Different Colour for different group of overlapping circles.

[Rose Jac]

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 !
Thanks in advance

[Paul Clapham]

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]

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]

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]

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]

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]

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]

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]

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

import javax.swing.*;
import java.awt.*;
import java.util.ArrayList;
import java.util.Set;

public class Circles extends JPanel{
    private int x[] = {50,120,140,200,210,280};
    private int y[] = {50,120,140,200,210,280};
    private int r = 50;
    private int total = 6;
    private int r1 = 0, g1 = 255, b = 0;
    private ArrayList<Integer> nodes = new ArrayList();
    private Set<Integer> groups;

    Circles(){
        JFrame frame=new JFrame("At t = 0");
        frame.add(this);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setSize(400, 440);
        this.setBackground(Color.WHITE);
        frame.setLocationRelativeTo(null);
        frame.setVisible(true);
        for(int i = 0; i<6; i++) nodes.add(i);      //let index be the unique ID for each circle.
    }

    public void paint(Graphics g)
    {
        super.paint(g);
        g.translate(0, 400);
        System.out.println(nodes);
        for(int i = 0; i<nodes.size();i++)
        {
         int node1 = nodes.get(i);
         groups.add(node1);
         int x1 = x[node1];
         int y1 = y[node1];
         int nodeID1 = i;
         for(int j = 0; j<nodes.size();j++)
         {
            if(node1 != i)
            {
            int node2 = j;
            int x2 = x[j];
            int y2 = y[j];
            boolean result =  canCommunicate( node1,node2, x1, x2,  y1,  y2, r, r );
            if(result == true)
            {
                groups.add(j);
                for(int p = 0 ; p<groups.size(); p++)
                {
                    g.setColor(new Color(r1+30, g1-30, b+30));
                    g.drawOval(x1-r, y1-r, 2*r, 2*r);
                    g.drawOval(x2-r, y2-r, 2*r, 2*r);
                }
                nodes.remove(j);
                System.out.println("Aftre removal: " + nodes);
            }
          }
         }
        }
    }

    public boolean canCommunicate(int node1, int node2, int x1, int x2, int y1, int y2, int r1, int r2 )
{
    int distanceBetweenCenters1 = (int) Math.pow( (Math.pow( (x2-x1),2 ) + Math.pow( (y2-y1),2 )), 0.5);
    int overlap1 = (int)Math.abs(r1 - r2);
    int overlap2 = r1+r2;
    if((distanceBetweenCenters1 <= overlap1) || (distanceBetweenCenters1 <= overlap2))
        return true;
    else
        return false;
}
    public static void main(String args[])
    {
        Circles c = new Circles();
    }
}

Do help

[Darryl Burke]

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]

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]

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.