GraphicsPath Polygon Fitting in C#

Question

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.

Answer 1

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.

Answer 2

I don't see why you need the binary search.

Once you get the bounding rectangle for your shape, and you have the target rectangle into which you want to fit the shape, you can compare the two ratios targetHeight / shapeHeight and targetWidth / shapeWidth.

Take the smaller ratio, and use this as the scaling factor to scale your shape.

If the target is a circle and not a rectangle, you can use a similar solution by taking the ratio of targetCircleDiameter / boundingRectangleDiagonal and use this as your scaling factor.

Answer 3

You could use GetBounds on the GraphicsPath and the Region, then compare the sizes of the rectangles to at least get you close.

If the defined space is a square that should be exact.

If the defined space something else, that would at least get you close. You could then use a binary search to find the actual scaling amount.

Answer 4

Can't you compute the center of the graphicspath and a radius?

You could either compute center of gravity (average of coordinates) and add 2 times standard deviation - this should get you around 92% of your graph - most of the time it would be good, but will fail if your graph has most 'weight' in one end.

You could also compute the center of the points - run through all points, get max/min points in all directions as when computing boundingbox, take the center of this and measure longest distance to your (max/min) points as radius.

You could probably find a more sophisticated algorithm if you look for a bounding sphere algorithm - but if it is just to display something you could do some trade offs. If you are doing collision detection there exists some quick algorithms for that too :)

Answer 5

How about going the opposite way using simple math? Namely, get the bounding box/circle of the path, calculate the predefined rectangular ratio of height/width, compare that to the same value of BB, stretch the BB accordingly (e.g if predefined ration is less than 1, the BB is stretched horizontally and vertically otherwise to match the same ratio), finally scale the whole thing to the predefined rectangular size. The scale factor is now just the minimum between predefined height divided by BB height and predefined width divided by BB width. (For the bounding circle there is no need to adjust its size.)