Labeling graphical features of drawings

Details Labeling graphical features of drawings Labeling graphical features of drawings

1996-11-01

2000-07-18

Jankus, Almis R.

Computer graphics processing and selective visual display system

Computer graphics processing

Graph generating

G06T 700

Patent

active

060914246

ABSTRACT:
A method is provided for automated placement of labels for a given graph layout or map. Even though in practice a label is usually associated with a line (edge), point (node) or area, this method can be extended to produce labeling solution for any graphical feature with explicit geometric representation (in two or three dimensions). This method first finds a labeling solution for a set of graphical features G by eliminating a subset of the set of potential label placements for any member of G, and reducing the labeling problem to a maximum matching problem of a bipartite graph. Next, if there are graphical features in G that have no label placement assigned to them yet, a backtracking algorithm may be used to improve the space available for the labeled graphical features. It may be shown that the labeling problem is NP-hard if any graphical feature in G is a line or point. As a result, the GFLP problem cannot be solved in polynomial time, but requires the application of well-devised heuristics.

REFERENCES:
patent: 5450535 (1995-09-01), North
patent: 5684940 (1997-11-01), Freeman et al.
Christensen, et al., "An Empirical Study of Algorithms for Point-Feature Label Placement", ACM Trans. on Graphics, vol. 14, No. 3, pp. 1-23 (1995).
Kakoulis, et al., "On the Edge Label Placement Problem", Proc. 1996 International Symposium on Graph Drawing (GD '96), Lecture Notes in Computer Science, vol. 1190, S. North, editor, pp. 241-256 (1997).
van Roessel, "An Algorithm for Locating Candidate Labeling Boxes Within a Polygon", The American Cartographer, vol. 16, No. 3, pp. 201-209 (1989).
Wagner, et al., "Map Labeling Heuristics: Provably Good and Practically Useful", Proceedings of the 11th Annual ACM Symposium on Computational Geometry, pp. 109-118 (1995).
Zoraster, "Positioning Large Labels Inside Small Polygons", Landmark, Canada.TXT, pp. 1-9 (1994).
Zoraster, "The Solution of Large 0-1 Integer Programming Problems Encountered in Automated Cartography", Operations Research, vol. 38, No. 5, pp. 752-759 (1990).

Affiliated with

Also associated with

Rating

Labeling graphical features of drawings does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Labeling graphical features of drawings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Labeling graphical features of drawings will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2041928