Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2001-10-30
2004-11-02
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S428000
Reexamination Certificate
active
06812925
ABSTRACT:
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH
Not Applicable.
FIELD OF THE INVENTION
The present invention relates generally to data processing and, more particularly, to systems for displaying maps.
BACKGROUND OF THE INVENTION
As is known in the art, advances in satellite imaging techniques have provided the ability to acquire highly detailed geographical map models. Such models enable interactive visual exploration of massive data sets, much of which is spatial in nature, generated with respect to an underlying geographic domain. For example, geographic information systems deal with the problem of capture, storage and display of large amounts of data with spatial information, such as weather and elevation information. Large telecommunications networks are visualized over an underlying global map. Thus, one of the major challenges facing any interactive system for visualizing such data is the problem of rendering the underlying spatial domain, which could be a political or topographical map of a region, or even a three-dimensional terrain. Such map data can be extremely complex in its finest detail. For example the so-called Tiger data provided by the U.S. Census Bureau contains U.S. maps with a few hundred million vertices occupying over 30 GB of storage.
The maps created by known techniques are seldom optimized for rendering efficiency and can usually be replaced with far fewer primitives, e.g., vertices and chains, without any loss in visual fidelity. In order to further improve the rendering speed and quality, known systems typically compute several versions of these maps. More detailed versions can be used when the object is very close to the viewer, and are replaced with coarser representations as the object recedes. The level of refinement can be adapted in different areas depending on the viewing parameters, which is commonly referred to as view-dependent simplification strategy. In addition, conventional systems can utilize simplification algorithms that are static or dynamic depending upon whether the refinement is performed as a preprocessing step or as part of the rendering loop.
It would, therefore, be desirable to provide a map simplification system that overcomes the aforesaid and other disadvantages.
SUMMARY OF THE INVENTION
The present invention provides a map simplification system for interactively maintaining a planar subdivision, e.g., arrangement of polylines, at varying levels of detail that preserves the shape features of the region, e.g., the essential geometric and topological characteristics. The system provides scalability, real-time performance, and robustness in comparison to conventional geometric map simplification systems. While the invention is primarily shown and described in conjunction with map simplification, it is understood that the invention is applicable to systems in general in which relatively large amounts of data are displayed.
In one aspect of the invention, a system simplifies a map by generating voronoi diagrams for a plurality of non-intersecting chains that define the map and removing non-compliant shortcut segments based upon the voronoi diagrams. The system removes non-proximate shortcut segments based upon the voronoi diagrams. In one embodiment, the system determines shortest paths from the compliant, proximate segments to provide a simplified map.
REFERENCES:
patent: 5363478 (1994-11-01), Fiasconaro
patent: 5390291 (1995-02-01), Ohashi
patent: 5850229 (1998-12-01), Edelsbrunner et al.
patent: 5960118 (1999-09-01), Briskin et al.
patent: 6133921 (2000-10-01), Turkiyyah et al.
patent: 6256039 (2001-07-01), Krishnamurthy
patent: 6285372 (2001-09-01), Cowsar et al.
patent: 6560361 (2003-05-01), Collins
Varadarajan, “Approximating Monotone Polygonal Curves Using the Uniform Metric”, 1996, ACM 0-89791-804-5/96/05, pp. 311-318.*
Wang et al, “An optimal Algorithm for constructing the Delaunay triangulation of a set of line segments”, 1987 ACM 0-89791-231-4/87/0006/0223, pp. 223-232.*
Mithchell et al, “Minimum-Link Paths Among Obstacles in the plane”, 1990 ACM 0-89791-362-0/90/00006/063, pp. 63-72.*
Rajasekaran, “Optimal Parallel Randomized Algorithms for the Voronoi Diagram of Line segments in the plane and related problems”, 1994 ACM 0-89791-648-4/94/0006, pp. 57-66.*
Gold, “Map Generalization by Skeleton Retraction”, Dept. of Land Surveying and Geo-Informatics.*
Mustafa et al, “Hardware-Assisted View-dependent Map Simplication”, 2001, ACM 1-58113-357-X/01/0006, pp. 50-59.*
Canny et al, “Simplified Voronoi Diagrams”, 1987 ACM 0-89791-231-4/87/00006/0153, pp. 153-161.*
STorer et al, “Shortest PAths in the Plane with Polygonal Obstacles”, 1994 ACM 0004-5411/94/090-0982, pp. 982-1012.
Krishnan Shankar
Mustafa Nabil
Venkatasubramanian Suresh
AT&T Corp.
Daly, Crowley & Mofford LLP
Wallace Scott
Zimmerman Mark
LandOfFree
Map simplification system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Map simplification system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Map simplification system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3359318