Search code examples
c#polygongraphicspath

GraphicsPath Polygon Fitting in C#

I need to "fit" an arbitrarily shaped GraphicsPath into a defined space (almost always a Rectangle or Circle).

I currently scale the GraphicsPath using the Matrix object and the scaling works fine, but the problem is getting the scale factors.

The best technique I can come up with is converting the GraphicsPath to a Region, converting the Rectangle or Circle to a Region, and performing a:

rgnShape.Intersect(rgnCircle);

and then checking if:

rgnShape.IsEmpty()

However, this just tells me if the shape is too large to fit, and it becomes necessary to scale the shape smaller, and try again (possibly many, many times).

Is there an easy way to instantly calculate the scaling factors to fit a polygon GraphicsPath so that it fits entirely into a circle. The result should be the largest polygon that still fits completely within the circle.

Solution

  • See http://en.wikipedia.org/wiki/Smallest_circle_problem for discussion of this problem in terms of points rather than paths, found by Simon.

    1. So, do that, use rgnShape.Intersect(rgnCircle); to check if it worked. If it failed, take each curve and grab the points farthest from the center of the circle you found (there may be more than one such point for any given region).

    2. Add them to your points list reapply the algorithm. You won't need to start from scratch; you do not need to consider points not on the border (i.e., ignore points not in "Set Q" that was found by the original call to the algorithm).

    Note that this is no longer linear, since the probability of generating recursive calls is no longer 1/i for the ith point.

    This has one edge condition you must handle explicitly. In the event that one of the curves found found outside the region found during the first iteration of step 1 is perfectly circular and touching the outside circle, there will be infinite points within "Set Q" and this algorithm will fail miserably. So, after applying rgnShape.Intersect(rgnCircle); for the first time, you should check any perfectly round curves explicitely for this case. For example, if your shape is (} you should explicitly check () (for purposes of this discussion, pretend () is a circle) if ( lies outside of the region found during the first iteration.

    This is still pretty bad, but it's better than changing every curve into points.