Title: Draw interlocked circles in C#

This example draws a set of interlocked circles so they alternate between above and below each other. As you can see from the picture, the circles are made up of colored lines with black outlines so it's easy to see when one passes over another. The problem is that there's no order in which you can draw the circles so they appear properly woven together.

The program works in two stages. First it finds the points where interlocked circles intersect. It then draws the circles and their intersections. Much of the code that performs those operations is in the Circle class, which I'll describe shortly. First I'll describe the Poi class that the program uses to store information about points of intersection.

Points of Intersection

The following Poi class stores information about the point of intersection (POI) between two interlocked circles. If two circles intersect, then they share a common Poi object that represents that point of intersection.

class Poi { public PointF Location; public Circle[] Circles = null; public Circle CircleOnTop = null; public Poi(PointF location, Circle circle1, Circle circle2) { Location = location; Circles = new Circle[] { circle1, circle2 }; } public override string ToString() { return string.Format("({0}/{1}", Circles[0], Circles[1]); } // Return the other circle. public Circle OtherCircle(Circle this_circle) { if (Circles[0] != this_circle) return Circles[0]; return Circles[1]; } // Return the circle on the bottom, if the top circle is assigned. public Circle CircleOnBottom() { if (CircleOnTop == null) return null; return OtherCircle(CircleOnTop); } }

The Location field indicates where the intersection occurs, the Circles array stores references to the two circles, and CircleOnTop indicates the circle that is on top at the point of intersection.

The class's constructor simply saves the two circles. The ToString method just returns the names of the circles.

The OtherCircle method simply returns the Poi object's circle that is not passed in as a parameter. The CircleOnBottom method uses that method to return the circle that is on the bottom. It first checks whether CircleOnTop is defined and, if it is, it returns the other circle.

The Poi class holds information about an intersection, but it doesn't do much. The Circle class described in the following sections performs the most interesting work.

Finding Points of Intersection

The following code snippet shows how the beginning of the Circle class.

class Circle { public PointF Center; public float Radius, CircleThickness, OutlineThickness; public Color FillColor, OutlineColor; public List<Poi> Pois = new List<Poi>(); public List<float> Angles = new List<float>(); public int NumAssigned = 0; ... }

The Center and Radius values define the circle's position and size. The CircleThickness and OutlineThickness values indicate how thick the circle's edge and outlines should be. The FillColor and OutlineColor values hold the circle's colors.

The other values are a bit more interesting. The Pois list holds information about places where other circles intersect this one. The Angles list holds the angles from the center of the circle to the corresponding points of intersection. The last value, NumAssigned, indicates the number of Poi objects that this circle has that have not yet had their CircleOnTop values assigned.

The class's AllPoisAreAssigned method shown in the following code uses the NumAssigned value.

// Return true if all of the POIs have been assigned. public bool AllPoisAreAssigned() { return NumAssigned == Pois.Count; }

This method simply returns true if NumAssigned equals the number of Poi objects meaning all of those objects have been assigned.

Finding POIs

After the program defines its interlocked circles, it calls the Circle class's static FindPois method shown in the following code.

// Find the circles' POIs in sorted order. public static void FindPois(Circle[] circles) { // Find the POIs. for (int i = 0; i < circles.Length; i++) { for (int j = i + 1; j < circles.Length; j++) { PointF p1, p2; FindCircleCircleIntersections( circles[i].Center.X, circles[i].Center.Y, circles[i].Radius, circles[j].Center.X, circles[j].Center.Y, circles[j].Radius, out p1, out p2); if (!float.IsNaN(p1.X)) { Poi poi = new Poi(p1, circles[i], circles[j]); circles[i].Pois.Add(poi); circles[j].Pois.Add(poi); } if (!float.IsNaN(p2.X)) { Poi poi = new Poi(p2, circles[i], circles[j]); circles[i].Pois.Add(poi); circles[j].Pois.Add(poi); } } } // Sort the POIs. foreach (Circle circle in circles) { circle.SortPois(); } // Initially none of the circles has its POIs assigned. List<Circle> unfinished = new List<Circle>(circles); // Repeat until all circles are completely assigned. while (unfinished.Count > 0) { // At this point, all unfinished circles have no assignments. // Make a list to hold circles that are partially assigned. List<Circle> partially_assigned = new List<Circle>(); // Add the first unfinished circle to the // partially_assigned list. // Arbitrarily make it on top in its first POI. Circle circle = unfinished[0]; unfinished.RemoveAt(0); partially_assigned.Add(circle); if (circle.Pois.Count > 0) circle.Pois[0].CircleOnTop = circle; // Process circles in the partially_assigned // list until it is empty. while (partially_assigned.Count > 0) { // Remove the first circle from the list. circle = partially_assigned[0]; partially_assigned.RemoveAt(0); // Assign the remaining entries for this circle. circle.Assign(unfinished, partially_assigned); } // When we reach this point, partially_assigned // is empty and the most recent connected // component has been assigned. } // When we reach this point, unfinished is // empty and all Circles have been assigned. }

The method first uses two nested loops to loop over every pair of interlocked circles. The outer loop makes i loop from 0 to the index of the last circle. The inner loop makes j loop from i + 1 to the index of the last circle. That makes the loops consider each pair of circles only once. For example, the program first compares circle 0 to circle 1. Because the inner loop makes j start at i + 1, the code does not later compare circle 1 to circle 0.

For each unique pair of circles, the program calls the FindCircleCircleIntersections method to see where the two circles intersect. For information on that method, see my post Determine where two circles intersect in C#.

The program creates Poi objects to store information about any intersections between the two circles.

Next, the code loops through the circles and calls their SortPois methods to sort their POIs by their angles with respect to the circles' centers. I'll show that method shortly.

The method then creates a list of Circle objects named unfinished to hold Circle objects that have not yet been processed. None of the Poi objects of these circles have their CircleOnTop values assigned. The code passes circles array into the list's constructor so the list initially holds all of the circles.

The program then enters a loop that lasts as long as the unfinished list is not empty. Within the loop some Circle objects may may have both assigned and unassigned Poi objects. The code creates a list named partially_assigned to hold those Circle objects that are partially assigned. Initially that list is empty.

The code removes the first Circle from the unfinished list and adds it to the partially_assigned list. If the Circle has any Poi objects, the code also arbitrarily sets that Circle to be on top in its first Poi. Note that this determines whether the Circle is on the top or bottom for all of its other points of intersection because they alternate: on-top/on-bottom.

Now the program enters another loop that executes as long as the partially_assigned list is not empty. Within the loop, the code removes the first Circle from the partially_assigned list and calls that object's Assign method. I'll describe that method shortly, but for now I'll just tell you what it does. That method assigns the CircleOnTop value for all of the Circle's Pois. When it makes an assignment, the method also adds the other circle that shares the Poi to the partially_assigned list and removes it from the unfinished list.

After the FindPois method finishes processing an entry in the partially_assigned list, it repeats the process for the next item in the list.

Once the partially_assigned list is empty, the method processes the next entry in the unfinished list. When the unfinished list is empty, all of the interlocked circles have been completely assigned so the method is done.

SortPois

The Circle class's SortPois method shown in the following code sorts a Circle object's Pois list.

// Sort this circle's POIs. private void SortPois() { // Calculate the POIs' angles. Angles = new List<float>(); foreach (Poi poi in Pois) { float dx = poi.Location.X - Center.X; float dy = poi.Location.Y - Center.Y; double radians = Math.Atan2(dy, dx); Angles.Add((float)(radians / Math.PI * 180)); } // Sort the POIs by angle. Poi[] poi_array = Pois.ToArray(); float[] angle_array = Angles.ToArray(); Array.Sort(angle_array, poi_array); // Save the POIs and angles. Pois = new List<Poi>(poi_array); Angles = new List<float>(angle_array); }

This method first sets the Circle object's Angles value to a new list of float. It then loops through the Pois list and sets the corresponding Angles value for each Poi.

Next the code converts the Pois and Angles lists into arrays and calls the Array class's Sort method. It passes that method the two arrays so it sorts poi_array while using angle_array as the sort keys. The method finishes by using the sorted arrays to reinitialize the Circles and Angles lists so they are in sorted order.

Assign

The Circle class's Assign method assigns the CircleOnTop value for a Circle object's Poi objects. This method should only be called if at least one Poi has already been assigned. The following code shows the method.

// Assign POIs for this circle alternating // top/bottom with index first_on_top on top. // Add other circles that share this one's POIs // to the partially_assigned list and remove // them from the unfinished list. private void Assign(List<Circle> unfinished, List<Circle> partially_assigned) { // If this circle has no Pois or if all of its Pois // are assigned, remove it from the list and return. if ((Pois.Count == 0) || AllPoisAreAssigned()) { partially_assigned.Remove(this); return; } // Find the first POI that is assigned. int first_assigned = -1; for (int i = 0; i < Pois.Count; i++) { if (Pois[i].CircleOnTop != null) { first_assigned = i; break; } } // See whether the first assigned Poi is this Circle. bool last_was_this = (Pois[first_assigned].CircleOnTop == this); // Assign the other Pois. for (int i = 1; i < Pois.Count; i++) { int index = (first_assigned + i) % Pois.Count; if (Pois[index].CircleOnTop == null) { // Find the other Circle at this Poi. Circle other = Pois[index].OtherCircle(this); // Place the correct Circle on top. if (last_was_this) Pois[index].CircleOnTop = other; else Pois[index].CircleOnTop = this; // If the other circle is not completely assigned and // is not aleady on the partially_assigned list, add it. if (!other.AllPoisAreAssigned() && !partially_assigned.Contains(other)) partially_assigned.Add(other); // Remove the other Circle from the unfinished list. if (unfinished.Contains(other)) unfinished.Remove(other); NumAssigned++; } // Remember whether this Poi has this Circle on top. last_was_this = !last_was_this; } }

If the Circle object has no Poi objects or if all of the Poi objects have been assigned, then the method simply removes the Circle from the partially_�assigned list and returns.

If the method does not immediately return, it loops through the Pois list and finds the first object that has CircleOnTop assigned. It sets variable first_assigned equal to the index of that object.

The method then sets variable last_was_this to true if the first assignment had the current Circle on top. The code enters a loop where value i runs from 1 to the number of Poi objects in the Pois list. It sets index = (first_assigned + i) % Pois.Count. As a result, the value index loops through the list's indices starting at first_assigned + 1 and ending at first_assigned - 1.

For the new index value, the code checks to see if the corresponding Poi object has a non-null CircleOnTop value. If CircleOnTop is null, the code gets the other Circle at this Poi. (I'll show the OtherCircle method shortly.)

If the last Poi has the current Circle on top, then the code makes the current Poi place the other Circle on top. If the last Poi has its other Circle on top, then the code places the current Circle on top of the current Poi.

This step assigns the CircleOnTop value for the Poi, which is shared by the other Circle. That means the other Circle has now been partially assigned. If that other Circle has not yet been completely assigned and if it is not already in the partially_assigned list, the code adds it there. If the other Circle is in the unfinished list, the code also removes it from that list.

After it has finished assigning this Poi, the method increments the Circle object's NumAssigned value. It then toggles the last_was_this value so alternate Poi objects have the current Circle on top.

OtherCircle

The Poi class's OtherCircle method takes as an input parameter a Circle and then returns the Poi object's other circle. The following code shows how the method works.

// Return the other circle. public Circle OtherCircle(Circle this_circle) { if (Circles[0] != this_circle) return Circles[0]; return Circles[1]; }

This method simply compares the input Circle to the Poi object's first Circle. If the two do not match, the method returns the first Circle object. If the two do match, the method returns the second Circle object.

Drawing Circles

The following code shows the main form's Paint event handler.

// Draw the circles. private void Form1_Paint(object sender, PaintEventArgs e) { e.Graphics.SmoothingMode = SmoothingMode.AntiAlias; // Draw the circles. foreach (Circle circle in Circles) circle.Draw(e.Graphics); // Draw the on top POIs. foreach (Circle circle in Circles) circle.DrawPois(e.Graphics); }

This method sets the Graphics object's SmoothingMode property. It then loops through the Circle objects and calls their Draw methods (shown shortly) to draw the circles. At this point, the circles drawn last are drawn on top so the circles are not interlocked. The picture on the right shows what they might look like at this point.

Next the code loops through the Circle objects again, this time calling their DrawPois methods (also shown shortly) to draw the POIs so those on top look like they are on top.

The following sections show the Circle class's Draw and DrawPois methods.

Draw

The following code shows the Circle class's Draw method.

// Draw the circle. public void Draw(Graphics gr) { using (Pen fill_pen = new Pen(FillColor, CircleThickness)) { using (Pen outline_pen = new Pen(OutlineColor, OutlineThickness)) { gr.DrawThickArc(Center, Radius, 0, 360, fill_pen, outline_pen); } } }

This method creates two pens. The fill_pen is used to fill the interior of the circle's edge. The outline_pen is used to draw the outline along the sides of the circle's edges.

After creating the pens, the method calls the DrawThickArc method to draw the circle.

The DrawThickArc method is an extension method added to the Graphics class that draws an arc of a circle. The following code shows that method.

// Draw a thick arc with different inside and outside pens. public static void DrawThickArc(this Graphics gr, PointF center, float radius, float start_angle, float sweep_angle, Pen fill_pen, Pen outline_pen) { // Draw the main arc. gr.DrawArc(fill_pen, center.X - radius, center.Y - radius, 2 * radius, 2 * radius, start_angle, sweep_angle); // Draw the outer outline. float r1 = radius + fill_pen.Width / 2f + outline_pen.Width / 2f; gr.DrawArc(outline_pen, center.X - r1, center.Y - r1, 2 * r1, 2 * r1, start_angle, sweep_angle); // Draw the inner outline. float r2 = radius - fill_pen.Width / 2f - outline_pen.Width / 2f; gr.DrawArc(outline_pen, center.X - r2, center.Y - r2, 2 * r2, 2 * r2, start_angle, sweep_angle); }

This method first draws the body of the arc with the fill_pen.

The code then calculates a new radius for the arc's outer edge. The new radius is the original arc radius plus half of the fill_pen thickness plus half of the outline_pen thickness. The method then uses the new radius and the outline_pen to draw the outer edge.

The code draws the inner edge similarly. It calculates a new radius equal to the original radius minus half of the fill and outline pen thicknesses and then draws the inner edge.

DrawPois

The DrawPois method shown in the following code draws a Circle object's POIs where the Circle should be in top.

// Draw the POIs where this circle is on top. public void DrawPois(Graphics gr) { using (Pen fill_pen = new Pen(FillColor, CircleThickness)) { using (Pen outline_pen = new Pen(OutlineColor, OutlineThickness)) { for (int i = 0; i < Pois.Count; i++) { if (Pois[i].CircleOnTop == this) { const float sweep_angle = 30; float start_angle = Angles[i] - sweep_angle / 2f; gr.DrawThickArc(Center, Radius, start_angle, sweep_angle, fill_pen, outline_pen); } } } } }

This method first creates the Circle object's fill and outline pens. It then loops through the object's Pois list. If a Poi has this circle in its CircleOnTop value, then the method calls the DrawThickArc method to draw the piece of the circle where the POI lies.

Note that this won't work if the two interlocked circles at this POI meet at a very shallow angle. In that case, the 30 degree sweep angle used by the code will not be large enough to cover the entire area where the two circles overlap. You can make the sweep angle larger, but then the method may draw over part of a different POI if this Circle has multiple POIs that are close together. The value 30 degrees works well for the examples that I tested.

The Main Program

When the program starts, the form's Load event handler uses the following code to define the circles shown in the picture at the top of this post.

// See where the circles intersect. private void Form1_Load(object sender, EventArgs e) { // Make some circles. // Four all interlocked. Circles = new Circle[] { new Circle(new PointF(100, 100), 50, 10, 2, Color.Orange, Color.Black), new Circle(new PointF(150, 100), 50, 10, 2, Color.Green, Color.Black), new Circle(new PointF(100, 150), 50, 10, 2, Color.Red, Color.Black), new Circle(new PointF(150, 150), 50, 10, 2, Color.Blue, Color.Black), }; // Find the circles' POIs. Circle.FindPois(Circles); }

This code simply creates an array of Circle objects and then calls the Circle class's FindPois method to find their POIs. The Paint event handler does the rest.

Conclusion

As I mentioned earlier, the 30 degree sweep angle may not work if the interlocked circles have POIs too close together or if two circles intersect at too small an angle. The method of alternating which circle belongs on top also only works if circles that intersect always intersect twice. For example, in the picture on the right, the red and green circles intersect only once. As a result, the red circle has three intersections so there is no way that it can be on top half of the time and on the bottom half of the time.

Download the example program to experiment with it. The code contains a some compiler directives that let you easily try out a few test patterns. If you build particularly interesting pictures and post them somewhere, email me.

Download the example to experiment with it and to see additional details.