Partition an area with circles and draw each region’s count in C#

[Partition an area with circles]

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.)


Download Example   Follow me on Twitter   RSS feed   Donate




This entry was posted in algorithms, geometry, graphics, mathematics and tagged , , , , , , , , , , , , . Bookmark the permalink.

4 Responses to Partition an area with circles and draw each region’s count in C#

  1. Ate Peeringa says:

    Hello,

    I am almost there with your examples but how do i get only the highest centroid. Thanx

  2. Rod Stephens says:

    I’m not sure I understand. Do you mean only the region with the largest count? Just look through the list of RegionInfo objects to find the one with the largest Count value.

  3. Baldvin says:

    I assume it’s normal, and can be expected, that as soon as we draw the 5th circle, this becomes incredibly slow? Would there be any way to work around that using any methods you know of?

  4. Rod Stephens says:

    You can probably improve things a little bit but I think you’re still going to have this problem. For example, this program builds the regions and finds their intersections in the Paint event handler. It would be more efficient to do this in the MouseUp event and then store the regions for drawing in the Paint event handler.

    But I think the Region class is pretty heavyweight and finding intersections between two Regions isn’t super fast.

    If you draw the circles so they don’t overlap, you only get one region per circle and comparing them is pretty fast. You should be able to draw a lot of circles that way.

    But if the circles intersect a lot, you get a combinatorial explosion so you end up with a lot of regions.

    Also note that small regions are more efficient than big ones. This is because of the way regions are implements. You can read about it (it’s pretty interesting) in the article GDI Objects.

    I suspect the real way to get better performance would be to create your own Region class that finds intersections more efficiently, perhaps treating a region as a polygon instead of a collection of rectangles. Unfortunately I don’t have time to really dig into it. If someone needs this for business purposes (i.e. can afford to pay for consulting on it), let me know.

Leave a Reply

Your email address will not be published. Required fields are marked *