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 `Poi`s. 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, feel free to mention them in the comments below.

Pingback: Draw lines with gaps to show they are passing under other lines in C# - C# HelperC# Helper