Determining the convex hull of convex polygons with...

Details Determining the convex hull of convex polygons with... Determining the convex hull of convex polygons with...

2007-03-06

2007-03-06

Chauhan, Ulka (Department: 2628)

Computer graphics processing and selective visual display system

Computer graphics processing

Three-dimension

C345S420000, C715S863000

Reexamination Certificate

active

10438635

ABSTRACT:
The convex hull of two polygons having congruent corresponding angles with the same orientation can be determined by analyzing the relationship of each vertex of one of the polygons relative to its adjacent vertices. More particularly a line may be defined between a selected vertex on one of the polygons and its corresponding vertex on the other polygon. If the vertices adjacent to the selected vertex both fall on the same side of the line, then a line connecting the selected vertex with its corresponding vertex lies on the convex hull of the two polygons. If, on the other hand, the vertices adjacent to the selected vertex are located on different sides of the line, then the line connecting the selected vertex with its corresponding vertex does not lie on the convex hull.

REFERENCES:
patent: 5155813 (1992-10-01), Donoghue et al.
patent: 5434959 (1995-07-01), Von Ehr et al.
patent: 5548705 (1996-08-01), Moran et al.
patent: 5596692 (1997-01-01), Martin et al.
patent: 6628279 (2003-09-01), Schell et al.
Preparata et al., “Convex Hull of Finite Sets of Points in Two and Three Dimensions”, Communications of the ACM archive, vol. 20, Issue 2 (Feb. 1977), pp. 87-93.
Cheng et al., “Space-efficient Ray-shooting and Intersection Searching: Algorithms, Dynamization, and Applications”, Symposium on Discrete Algorithms archive, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, Pub 1991, pp. 7-16.
O. Bouattane et al., “A Fast Parallel Algorithm for Convex Hull Problem of Multi-Leveled Images,” Journal of Intelligent and Robotic Systems, 33: 285-299, 2002.
Z.Q. Wang et al., “An Optimal Real Time Algorithm for Determine the Convex Hull of a Set of Points in a Plane,” Computers Ind. Engng, vol. 35, Nos. 1-2 pp. 331-334, 1998.
J. Yamamoto, “Convex—Hull—A Pascal Program for Determining the Convex Hull for Planar Sets,” Computers & Geosciences, vol. 23, No. 7, pp. 725-738, 1997.
Guohua Cui et al., “A Clas of Optimal Algorithms for Determine the Convex Hull of a Set of Nodes in a Plane,” J. Computers, vol. 20, No. 4, Apr. 1997.
D. Rutovitz, “Efficient Processing of 2-D Images,” Medical Research Council, Edinburgh, pp. 229-253, 1990.
Z. Hussain, “A fast approximation to a convex hull,” Pattern Recognition Letters 8, pp. 289-294, Dec. 1988.
R. Miller et al., “Computational Geometry on a Mesh-Connected Computer,” IEEE, pp. 66-73, 1984.
D. Avis, “On the Complexity of Finding the Convex Hull of a Set of Points,” Discrete Applied Mathematics 4, pp. 81-86, 1982.
A. Yao, “A Lower Bound to Finding Convex Hulls,” Journal of the Association for Computing Machinery, vol. 28, No. 4, Oct. 1981, pp. 780-787.
S. Akl, “Two Remarks on a Convex Hull Algorithm,” Information Processing Letters, vol. 8, No. 2, Feb. 1979, pp. 108-109.
R.A. Jarvis, “On the Identification of the Convex Hull of a Finite Set of Points in the Plane,” Information Processing Letters 2, pp. 18-21, 1973.
H. Lee et al., “Determining in Linear Time the Minimum Area Convex Hull of Two Polygons,” IIE Transactions, vol. 20, No. 4, pp. 338-345, Dec. 1988.
R. Miller et al., “Efficient Parallel Convex Hull Algorithms,” IEEE Transactions on Computers, vol. 37, No. 12, pp. 1605-1618, Dec. 1988.
R. Miller et al., “Mesh Computer Algorithms for Computational Geometry,” IEEE Transactions on Computers, vol. 38, No. 3, pp. 321-340, Mar. 1989.
J. Erickson, “New Lower Bounds for Convex Hull Problems in Odd Dimensions,” IEE, pp. 1-16, 1999.
M. Ikhsan et al., “Automatic Generation of Haptic Aspect for a Polyhedron Via its Convex Hull,” IEE, pp. 548-551, 1996.

Affiliated with

Also associated with

Rating

Determining the convex hull of convex polygons with... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Determining the convex hull of convex polygons with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Determining the convex hull of convex polygons with... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3749752