Optimal place a piece of cake in a rectangle

Question

For a rectangle (w, h) and a piece of cake with a radius less than or equal to the smaller of the two sides (w, h), the starting angle and the angle of the end, how can I place the slice optimally in the rectangle so that it fills the room better (with optical point of view, not mathematically)?

Currently, I place the center of the slice of the cake in the center of the rectangle and use half the smaller of both sides of the rectangle as the radius. This leaves a lot of room for certain configurations.

Examples to clearly define what I need, based on the premise that the slice is drawn as a unit circle (i.e., 0 degrees along the positive X axis, and then works clockwise):

• Starting angle 0 and ending angle PI will result in a filled bottom half of the rectangle and an empty upper half. A good solution here would be to move the center 1/4 * h.
• Starting angle 0 and ending angle PI / 2 will lead to the filled bottom right quarter of the rectangle. A good solution here would be to move the center point to the upper left of the rectangle and set the radius to the smaller side of both sides of the rectangle.

This is pretty easy for the cases I drew, but it gets complicated when the start and end angles are arbitrary. I am looking for an algorithm that determines the center of the cutoff and the radius in a way that fills the rectangle best. The pseudo code will be great, since I'm not a big mathematician.

Answer 1

The extremums of the bounding box of your arc have the following format:

x + x0 * r = 0 x + x1 * r = w y + y0 * r = 0 y + y1 * r = h 

The values ​​x0, x1, y0 and y1 can be found by taking the minimum and maximum values ​​of up to 7 points: any tangential points that are covered (i.e. 0, 90, 180 and 270 degrees) and the end points of two line segments,

Given the extrema of the axis bounding box (x0, y0), (x1, y1) aligned, the radius and center point can be calculated as follows:

 r = min(w/(x1-x0), h/(y1-y0) x = -x0 * r y = -y0 * r 

Here is an implementation written in Lua:

 -- ensures the angle is in the range [0, 360) function wrap(angle) local x = math.fmod(angle, 2 * math.pi) if x < 0 then x = x + 2 * math.pi end return x end function place_arc(t0, t1, w, h) -- find the x-axis extrema local x0 = 1 local x1 = -1 local xlist = {} table.insert(xlist, 0) table.insert(xlist, math.cos(t0)) table.insert(xlist, math.cos(t1)) if wrap(t0) > wrap(t1) then table.insert(xlist, 1) end if wrap(t0-math.pi) > wrap(t1-math.pi) then table.insert(xlist, -1) end for _, x in ipairs(xlist) do if x < x0 then x0 = x end if x > x1 then x1 = x end end -- find the y-axis extrema local ylist = {} local y0 = 1 local y1 = -1 table.insert(ylist, 0) table.insert(ylist, math.sin(t0)) table.insert(ylist, math.sin(t1)) if wrap(t0-0.5*math.pi) > wrap(t1-0.5*math.pi) then table.insert(ylist, 1) end if wrap(t0-1.5*math.pi) > wrap(t1-1.5*math.pi) then table.insert(ylist, -1) end for _, y in ipairs(ylist) do if y < y0 then y0 = y end if y > y1 then y1 = y end end -- calculate the maximum radius the fits in the bounding box local r = math.min(w / (x1 - x0), h / (y1 - y0)) -- find x & y from the radius and minimum extrema local x = -x0 * r local y = -y0 * r -- calculate the final axis-aligned bounding-box (AABB) local aabb = { x0 = x + x0 * r, y0 = y + y0 * r, x1 = x + x1 * r, y1 = y + y1 * r } return x, y, r, aabb end function center_arc(x, y, aabb, w, h) dx = (w - aabb.x1) / 2 dy = (h - aabb.y1) / 2 return x + dx, y + dy end t0 = math.rad(60) t1 = math.rad(300) w = 320 h = 240 x, y, r, aabb = place_arc(t0, t1, w, h) x, y = center_arc(x, y, aabb, w, h) print(x, y, r) 

Output Example:

Answer 2

Instead of pseudo code, I used python, but it should be used. For this algorithm, I assume that startAngle < endAngle and that both are inside [-2 * PI, 2 * PI] . If you want to use both inside [0, 2 * PI] and startAngle> endAngle, I would do:

 if (startAngle > endAngle): startAngle = startAngle - 2 * PI 

So, the algorithm that comes to mind is to calculate the boundaries of the unit arc, and then scale to fit your rectangle.

Firstly, it is more complicated. You need to calculate 4 numbers:

 Left: MIN(cos(angle), 0) Right: MAX(cos(angle), 0) Top: MIN(sin(angle),0) Bottom: MAX(sin(angle),0) 

Of course, an angle is a range, so it is not as simple as this. However, in this calculation you need to include up to 11 points. Starting angle, ending angle, and possibly cardinal directions (of which 9 are from -2 * PI to 2 * PI .) I am going to define boundingBoxes as lists of 4 elements ordered [left, right, top, bottom]

 def IncludeAngle(boundingBox, angle) x = cos(angle) y = sin(angle) if (x < boundingBox[0]): boundingBox[0] = x if (x > boundingBox[1]): boundingBox[1] = x if (y < boundingBox[2]): boundingBox[2] = y if (y > boundingBox[3]): boundingBox[3] = y def CheckAngle(boundingBox, startAngle, endAngle, angle): if (startAngle <= angle and endAngle >= angle): IncludeAngle(boundingBox, angle) boundingBox = [0, 0, 0, 0] IncludeAngle(boundingBox, startAngle) IncludeAngle(boundingBox, endAngle) CheckAngle(boundingBox, startAngle, endAngle, -2 * PI) CheckAngle(boundingBox, startAngle, endAngle, -3 * PI / 2) CheckAngle(boundingBox, startAngle, endAngle, -PI) CheckAngle(boundingBox, startAngle, endAngle, -PI / 2) CheckAngle(boundingBox, startAngle, endAngle, 0) CheckAngle(boundingBox, startAngle, endAngle, PI / 2) CheckAngle(boundingBox, startAngle, endAngle, PI) CheckAngle(boundingBox, startAngle, endAngle, 3 * PI / 2) CheckAngle(boundingBox, startAngle, endAngle, 2 * PI) 

Now you have calculated the bounding box of the arc with the center 0,0 and radius 1 . To fill in the field, we will need to solve the linear equation:

 boundingBox[0] * xRadius + xOffset = 0 boundingBox[1] * xRadius + xOffset = w boundingBox[2] * yRadius + yOffset = 0 boundingBox[3] * yRadius + yOffset = h 

And we have to decide for xRadius and yRadius. You will notice that there are two radii. The reason for this is that in order to fill the rectangle, we must have several differences in two directions. Since your algorithm only requests one radius, we simply select the bottom of the two values.

The solution of the equation gives:

 xRadius = w / (boundingBox[1] - boundingBox[0]) yRadius = h / (boundingBox[2] - boundingBox[3]) radius = MIN(xRadius, yRadius) 

Here you need to check boundingBox[1] - boundingBox[0] to 0 and set xRadius to infinity in this case. This will give the correct result, since yRadius will be smaller. If you don't have infinity, you can just set it to 0 and in the MIN function, check 0 and use a different value in this case. xRadius and yRadius cannot be 0 , because for sin and cos must be 0 for all angles included above.

Now we have to put the center of the arc. We want this to be concentrated in both directions. Now we will create another linear equation:

 (boundingBox[0] + boundingBox[1]) / 2 * radius + x = xCenter = w/2 (boundingBox[2] + boundingBox[3]) / 2 * radius + y = yCenter = h/2 

The solution for x and y , the center of the arc, gives

 x = w/2 - (boundingBox[0] + boundingBox[1]) * radius / 2 y = h/2 - (boundingBox[3] + boundingBox[2]) * radius / 2 

This should give you the center of the arc and the radius needed to fit the largest circle in the given rectangle.

I have not tested any of this code, so this algorithm can have huge holes or possibly tiny ones caused by typos. I would really like to know if this algorithm works.

edit:

Entering the whole code gives:

 def IncludeAngle(boundingBox, angle) x = cos(angle) y = sin(angle) if (x < boundingBox[0]): boundingBox[0] = x if (x > boundingBox[1]): boundingBox[1] = x if (y < boundingBox[2]): boundingBox[2] = y if (y > boundingBox[3]): boundingBox[3] = y def CheckAngle(boundingBox, startAngle, endAngle, angle): if (startAngle <= angle and endAngle >= angle): IncludeAngle(boundingBox, angle) boundingBox = [0, 0, 0, 0] IncludeAngle(boundingBox, startAngle) IncludeAngle(boundingBox, endAngle) CheckAngle(boundingBox, startAngle, endAngle, -2 * PI) CheckAngle(boundingBox, startAngle, endAngle, -3 * PI / 2) CheckAngle(boundingBox, startAngle, endAngle, -PI) CheckAngle(boundingBox, startAngle, endAngle, -PI / 2) CheckAngle(boundingBox, startAngle, endAngle, 0) CheckAngle(boundingBox, startAngle, endAngle, PI / 2) CheckAngle(boundingBox, startAngle, endAngle, PI) CheckAngle(boundingBox, startAngle, endAngle, 3 * PI / 2) CheckAngle(boundingBox, startAngle, endAngle, 2 * PI) if (boundingBox[1] == boundingBox[0]): xRadius = 0 else: xRadius = w / (boundingBox[1] - boundingBox[0]) if (boundingBox[3] == boundingBox[2]): yRadius = 0 else: yRadius = h / (boundingBox[3] - boundingBox[2]) if xRadius == 0: radius = yRadius elif yRadius == 0: radius = xRadius else: radius = MIN(xRadius, yRadius) x = w/2 - (boundingBox[0] + boundingBox[1]) * radius / 2 y = h/2 - (boundingBox[3] + boundingBox[2]) * radius / 2 

edit:

One of the problems is that sin[2 * PI] will not be exactly 0 due to rounding errors. I think the solution is to get rid of the CheckAngle calls and replace them with something like:

 def CheckCardinal(boundingBox, startAngle, endAngle, cardinal): if startAngle < cardinal * PI / 2 and endAngle > cardinal * PI / 2: cardinal = cardinal % 4 if cardinal == 0: boundingBox[1] = 1 if cardinal == 1: boundingBox[3] = 1 if cardinal == 2: boundingBox[0] = -1 if cardinal == 3: boundingBox[2] = -1 CheckCardinal(boundingBox, startAngle, endAngle, -4) CheckCardinal(boundingBox, startAngle, endAngle, -3) CheckCardinal(boundingBox, startAngle, endAngle, -2) CheckCardinal(boundingBox, startAngle, endAngle, -1) CheckCardinal(boundingBox, startAngle, endAngle, 0) CheckCardinal(boundingBox, startAngle, endAngle, 1) CheckCardinal(boundingBox, startAngle, endAngle, 2) CheckCardinal(boundingBox, startAngle, endAngle, 3) CheckCardinal(boundingBox, startAngle, endAngle, 4) 

You still need IncludeAngle(startAngle) and IncludeAngle(endAngle)

Answer 3

Just think about the circle and forget about filling. The boundaries will be either the center of the circle, or the end points, or points at 0, 90, 180, or 270 degrees (if they exist in this fragment). The highs and lows of these seven points will determine your bounding box.

To place it in the center, calculate the average value of max and min for both the rectangle and the piece of cake, and add or subtract the difference in what you want to move.

Answer 4

I would divide the problem into three stages:

• Find the bounding box of a single piece of the pie (or if the radius is set to the actual slice of the pie centered at (0, 0)).
• Set the bounding box to the rectangle.
• Use the bounding box setup information to adjust the center and cutoff radius of the pie.

When I have time, I can merge this with more details.