Browse Prior Art Database

Correlation on Elliptic Arcs

IP.com Disclosure Number: IPCOM000060728D
Original Publication Date: 1986-May-01
Included in the Prior Art Database: 2005-Mar-09
Document File: 3 page(s) / 29K

IBM

Related People

Niblett, PD: AUTHOR

Abstract

This article describes an efficient algorithm for determining whether or not an elliptic arc lies completely or partly within a given rectangular area. An arc that intersects the rectangle is said to be 'accepted'; one that does not is termed 'rejected'. Such an algorithm can be used by a graphics application or terminal to implement a Pick device. In this situation the arc forms part of the picture displayed and the rectangle is the 'Pick window' moved around the screen under operator control. The rectangle is assumed to have sides parallel to the coordinate axes, this being adequate for the use just described, but the algorithm can be adapted to allow a general polygon to be used instead of this rectangle.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 3

Correlation on Elliptic Arcs

This article describes an efficient algorithm for determining whether or not an elliptic arc lies completely or partly within a given rectangular area. An arc that intersects the rectangle is said to be 'accepted'; one that does not is termed 'rejected'. Such an algorithm can be used by a graphics application or terminal to implement a Pick device. In this situation the arc forms part of the picture displayed and the rectangle is the 'Pick window' moved around the screen under operator control. The rectangle is assumed to have sides parallel to the coordinate axes, this being adequate for the use just described, but the algorithm can be adapted to allow a general polygon to be used instead of this rectangle. The arc is specified by two points (start and stop), a direction (clockwise or anticlockwise) and an analytic equation of the form:

(Image Omitted)

The problem is further complicated by the fact that the arc may form part of an area boundary definition. It is assumed that correlation on filled areas is performed by counting the number of times modulo 2 that the area boundary crosses the horizontal half-line stretching from the top left corner of the pick window to minus infinity. The 'brute force' solution to this problem is to raster the arc into a sequence of points as if for drawing and to compare each point in turn against the four boundaries of the rectangle. While this approach is satisfactory for small arcs, it is inefficient for those large arcs which cannot be trivially accepted or rejected. The algorithm to be described uses the analytic equation of the arc and some elementary calculus. It does not involve rastering the arc. THE BOUNDING RECTANGLE Taking the center of the ellipse as the origin of our coordinate space, it can be seen that the maximum x value attained by the ellipse is sqrt(B) and the maximum y value is sqrt(A). If we construct a rectangle going between Åsqrt(B) in the x direction and Åsqrt(A) in the y, we observe two properties: 1. The ellipse never strays outside this bounding rectangle. 2. Any horizontal or vertical line within this rectangle will intersect the ellipse (if extended to the rectangle's edges). THE ALGORITHM This will be described first for the simplest case, namely, full ellipses not forming part of an area boundary. 1. Compute the bounding rectangle and test it for intersection with the pick window. If the rectangle and window have no overlap, then reject the arc straightaway. 2. Test a known point on the arc (e.g., its start point) to see if it lies inside the pick window.

Accept the arc straightaway if it does. 3. Test the arc for intersection with each of the four edges of the pick window. If it crosses any of the edges, then accept the arc; if it crosses none of them, then reject it. To test an edge for intersection with the arc, proceed as follows a.Test the edge to see if any o...