Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

Intersect ellips and rectangle

118 views
Skip to first unread message

Едуард Зозуля

unread,
Jun 8, 2018, 5:03:09 AM6/8/18
to
There is an ellipse and a rectangle.
Ellips is given by two radius (small and large) and coordinates of the center.
Rectangle - four points.

How to find the intersection points of an ellipse and a rectangle ?

Thanks !

Arjen Markus

unread,
Jun 8, 2018, 5:48:38 AM6/8/18
to
I do not think there is a shortcut for this, especially not if you have an ellipse that can have any orientation. So:
- Consider the four sides of the rectangle in turn
- Find the coordinates of the intersections of the line through two of the vertices making up the side (not the line piece yet) with the ellipse. That means solving the set of equations:
x**2/a**2 + y**2/b**2 = 1 (Okay, not the most general formula for an ellipse, but the principle remains the same)
c*x +d*y = 1 (the equation for the line through the side)
- After this slightly boring exercise, determine if the two points are within the bounds for the side.
- Repeat for all four sides.

It may get simpler if you first transform the ellipse to a circle, determine the intersections of the transformed rectangle with this circle and invert the transform. The geometry package in Tcllib may help (didn't quite check that).

Regards,

Arjen

Rich

unread,
Jun 8, 2018, 9:36:13 AM6/8/18
to
Arjen Markus <arjen.m...@gmail.com> wrote:
The OP's origional question also has the suspicious smell of a
"homework problem" from their geometry class about it.

Ricardo kozmate.net

unread,
Jun 9, 2018, 8:19:31 PM6/9/18
to
Em 08/06/18 14:36, Rich escreveu:
> The OP's origional question also has the suspicious smell of a
> "homework problem" from their geometry class about it.

Probably not. He makes a question here every once in a while some
related to images and geometry. (at least since 2016 my archive says)

On the other hand, *I* am taking two classes relating to geometry... and
I doubt there is anything much simpler than Arjen's reply. Still, may be
a good real life problem to try, on a break.

--
{ricardo from kozmate.net}

Едуард Зозуля

unread,
Jun 10, 2018, 1:35:14 AM6/10/18
to
пятница, 8 июня 2018 г., 12:48:38 UTC+3 пользователь Arjen Markus написал:
Many thanks !

I also thought to solve this way, but I asked the question for two reasons:
1) To listen to the opinion of people smarter than me
2) Perhaps someone faced this problem and has a ready solution

Arjen Markus

unread,
Jun 11, 2018, 4:08:24 PM6/11/18
to
Well, it is mostly circles for which this kind of questions arises. Are the ellipses aligned with the x/y-axis or are they more general?

(By the way, the Tcllib geometry module does not contain anything in this direction ...)

Regards,

Arjen
Message has been deleted

Едуард Зозуля

unread,
Jun 12, 2018, 3:31:57 AM6/12/18
to
понедельник, 11 июня 2018 г., 23:08:24 UTC+3 пользователь Arjen Markus написал:
For my task, everything can be simplified by imposing auxiliary restrictions:
1) The radii (half of the axis) of the ellipse are placed strictly on the axis-x and axis-y
2) Instead of a intersect with a rectangle, we find points intersect with a circle
3) The circle center always lies (placed) on the line of the ellipse

Example picture:
http://doro.poltava.ua/vintersect.png

I understand that it is necessary to solve the system of equations:
(x-x0)**2 + (y-y0)**2 = r**2
x**2/a**2 + y**2/b**2 = 1
but, this is a difficult

Arjen Markus

unread,
Jun 12, 2018, 3:44:08 AM6/12/18
to
Not difficult, merely tedious :). Although, you do end up with a fourth-degree equation if you eliminate, say, x. What you could do instead is, let a point move along the ellipse in small steps and determine when it enters and leaves the circle. That is an easy calculation. If you then average the position of the last point outside and the first point inside the circle you have a good approximation.

(You mentioned an ellipse and a rectangle before, this is a slightly different problem)

Regards,

Arjen

heinrichmartin

unread,
Jun 12, 2018, 4:35:39 AM6/12/18
to
On Tuesday, June 12, 2018 at 9:44:08 AM UTC+2, Arjen Markus wrote:
> > > > > > Ellips is given by two radius (small and large) and coordinates of the center.
> > For my task, everything can be simplified by imposing auxiliary restrictions:
> > 1) The radii (half of the axis) of the ellipse are placed strictly on the axis-x and axis-y
> > 2) Instead of a intersect with a rectangle, we find points intersect with a circle
> > 3) The circle center always lies (placed) on the line of the ellipse
> [...] What you could do instead is, let a point move along the ellipse in small steps and determine when it enters and leaves the circle. That is an easy calculation. If you then average the position of the last point outside and the first point inside the circle you have a good approximation.

Walking on the circle might be simpler. Parameter is the angle. Unfortunately, the math::complexnumbers package cannot construct complex numbers from modulus and argument, but this is an easy task. Test the point in the equation of the ellipse for lt/gt 1.

You could bisect (or otherwise split) to the desired precision.

On Friday, June 8, 2018 at 11:48:38 AM UTC+2, Arjen Markus wrote:
> - Find the coordinates of the intersections of the line through two of the vertices making up the side (not the line piece yet) with the ellipse. That means solving the set of equations:
> x**2/a**2 + y**2/b**2 = 1 (Okay, not the most general formula for an ellipse, but the principle remains the same)
> c*x +d*y = 1 (the equation for the line through the side)
> - After this slightly boring exercise, determine if the two points are within the bounds for the side.

> (You mentioned an ellipse and a rectangle before, this is a slightly different problem)

For the rectangle, I'd first check whether the edges are inside or outside the ellipse, and only then walk the side (line segment).

Arjen Markus

unread,
Jun 12, 2018, 7:12:59 AM6/12/18
to
On Tuesday, June 12, 2018 at 10:35:39 AM UTC+2, heinrichmartin wrote:

>
> Walking on the circle might be simpler. Parameter is the angle. Unfortunately, the math::complexnumbers package cannot construct complex numbers from modulus and argument, but this is an easy task. Test the point in the equation of the ellipse for lt/gt 1.
>

Here is some code to walkt the ellipse:

set t 0.0
while { $t < 6.29 } { ;# 2pi would probably be better ...
set x [expr {$a * cos($t)}]
set y [expr {$b * sin($t)}]
set t [expr {$t + 0.01}]
}

(Hm, intriguing remark vis-a-vis math::complexnumbers)

Regards,

Arjen

Christian Gollwitzer

unread,
Jun 12, 2018, 4:06:04 PM6/12/18
to
Am 12.06.18 um 09:31 schrieb Едуард Зозуля:
> For my task, everything can be simplified by imposing auxiliary restrictions:
> 1) The radii (half of the axis) of the ellipse are placed strictly on the axis-x and axis-y
> 2) Instead of a intersect with a rectangle, we find points intersect with a circle
> 3) The circle center always lies (placed) on the line of the ellipse
>
> Example picture:
> http://doro.poltava.ua/vintersect.png

Nice picture. Now the task is much clearer to me. In general, there
would be many cases including that there is no intersection point
because the circle completely encloses the ellipse and vice versa etc.,
but in this settig this can't happen.

> I understand that it is necessary to solve the system of equations:
> (x-x0)**2 + (y-y0)**2 = r**2
> x**2/a**2 + y**2/b**2 = 1
> but, this is a difficult

equations like this can usually be solved using fixed-point iteration. A
general scheme is the Newton-Raphson iteration, however this is probably
overkill. I think this set of equations can be solved easily by the
following iteration:

suppose x,y is a first approximation

repeat:
x = a**2 * ( 1 - y**2/b**2)

s = sqrt((x-x0)**2 + (y-y0)**2)
x = x0 + (x-x0)/s*r
y = y0 + (y-y0)/s*r
until convergence

The first equation moves (x,y) onto the ellipse. Then, the point is
projected onto the circle. That should converge in a few iterations.

(untested, though)

Christian

Christian Gollwitzer

unread,
Jun 12, 2018, 4:13:43 PM6/12/18
to
Am 12.06.18 um 22:05 schrieb Christian Gollwitzer:
and of course, there is an error here: There should be a square root and
it computes only x > 0. But maybe a similar scheme as for the circle
will work: project x/a, y/a onto the unit circle. i.e.

s = sqrt((x/a)**2 + (y/b)**2)
x = x/s
y = y/s

(still untested)

Ricardo kozmate.net

unread,
Jun 12, 2018, 6:08:07 PM6/12/18
to
Em 12/06/18 08:31, Едуард Зозуля escreveu:
>
> For my task, everything can be simplified by imposing auxiliary restrictions:
> 1) The radii (half of the axis) of the ellipse are placed strictly on the axis-x and axis-y
> 2) Instead of a intersect with a rectangle, we find points intersect with a circle
> 3) The circle center always lies (placed) on the line of the ellipse
>
> Example picture:
> http://doro.poltava.ua/vintersect.png
>
> I understand that it is necessary to solve the system of equations:
> (x-x0)**2 + (y-y0)**2 = r**2
> x**2/a**2 + y**2/b**2 = 1
> but, this is a difficult
>

If the circles are "small", i.e. r**2 / (a**2 + b**2) << 1, and your
lines are thick - as you example image suggests - maybe you can do with
an approximate solution.

Lets assume y>0.

Then the half-ellipse can be expressed as
y = b * sqrt(1 - x**2/a**2)

We can approximate the ellipse, near some point over it, (x0,y0), with a
line with slope, m, equal to the derivative at that point:
dy/dx = -b*x/(a*sqrt(a**2-x**2))

replacing x=x0
m = -b*x0/(a*sqrt(a**2-x0**2))

The line is
(y-y0) = m*(x-x0)

replacing this on the circle equation (y-y0)**2 + (x-x0)**2 = r**2 we
get the values for the x coordinate of the intercept points, xi:
xi = x0 +/- r/sqrt(1+m**2)

replace these back in the ellipse equation to get the respective yi
coordinates.

In short, given: a, b, r, x0 (y0 is defined from x0 because we assumed
y>0 and the point is over the ellipse) compute:

m = -b*x0/(a*sqrt(a**2-x0**2))
xip = x0 + r/sqrt(1+m**2)
xim = x0 - r/sqrt(1+m**2)
yip = b * sqrt(1 - xip**2/a**2)
yim = b * sqrt(1 - xim**2/a**2)

(notation: i for intercept, m and p for minus and plus)

The intercepts are (near to) (xip,yip) and (xip,yip)

If y<0, then use -y, and at the end use -yip and -yim (i.e, flip the y axis)

If the circle centre is near the maximum (or minimum) x, and it will
likely intercept the branch for y<0, then switch x by y and a by b (i.e
rotate the axis), compute, and switch back.

You can *probably* (I have not checked anything) improve the
approximation with a correction, k at the equations for xi, as in
xi = x0 +/- k*r/sqrt(1+m**2)

with k less but close to 1.


Obviously it has the downside of being an approximation, but on the
other hand it is a closed form solution, without iterations. If not for
anything else, it could be a good stating point for a more accurate
iterative solution.


--
{ricardo from kozmate.net}

Arjen Markus

unread,
Jun 18, 2018, 2:35:22 AM6/18/18
to
On Monday, June 11, 2018 at 10:08:24 PM UTC+2, Arjen Markus wrote:

>
> (By the way, the Tcllib geometry module does not contain anything in this direction ...)
>

No solution yet for ellipses, but I have done some work on the geometry package - intersection and the like with circles. Should be available soon (still need to do the documentation).

Regards,

Arjen

Едуард Зозуля

unread,
Jun 18, 2018, 3:35:24 AM6/18/18
to
понедельник, 18 июня 2018 г., 9:35:22 UTC+3 пользователь Arjen Markus написал:
Excellent !
Thanks.
0 new messages