| Title: | Mathematics at DEC |
| Moderator: | RUSURE::EDP |
| Created: | Mon Feb 03 1986 |
| Last Modified: | Fri Jun 06 1997 |
| Last Successful Update: | Fri Jun 06 1997 |
| Number of topics: | 2083 |
| Total number of notes: | 14613 |
I will describe a minor mind bending type question: ( I'm not a true math person, so please disregard the sloppy approach used here. Feel free to re-word the question or to propose a mathematical approach to solving it. I appreciate any attempts at solving this.) The problem: How many "internal pieces" can a arbitrarily oriented 2d ellipse be broken into when clipped against a 6 sided unit cube ( clip volume ) ? I believe that this ellipse may have been transformed by a perspective transformation. The clip volume is a unit cube, but I'm not sure that the ellipse is a true ellipse after the perspective transformation. An "internal piece" is defined as a segment ( an elliptical arc ?) of the ellipse that lies inside of the clip volume. I do know that the answer for the maximum number of internal pieces is between 4 and 12. ( 12 is the absolute upper bound for a n-sided convex polygon that clips against all 6 clip planes. If the ellipse were an ellipsoid, then there would be 12 internal pieces. I guess if I were clipping an "egg" shaped object this would be true. However I am only concerned with a 2d ellipse in this question. ) To better understand what a "piece" is, I will describe a simpler problem: A circle can be broken into a maximum of 4 internal pieces and 4 external pieces when clipped against a square with the following constraints. The 4 internal pieces result when the radius of square ( a perpendicular line from the center to a side ) is slightly less than the radius of a circle existing at the same center as the square. thanks for any approaches, matt
| T.R | Title | User | Personal Name | Date | Lines |
|---|---|---|---|---|---|
| 1049.1 | up to six | CTCADM::ROTH | If you plant ice you'll harvest wind | Thu Apr 06 1989 13:47 | 9 |
The ellipse (or any conic section) lies in a plane. A plane can
be clipped against a cube into up to a 6 sided polygon, even a
regular hexagon; consider a plane passing thru the points
[.5,0,0], [1,0,.5], [1,.5,1], [.5,1,1], [0,1,.5], [0,.5,0].
Thus an ellipse can be found which is clipped against all 6 corners
of the polygon.
- Jim
| |||||
| 1049.2 | They all look alike from the right direction | NIZIAK::YARBROUGH | I PREFER PI | Thu Apr 06 1989 16:19 | 11 |
> I believe that this ellipse may have been transformed by a perspective > transformation. The clip volume is a unit cube, but I'm not sure > that the ellipse is a true ellipse after the perspective transformation. It is. To prove this you only need to show that the form of the basic ellipse equation, ((x-x0)/(x1-x0))^2+((y-y0)/(y1-y0))^2 = 1, is maintained when you apply a perspective transformation. The transformation changes the value of the constants x0, x1, y0, and y1, but not the form of the equation. Lynn | |||||
| 1049.3 | CTCADM::ROTH | If you plant ice you'll harvest wind | Thu Apr 06 1989 16:30 | 7 | |
< Note 1049.2 by NIZIAK::YARBROUGH "I PREFER PI" >
-< They all look alike from the right direction >-
Unless the ellipse becomes a hyperbola or parabola. It depends on
where you move the eye point to.
- Jim
| |||||
| 1049.4 | 6 internal arcs ( thanks ) | 3D::CORKUM | Hey Sports Fans, I love ya' | Thu Apr 06 1989 17:26 | 40 |
Jim,
Thanks for your answers. It helped me arrive at the solution I
was looking for. The solution is in fact 6 "internal pieces".
--------------------------------------------------------------------------------
For those of you who wish to understand the details:
The 6 "internal pieces" are the following elliptical (circular for
a regular hexagon) arcs.
The ellipse that generates "6 internal pieces" is the ellipse that
lies between:
an inscribing ellipse ( actually I believe that it's a
circle for the regular hexagon
that Jim described )
and an outscribing ellipse that contain the six intersection
points that Jim mentioned. Of course these are not the only
6 intersection points possible, but they did help in solving
the problem quite quickly.
Thus, in this special case there are a family of circles that solve the
problem of trying to determine the maximum number of "internal pieces"
that can be generated.
Another quick angle is:
A regular hexagon, defined by the 6 points that Jim mentioned, could be used
as the bounding "area" to clip against
[.5,0,0], [1,0,.5], [1,.5,1], [.5,1,1], [0,1,.5], [0,.5,0].
Simply looking at clipping a circle against a this regular hexagon resulted
in determining that at most 6 internal circular arcs can be generated.
thanks all,
matt
| |||||