This example shows how you can partition an area with circles and determine the number of circles that contain each of the pieces.
The example Find the area where circles overlap in C# explains how to find the area where two or more circles overlap. This example extends this idea farther by using circles to partition an area. In other words, it uses circles to divide the area into non-overlapping pieces. It then labels each area with the number of circles that contain it. (The inspiration for this example comes from a collection of cellphone towers. The circles represent their areas of coverage and the labels tell how many towers are within range at every point.)
The RegionInfo class holds information about the partitions. This class has a Region property holding a Region that represents the partition. Its Count property indicates the number of circles that include the region.
The high-level idea behind the program is fairly simple, although the details are rather involved so I won’t cover them all here. Download the example and look at the code to learn the details.
When the form receives a Paint event, the program builds a List<regioninfo> named regioninfos that holds RegionInfo objects representing the circular partitions.
To build this list, the program considers each circle in turn. It builds a RegionInfo object to represent the circle and then calls the RegionInfo object’s MakeIntersections method.
The MakeIntersections method loops through the RegionInfo objects that are already in the list. For each other object in the list, the code considers how other and the current object this partition their areas. If the two objects overlap, then they divide their are into three pieces:
- this ∩ other
- this - other
- other - this
If the regions overlap, the code:
- Replaces other with other - this
- Replaces this with this - other
- Adds this ∩ other to a new list of RegionInfo objects
After it has compared this to all of the RegionInfo objects in the old list, it adds the objects in the new list to the old list.
After it has finished comparing every circle to the list, the partition is complete.
After building the partition, the Paint event handler loops through the RegionInfo objects calling their Draw methods.
The Draw method fills a partition with a color that depends on the partition’s count (so partitions with larger counts get brighter colors). It then uses techniques described in the example Find a Region centroid in C# to find the partition’s centroid and it draws the count there.
Download the example for additional details.
(Note that you can use this technique to partition an area with regions of any shape, not just circles.)