Generalization of features in a digital map

Details Generalization of features in a digital map Generalization of features in a digital map

2006-07-26

2010-12-28

Wu, Xiao M (Department: 2628)

Computer graphics processing and selective visual display system

Computer graphics processing

Shape generating

C345S442000, C345S443000, C340S995100, C701S208000

Reexamination Certificate

active

07859536

ABSTRACT:
Generalization of features in a digital map is enabled by performing a simplification of polylines. A set of chords between points on a polyline is selected such that each chord does not violate specified rules such as maximum distance from the original polyline. If a chord is acceptable, a node representing the chord is created, described by the start and end points of the chord. For pairs of nodes created, a transition from the first node to the second node is evaluated to determine whether it is acceptable. In one embodiment, a transition is acceptable if the absolute value of the angle formed by the chords is within a threshold angle from the angle formed by the original polyline at that point. If the transition is acceptable, a link between the two nodes is established. A least-cost path through the graph is chosen, and a simplified polyline is then generated.

REFERENCES:
patent: 5566292 (1996-10-01), Krembs
patent: 5893081 (1999-04-01), Poppen
patent: 6812925 (2004-11-01), Krishnan et al.
patent: 2003/0109984 (2003-06-01), Adachi
patent: 2005/0102097 (2005-05-01), Tanizaki et al.
patent: 2005/0209774 (2005-09-01), Finlay
patent: 2005/0244058 (2005-11-01), Gorbatov
Wu and Marquez , A non-self-intersection Douglas-Peucker algorithm, In Proceedings of the XVI Brazilian Symposium on Computer Graphics and Image Processing, pp. 60-66, Oct. 2003.
International Search Report and Written Opinion of the International Searching Authority, International application No. PCT/US06/29711, Mar. 10, 2008.
Dijkstra, E.W., “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik, 1959, pp. 269-271, vol. 1.
Douglas, David H., et al., “Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or its Caricature,” The Canadian Cartographer, 1973, pp. 112 -122, vol. 10, No. 2.
Lang, T., “Rules for robot draughtsmen,” Geographical Magazine, 1969, pp. 50-51, vol. 42.
PCT International Search Report and Written Opinion, PCT/US2008/072393, Nov. 3, 2008, 8 Pages.
Extended European Search Report, European Patent Application No. 06788966.7, May 3, 2010, 8 Pages.
McMaster, R., “Automated Line Generalization,” Cartographica, Jan. 1, 1987, pp. 74-111, vol. 24, No. 2, University of Toronto Press.

Affiliated with

Also associated with

Rating

Generalization of features in a digital map does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Generalization of features in a digital map, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generalization of features in a digital map will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4234785