CODEWITHSUNDEEP
iosswiftgraphicsgeometry
Stefan
Stefan

Reputation: 1056

Fitting irregular shape into circle

I have a bitmap with an alpha channel, showing an irregular shape. I try to scale and shift the shape to fit into a circle of given radius. Any ideas how to do this in an efficient way? This will have to be calculated at runtime.

Precision can be 1..2 pixels, it is more important not to cut away from the shape. I suppose it can be done by stepping through offset and scale values, drawing and checking for collisions, but this sounds kind of expensive.

schematic view

Solutions involving Swift/iOS greatly appreciated…

Upvotes: 1

Views: 475

Answers (2)

user1196549
user1196549

Reputation:

As a first step, scan the image to find all foreground pixels, and compute their convex hull (use the monotone chain approach, taking linear time O(N) as you can detect the points in sorted order). This will strongly reduce the number of points to consider.

Then you can find the smallest enclosing circle, which can be constructed in linear time O(H).

enter image description here

Lookup Nayuki's Smallest Enclosing Circle for what seems to be a clean implementation of the randomized algorithm.

Upvotes: 2

TheEye
TheEye

Reputation: 9346

You just have to fit the surrounding rectangle of the image (i suppose the image size is cut to just enclose the image without any white borders) into the circle. As you know the radius of the circle (i hope), the scale factor for the image should be 

scaleFactor = (circle diameter) / (longest diagonal of image)

Then center the scaled image on the circle and done.

Upvotes: 0

Related Questions