# Efficiently fill an ellipse with a k-many random ellipses

So, I can create a circle filled with circles of the same radius that gives this example picture:

with this code:

generateCirclesSameRadius[numCircles_Integer, boundaryRadius_, circleRadius_, maxAttempts_Integer] :=
Module[{circles = {}, attempt = 0, newCircle, canPlace},
While[Length[circles] < numCircles && attempt < maxAttempts,
canPlace = True;
Do[
If[Norm[newCircle - circle] < 2 circleRadius, canPlace = False; Break[];],
{circle, circles[[All, 2]]}
];
attempt++;
];
circles
]

drawCircles[circles_] :=
FaceForm[RandomColor[]], Circle[#[[2]], #[[1]]] & /@ circles}]

numCircles = 10; (* Adjust based on available space and circle radius *)
maxAttempts = 100;
drawCircles[circles]


And I can check overlaps of an ellipse with this code:

OverlapQ[ellipse1_List, ellipse2_List] :=
Module[
{a, b, \[Alpha], \[Beta], c, d, \[Delta], \[Gamma], ell1, ell2, int, realIntersectionExists},

(* Extract ellipse parameters from the lists *)
{a, b, \[Alpha], \[Beta]} = ellipse1;
{c, d, \[Delta], \[Gamma]} = ellipse2;

(* Define the parametric equations for the ellipses *)
ell1[t_] := {a Cos[t] + \[Alpha], b Sin[t] + \[Beta]};
ell2[t_] := {c Cos[t] + \[Delta], d Sin[t] + \[Gamma]};

(* Solve for intersection points, focusing on real solutions *)
int = Quiet[Solve[ell1[t] == ell2[s], {s, t}]];

(* Determine if there is at least one real intersection point *)
realIntersectionExists = Length[Select[int, FreeQ[#, Complex] &]] > 0;

(* Return True if there is at least one actual intersection, else False *)
realIntersectionExists

]


Which can be called with:

ellipse1 = {1, 0.5, 0, 0};
ellipse2 = {0.8, 0.9, 1, 1};
OverlapQ[ellipse1, ellipse2]


(gives True)

But I feel like there should be a more efficient way than to check the overlap of each this way or at least a more compact, readable method to do this. This is a very general problem that I think many people would use if solved.

• The ellisoids need to have the same shape？What is the ratio of the major axis and minor axis? Feb 12 at 4:10
• Are the ellipses aligned with x and y axes? If so, you can specify them as Disk[{alpha, beta}, {a, b}]. Or use Ellispoid for general ellipses (not necessarily axis aligned). You can use RegionDisjoint to test whether they overlap.
Feb 12 at 4:15
• @cvgmt No, they do not need to have a specific ratio. It would be up to the person to decide there were restrictions on input of the parameters. Feb 12 at 4:20
• An alternative is to use the Gilbert-Johnson-Keerthi-algorithm (see en.wikipedia.org/wiki/Gilbert–Johnson–Keerthi_distance_algorithm). It is a bit involved to implement, though. I have a C++ implementation at github.com/HenrikSchumacher/Repulsor. I can provide a LibraryFunction that uses it correctly, if you like. Feb 12 at 15:38
• If $n$ ellipses are present already, checking a new one against each of them costs $n$ ellipse-ellipse checks. For large $n$ this is of course too expensive. So you want to use some dynamic bounding volume hierarchy, octree, or other space partition tree to manage all the present ellipses. Then for a new ellipse one has to run only $O(n \, \log(n))$ collision checks between axis-aligned boxes (each of them is extremely fast); and only few ellipse-ellipse checks (roughly as many as there are present ellipses whose bounding box intersects with the bounding box of the new ellipse). Feb 12 at 15:44

One way to get non-overlapping ellipses is to place their centers far enough apart that they don't overlap no matter how they are oriented: use HardcorePointProcess to determine the centers, within a smaller version of the large ellipse so the ellipses around those centers are within that large ellipse.

For example:

center = {1, 0}; a = 2; b = 1; r = 0.2;
ellipse = Disk[center, {a, b}];

reg = RegionErosion[ellipse, r];
pts = RandomPointConfiguration[HardcorePointProcess[20, 2 r, 2], reg];

Graphics[{Style[ellipse, FaceForm[None], EdgeForm[Black]],
Disk[pts["Points"], r {1, 1/2}]}]


Each evaluation gives a new set of random locations.

If instead you'd like random rotations for the ellipses, change the last line to:

Graphics[{Style[ellipse, FaceForm[None], EdgeForm[Black]],
GeometricTransformation[Disk[#, r {1, 1/2}],
RotationTransform[RandomReal[{0, 2 \[Pi]}], #]] & /@
pts["Points"]}]


This method of placing centers work for any orientation of ellipses, so is a 'worst case' spacing of the centers. So it does not pack centers closer if the ellipses wouldn't overlap due to their orientation. This avoids needing to test whether ellipses overlap.

For different sizes or shapes, change Disk[#, r {1, 1/2}] to vary the values in the 2nd argument. Just be sure they don't exceed r, to avoid overlaps.

For example, for different sizes but the same shapes, you could use Disk[#, r RandomReal[{0.3, 1}] {1, 1/2}]:

For different sizes and shapes, e.g., Disk[#, r RandomReal[{0.2, 1}, 2]]:

• Does this only work if they are all the same size? Feb 12 at 4:54
• The ellipses can be different sizes or shapes. See the edit to the answer.
Feb 12 at 15:02
• For me this works very well, is fast, and super concise. The only draw back is that it technically isn't 100% random (entire state space) since there are restrictions, but for me it is perfect. Feb 12 at 18:03
• Just so people know, pts can be restricted in size or use a while loop to get a specified number of ellipses. But again, perfect for me. Feb 12 at 18:10
Clear["Global*"];
reg = Ellipsoid[{0, 0}, {10, 5}];
randomEllipsoid :=
TransformedRegion[
DiscretizeRegion@Disk[RandomPoint[reg], RandomReal[{.1, 3}]],
ScalingTransform[RandomReal[{1.2, 1.5}], RandomPoint[Circle[]]]];

randomEllipsoidIn :=
Block[{temp = randomEllipsoid},
While[! RegionWithin[reg, temp], temp = randomEllipsoid];
temp]
appendDisjoinEllipsoid[regs_] :=
Block[{ellipse = randomEllipsoidIn},
While[! (RegionDisjoint @@ Join[{ellipse}, regs]),
ellipse = randomEllipsoidIn];
Join[{ellipse}, regs]]
disjointEllipsoids[n_] :=
Nest[appendDisjoinEllipsoid, {randomEllipsoidIn}, n - 1]
k = 50;
Graphics[{{FaceForm[], EdgeForm[Cyan], reg}, {RandomColor[], #} & /@
disjointEllipsoids[k]}]

• k=50 ellipses

• k=150 ellipses

• 3D version
reg = Ellipsoid[{0, 0, 0}, {10, 8, 5}];
randomEllipsoid :=
TransformedRegion[
DiscretizeRegion@Ball[RandomPoint[reg], RandomReal[{.1, 3}]],
ScalingTransform[RandomReal[{1.2, 1.5}], RandomPoint[Sphere[]]]@*
ScalingTransform[RandomReal[{1.2, 1.5}], RandomPoint[Sphere[]]]];

randomEllipsoidIn :=
Block[{temp = randomEllipsoid},
While[! RegionWithin[reg, temp], temp = randomEllipsoid];
temp]
appendDisjoinEllipsoid[regs_] :=
Block[{ellipse = randomEllipsoidIn},
While[! (RegionDisjoint @@ Join[{ellipse}, regs]),
ellipse = randomEllipsoidIn];
Join[{ellipse}, regs]]
disjointEllipsoids[n_] :=
Nest[appendDisjoinEllipsoid, {randomEllipsoidIn}, n - 1]
k = 20;
Graphics3D[{{Opacity[.2],
reg}, {EdgeForm[], FaceForm[RandomColor[]], #} & /@
disjointEllipsoids[k]}, Boxed -> False]


Using DiscretizeRegion: (as a guide)

Clear["Global*"];
d2 = Disk[];
dreg = DiscretizeRegion[d2, MaxCellMeasure -> {1 -> 0.3}]


If the shape changes, the discretized region will change and so this strategy will work with any shape.

At this point Insphere should have come to the rescue, and please do try that with newer versions. I am using v12.2.0. I am resorting to a workaround.

The strategy is to get all polygons, find their centroids and the minimum distance from each centroid to the boundaries and place a circle in there.

polys2 = MeshPrimitives[dreg, 2];
cent = RegionCentroid /@ polys2;
mind = EuclideanDistance @@ {RegionCentroid@#,
RegionNearest[RegionBoundary@#, RegionCentroid@#]} & /@ polys2;
circles1 =
MapThread[Circle[#1, #2] &, {cent, mind}] //
Graphics[{#, d2 /. Disk -> Circle}] &


If you want to get circles that are of the same size, do some filtering with a threshold.

pos = Position[mind, _?(# > 0.03 &)];
circles2 =
MapThread[{RandomColor[], Circle[#1, 0.03]} &, {Extract[cent, pos],
Extract[mind, pos]}] // Graphics[{#, d2 /. Disk -> Circle}] &


Show[circles1, circles2]


If you can fit a circle inside a polygon, you can also fit an ellipse whose major axis will fit in there, although this may not be optimal in terms of packing. If you decide to fit ellipses in circles, these can be given a random rotation without violating the boundaries and causing overlap.

• Optimal packing is not a concern for me. I didn't know a better word for fill in the title. But your code is useful. Feb 12 at 5:38
• You can use shorter code e.g. circles3 = Insphere /@ polys2 // Graphics. Some days are tougher than others. @TegLouis
– Syed
Feb 12 at 16:01