0

do you know an algorithm for modeling an ellipse by a series of aligned circles? thanks

enter image description here

user2973395
  • 37
  • 1
  • 5
  • It is not clear what you want to achieve. Are you asking how to construct the three-centre curve of a [basket arch](https://www.mdpi.com/2073-8994/11/10/1243/htm)? – M Oehm Mar 25 '20 at 08:58
  • I want to check the intersection between two ellipses. I have a paper which describe collision detection and the recommendation is to do via circles inside ellipse, because the algo should count the number of intersected circles. It means I will check the intersection of circles, which are inside ellipse.... – user2973395 Mar 25 '20 at 09:03
  • @user2973395 what do mean? determine if two ellipses collide? Or determine the overlap surface? – Jean-Baptiste Yunès Mar 25 '20 at 09:11
  • [Like this](https://i.stack.imgur.com/1UDRu.png)? Perhaps you should link or quote the paper and illustrate what you want in the question. – M Oehm Mar 25 '20 at 09:16
  • https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=E9D1CACDD9068AE83B2012654E4F6C64?doi=10.1.1.369.3763&rep=rep1&type=pdf – user2973395 Mar 25 '20 at 09:21
  • So what you want is described by Figure 2 in that paper. Please edit your post so that it has all relevant information. People who want to answer shouldn't have to trawl the comments to piece together what they need to know. (I suggest to include a snap of Figure 2, since it makes clear what you want.) – M Oehm Mar 25 '20 at 09:43
  • That's probably what you want, section 2.1: https://www.researchgate.net/publication/309434476_A_new_algorithm_for_dense_ellipse_packing_and_polygonal_structures_generation_in_context_of_FEM_or_DEM – Ofek Shilon Mar 25 '20 at 10:42
  • @ Ofek Shilon it looks good, i'll check it...thanks! – user2973395 Mar 25 '20 at 11:00
  • It is possible to calculate intersection of ellipses. Why do you need circles? – MBo Mar 25 '20 at 13:39
  • in the paper (see above) was described why circles ;) but anyway, how can i calculate the intersection of two ellipses? I think it is not easy to do it, one soution would be polygon approximation – user2973395 Mar 25 '20 at 13:50
  • [First](https://stackoverflow.com/questions/17213922/finding-intersection-of-an-ellipse-with-another-ellipse-when-both-are-rotated/17214400#17214400), [second](https://stackoverflow.com/questions/15445546/finding-intersection-points-of-two-ellipses-python) – MBo Mar 25 '20 at 14:29

1 Answers1

1

If your ellipse is centered in the origin with long and short semiaxes a and b, the curvature radius r at the end of the long axis is

  r = b² − a

So, {±(a − r), 0} are the centres of the outer circles with radius r. The circle in the middle is at {0, 0} with radius b. For intermediate circles, you can describe a point on the ellipse with

  {x, y} = {a · cos θ, y = b · sin θ}

The tangent on the ellipse at this point is

  {dx, dy} = {− a · sin θ, dy = b · cos θ}

The intersection of the normal of that tangent and the major axis is the centre {x₀, 0} of a circle with radius r₀ that touches the ellipse.

  x₀ = x + y · dy / dx
  r₀ = hypot(x₀ − x, y)

The problem here is that you start with the angle θ and evnely spaced angles of the ellipse do not yield evenly distributed circles, see figure (a) below.

You can reverse the steps above to get evenly distributed circle centres. Given the centre {x₀, 0} of a circle,

  cos θ = x₀ / (a − b² / a)
  sin θ = sign(x₀) · sqrt(1 − cos² θ)
  r₀ = hypot(x₀ − a · cos θ, b · sin θ)

This will give the distribution in figure (b). You must play with the distances, so that your ellipse is covered by the circles. The flatter the ellipse, the more circles you need.

aequidistant ellipse angles bequidistand circle centres

M Oehm
  • 28,726
  • 3
  • 31
  • 42
  • ok, thanks. but what about the rotation? maybe i'll need a rotation matrix in order to rotate the ellipse and the centre of circles. – user2973395 Mar 25 '20 at 14:45
  • You probably know at what angle ϕ the ellipse's major axis is and where its centre {xₑ, yₑ} is. Calculate the circle centres and radii as above, then transform the centres {x₀, 0} to {xₑ + x₀ · cos ϕ, yₑ + x₀ · sin ϕ}. (That's the same as a rotation by a matrix, but the y component of the centres is always 0, so the calculation is simplified.) – M Oehm Mar 25 '20 at 14:56
  • Nice work. (while I believe that direct caclulation of ellipse intersection is really better:) – MBo Mar 26 '20 at 05:17
  • 1
    Thanks, @MBo. I agree with you that calculating the intersection of the ellipses is better, but what the OP wanted and what for came out one bit at a time, so I answered the actual question. He who asks an XY quesetion often just gets X. `:)` – M Oehm Mar 26 '20 at 06:11