Nonconvex polygon identifier

Details Nonconvex polygon identifier Nonconvex polygon identifier

1991-04-30

1994-09-13

Harkcom, Gary V.

395141, G06K 900

Patent

active

053476190

ABSTRACT:
A method is provided for distinguishing nonconvex polygons from complex polygons. The present invention compares the edges of a polygon for self intersection points. Initially, "base" and "compare" edges are designated and bounding boxes for each of these edges are determined. The bounding boxes are then compared and if they intersect the edges may have points in common, whereas if no intersection occurs, then there are no common points and the edges are incremented and a comparison of other edges occurs. If it is determined that bounding boxes intersect, the intersection point for the edges under consideration is determined. If this intersection point lies within both bounding boxes, then the polygon is complex and the test ends. However, if the intersection point is outside either bounding box, then the edges are incremented and processing continues until all relevant edges have been considered.

REFERENCES:
patent: 3889107 (1975-06-01), Sutherland
patent: 4783829 (1988-11-01), Miyakawa et al.
patent: 4791582 (1988-02-01), Ueda et al.
patent: 4809065 (1989-02-01), Harris et al.
patent: 4862392 (1989-08-01), Steiner
patent: 4897805 (1990-01-01), Wang
patent: 4930091 (1990-05-01), Schroeder et al.
patent: 4933865 (1990-06-01), Yamamoto et al.
patent: 4951227 (1990-08-01), Todd
patent: 4962468 (1990-10-01), Beauregard et al.
patent: 5129051 (1992-07-01), Cain
Triangulating Simple Polygons and Equivalent Problems. Fournier et al., ACM vol. 3, No. 2, Apr. 1984, pp. 153-174.
IBM TDB "Method to Determine the Convexity of Polygons", vol. 28, No. 5, Oct. 1985, pp. 2203-2208.
"Computer Graphics: Principles and Practice" J. Foley, A. Van Dam, S. Feiner, J. Hughes, Addison-Wesley, 1990, pp. 964-965.

Affiliated with

Also associated with

Rating

Nonconvex polygon identifier does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Nonconvex polygon identifier, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nonconvex polygon identifier will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1126714