A geometry package in Ada (abstract only)
Karl O. Rehmer, Linda S. Rising · 1987
Many kinds of applications need the ability to inquire about how some elementary geometric figures relate to one another. In particular, the questions about the location of a point with relation to a geometric object, whether one geometric object is contained within another, and whether two geometric objects overlap have broad applicability. An Ada package which provides the answers to some of the problems above has been developed at Magnavox Electronic Systems Company.Since many applications could potentially use this package, it was decided to make it a generic package with one parameter indicating the floating point type which would properly represent coordinates and distances to the desired number of significant figures. Further, since the geometric objects manipulated by this package are to be used by a variety of programs, they have been declared as private types. As a consequence, each of the types, Point_Type, Circle_Type, Convex_Quadrilateral_Type, and Polygon_Type has associated functions which allow the initialization of an object of the type and which allow inquiry properties like coordinates of a point, center and radius of a circle, and vertices of quadrilaterals and polygons. A polygon need not be convex. Thus, if one were going to store a trapezoid, one would use the Convex_Quadrilateral_Type, since this carries with it the fact that the figure is convex. A maximum number of vertices that polygons considered are allowed to have is a generic parameter to the package.Functions which show the relationship of a point to other objects include functions which give the distance between two points, the distance from a point to the line segment joining two other points, determine if a point is on a line, determine if a point is to the right of a line (from an observer's point of view), determine if a point is inside a circle, determine if a point is inside a convex quadrilateral, and determine if a point is inside a polygon.Functions involving circles only or circles and objects other than points include functions which give the area of a circle, determine whether a circle is contained within another circle, determine whether a circle overlaps another circle, whether a circle is contained in a convex quadrilateral, whether a circle intersects a convex quadrilateral, whether a circle is contained in a polygon, and whether a circle intersects a polygon.In addition to the functions mentioned above, a function which determines whether a convex quadrilateral is contained in another convex quadrilateral, and a function which determines if two convex quadrilaterals overlap are provided. Similarly, a function which determines if a convex quadrilateral is contained in a polygon and one which determines whether a convex quadrilateral and a polygon overlap are provided. In addition, a function which determines if a polygon is contained in a convex quadrilateral and a function for the area of a convex quadrilateral have also been implemented. The original specification for the package was to provide the functions above for rectangles only, but the algorithms turned out to be just as easy to implement for general convex quadrilaterals, so this was done for the sake of greater generality.For polygons only, two functions are provided. One determines if one polygon is contained in another, and the other determines whether two polygons overlap. At this time, a function for the area of a polygon has not been implemented, though this should not be a major task. An interesting problem for polygons is to determine the polygon which is formed by the intersection of two overlapping polygons. We also hope to soon implement a function which will determine whether a given polygon is convex. A function which determines if a polygon is contained in a convex polygon is much easier to implement than a function which solves the similar, but more general problem stated above.The most difficult algorithms of those implemented were functions which were used in determining containment or overlap of the figures which have line segments as edges. The questions of whether two polygons overlap, whether one polygon is contained in another, and whether two convex quadrilaterals overlap provide many special cases for consideration. (Edges can be shared, edges of different figures may intersect in other than one point, an edge of one figure may contain several edges of another figure, etc.). As an aid in answering the questions mentioned above, functions which report whether a line segment is contained in a polygon and whether a line segment overlaps a polygon or rectangle were produced. Each of these need to handle a number of special cases and are, by far, the most complex algorithms in this package.