Computer graphics processing and selective visual display system – Computer graphics processing – Shape generating
Reexamination Certificate
1999-10-01
2003-11-25
Brier, Jeffery (Department: 2676)
Computer graphics processing and selective visual display system
Computer graphics processing
Shape generating
Reexamination Certificate
active
06654015
ABSTRACT:
The file of this patent application includes a CD-ROM with a file named APPENDIX A.TXT, created Dec. 17, 2002, and having a size of 28,012 bytes, which is incorporated by reference. This file contains computer program listings referred to as Appendices A. Appendix A is a software program embodying aspects of the present invention. These programs were written for Microsoft Windows. Appendix A is a program that describes the geometric skeleton of a polygonal shape with respect to one of its sides according to the present invention.
COPYRIGHT NOTICE
This patent specification contains material that is subject to copyright protection. The copyright owner has no objection to the reproduction of this patent specification or related materials from associated patent office files for the purposes of review, but otherwise reserves all copyright whatsoever.
FIELD OF INVENTION
The present invention relates to polygons in general and in particular to the generation of geometric skeletons of polygonal shapes, such as character font outlines and shapes.
BACKGROUND OF INVENTION
The generation of a geometric skeleton is an important step in many image-processing tasks such as offset generation, character stroke generation, and artistic effects. For example, in character stroke generation, the geometric skeleton provides a medial axis transform associating points on the boundary with corresponding points on the other side of the stroke.
The publication “Medial Axis Transformation of a Planar Shape”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAM1-4, No. 4, July 1982, by D. T. Lee (hereinafter called Lee) discloses a method for computing a medial axis of a planar shape represented by an n-edge polygon. Lee defines the transformation as follows: given an object represented, say by a simple polygon G, the medial axis is the set of points {q} internal to G such that there are least two points on the object's boundary that are equidistant from {q} and are closest to {q}. Because of its shape, the medial axis of a figure is also called the skeleton or the symmetric axis of the figure. Specifically, Lee defines the skeleton S
p
for a polygonal shape P as a set of edges and nodes, where the edges are of the form of loci, and the nodes are the intersections points of these loci (locations in Sp that are closest to more than two points in P). The skeleton of a polygon is described in Lee as being made up of three types of loci. Namely, (1) the locus between two line segments, which is in this case a line segment, (2) the locus between a point and a line segment, which is in this case a parabolic segment, (3) the locus between two points, which is in this case a line. This method suffers from errors in calculating the skeleton, due to errors in floating point calculations, especially in calculating (2) above. Consequently, it is not possible to accurately describe a geometric skeleton in this fashion.
SUMMARY OF THE INVENTION
It is an object of the present invention to ameliorate one or more disadvantages of the prior art.
According to one aspect of the invention, there is provided a method of generating a component of a geometric skeleton of a polygon, said polygon comprising a plurality of interconnected line segments, the method comprising the step of: determining, for a current line segment of said plurality, a first point on a line perpendicular to said current line segment at a second point corresponding to a parameter value, wherein said first point is a point of a locus between said current line segment and one other of said line segments, which locus point is the closest locus point, on said line, to the current line segment of any locus point of said current line segment and any one of the line segments other than the current line segment, said first point forming a point of said component of said skeleton.
According to another aspect of the invention, there is provided a method of generating components of a geometric skeleton of a polygon, wherein said polygon comprises a plurality of line segments and one or more concave vertices, the method comprising the step of: determining, for each said concave vertex, a first point on a radial line from the current concave vertex, wherein said radial line has a corresponding parameter value and said first point is a point of a locus between said current concave vertex and a said line segment, which locus point is the closest locus point on said radial line of any locus point of said current concave vertex and any one of said line segments, said first point forming a point of said components of said skeleton.
According to still another aspect of the invention, there is provided a method of generating a geometric skeleton of a polygonal shape, the method comprising the steps of: determining a parameter value of an edge or concave vertex of the polygonal shape where the distance from said edge or concave vertex to a point of a locus between said edge or concave vertex and another edge of the polygonal shape is a minimum; and storing said parameter value and a label representative of said another edge having said minimum distance as a data signal representative of the geometric skeleton at said parameter value.
According to still another aspect of the invention, there is provided a method of generating a representation of components of a geometric skeleton of a polygon, wherein the polygon comprises a plurality of line segments, the method comprising the steps of: generating, for each said line segment (i) of the polygon, a list comprising a plurality of members { . . . ,(t′,N), . . . ,(t″,P), . . . }, where (t′,N) and (t″,P) are any members of the list, t′ and t″ are parameter values of a current line segment (i) and which are adjacent parameter values in the list, and N and P are said line segments of the polygon other than the current line segment (i), whereby a point of locus(i,N) on a line perpendicular to the current line segment (i) at the parameter value t′ forms one point of the skeleton and a point of locus(i,P) on a line perpendicular to the current line segment (i) at the parameter value t″ forms another point of the skeleton, and for any parameter value t′″ immediate t′ and t″ a point, being one of a point of locus (i,N) or a point of locus(i,P) on the line perpendicular to the current line segment (i) at the parameter value t′″, which is closest to the current line segment (i) forms another point of the skeleton; and storing said lists as a representation of said components of said skeleton.
According to still another aspect of the invention, there is provided a method of generating a representation of components of a geometric skeleton of a polygon, wherein the polygon comprises a plurality of line segments and one or more concave vertices, the method comprising the steps of: generating, for each concave vertex (i) of the polygon, a list comprising a plurality of members { . . . ,(&thgr;′,N), . . . ,(&thgr;″,P), . . . }, where (&thgr;′,N) and (&thgr;″,P) are any members of the list, &thgr;′ and &thgr;″ are parameter values of a current concave vertex (i) and which are adjacent parameter values in the list, and N and P are said line segments of the polygon, whereby a point of locus(i,N) on a radial line from the current concave vertex (i) at the parameter value &thgr;′ forms one point of the skeleton and a point of locus(i,P) on a radial line from the current concave vertex (i) at the parameter value &thgr;″ forms another point of the skeleton, and for any parameter value &thgr;′″ immediate &thgr;′ and &thgr;″ a point, being one of a point of locus (i,N) or a point of locus(i,P) on the radial line from the current concave vertex (i) at the parameter value &thgr;′″, which is closest to the current concave vertex (i) forms another point of the skeleton; and storing said lists as a representation of sa
Brier Jeffery
Cunningham G. F.
LandOfFree
Method and apparatus for generating a geometric skeleton of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for generating a geometric skeleton of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating a geometric skeleton of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3164879