Converting an ellipse into a polyline

Question

I currently have several ellipses. These are defined by a centre point, and then two vectors, one point to the minimum axis and other to the maximum axis.

However, for the program I'm creating I need to be able to deal with these shapes as a polyline. I'm fairly sure there must be formula for generating a set of points from the available data that I have, but I'm unsure how to go about doing it.

Does anyone have any ideas of how to go about this?

Thanks.

Answer 1

(Under assumption that both vectors that represent ellipse axes are parllel to coordinate axes)

If you have a radial ray emanating from the centre of ellipsis at angle angle, then that ray intersects the ellipse at point

x = x_half_axis * cos(angle);
y = y_half_axis * sin(angle);

where x_half_axis and y_half_axis age just the lengths (magnitudes) of your half-axis vectors.

So, just choose some sufficiently small angle step delta. Sweep around your centre point through the entire [0...2*Pi] range with that step, beginning with 0 angle, then delta angle, then 2 * delta angle and so on. For each angle value the coordinates of the ellipse point will be given by the above formulas. That way you will generate your polygonal representation of the ellipse.

If your delta is relatively large (few points on the ellipse) then it should be chosen carefully to make sure your "elliptical polygon" closes nicely: 2*Pi should split into a whole number of delta steps. Albeit for small delta values it does not matter as much.

---

If your minimum-maximum axis vectors are not parallel to coordinate axes, your can still use the above approach and then transform the resultant points to the proper final position by applying the corresponding rotation transformation.

---

Fixed-delta angle stepping has some disadvantages though. It generates a denser sequence of polygonal points near the miminum axis of the ellipse (where the curvature is smaller) and a sparser sequence of points near the maximum axis (where the curvature is greater). This is actually the opposite of the desirable behavior: it is better to have higher point density in the regions of higher curvature.

If that is an issue for you, then you can update the algorithm to make it use variadic stepping. The angle delta should gradually decrease as we approach the maximum axis and increase as we approach the minimum axis.

Answer 2

Assuming the center at (Xc,Yc) and the axis vectors (Xm,Ym), (XM,YM) (these two should be orthogonal), the formula is

X = XM cos(t) + Xm sin(t) + Xc
Y = YM cos(t) + Ym sin(t) + Yc

with t in [0,2Pi].

To get a efficient distribution of the endpoints on the outline, I recommend to use the maximum deviation criterion applied recursively: to draw the arc corresponding to the range [t0,t2], try the midpoint value t1=(t0+t2)/2. If the corresponding points are such that the distance of P1 to the line P0P2 is below a constant threshold (such as one pixel), you can approximate the arc by the segment P0P1. Otherwise, repeat the operation for the arcs [t0,t1] and [t1,t2].

Preorder recursion allows you to emit the polyline vertexes in sequence.