Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
2004-12-06
2009-06-02
Shah, Kamini S (Department: 2128)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C701S212000, C701S014000, C701S208000, C701S003000, C701S211000
Reexamination Certificate
active
07542882
ABSTRACT:
A system and method for making computer-generated maps includes a different scale factor for each road in a route. The scale factors are used to optimize the route map against a target function that considers factors such as the number of false intersections in the route and the number of roads falling below a minimum length threshold. A refinement technique such as simulated annealing is used to find a solution to the target function. Each road in the scaled map is rendered to provide a finished product having the appearance of a hand-drawn map. The finished product includes context roads that intersect the main route but are not part of the main route. Furthermore, the hand-drawn map is optimized to the characteristics of the viewport used to visualize the map.
REFERENCES:
patent: 4796189 (1989-01-01), Nakayama et al.
patent: 4814989 (1989-03-01), Dobereiner et al.
patent: 4897792 (1990-01-01), Hosoi
patent: 5179329 (1993-01-01), Nishikawa et al.
patent: 5229941 (1993-07-01), Hattori
patent: 5345388 (1994-09-01), Kashiwazaki
patent: 5486822 (1996-01-01), Tenmoku et al.
patent: 5559707 (1996-09-01), DeLorme et al.
patent: 5689717 (1997-11-01), Pritt
patent: 5787383 (1998-07-01), Moroto et al.
patent: 5802492 (1998-09-01), DeLorme et al.
patent: 5848374 (1998-12-01), Wakabayashi et al.
patent: 5884218 (1999-03-01), Nimura et al.
patent: 5897604 (1999-04-01), Takahashi et al.
patent: 5925090 (1999-07-01), Poonsaengsathit
patent: 5945927 (1999-08-01), Nakayama et al.
patent: 5948040 (1999-09-01), DeLorme et al.
patent: 5951622 (1999-09-01), Nomura
patent: 5961572 (1999-10-01), Craport et al.
patent: 5974356 (1999-10-01), Doyle et al.
patent: 5978747 (1999-11-01), Craport et al.
patent: 6011494 (2000-01-01), Watanabe et al.
patent: 6021372 (2000-02-01), Harrington
patent: 6038498 (2000-03-01), Briffe et al.
patent: 6067502 (2000-05-01), Hayashida et al.
patent: 6101443 (2000-08-01), Kato et al.
patent: 6108555 (2000-08-01), Maloney et al.
patent: 6112141 (2000-08-01), Briffe et al.
patent: 6119066 (2000-09-01), Sugiura et al.
patent: 6125367 (2000-09-01), NA
patent: 6154219 (2000-11-01), Wiley et al.
patent: 6202026 (2001-03-01), Nimura et al.
patent: 6222583 (2001-04-01), Matsumura et al.
patent: 6278383 (2001-08-01), Endo et al.
patent: 6321158 (2001-11-01), DeLorme et al.
patent: 6324469 (2001-11-01), Okude et al.
patent: 6349261 (2002-02-01), Ohnishi et al.
patent: 6414696 (2002-07-01), Ellenby et al.
patent: 6421659 (2002-07-01), Nomura
patent: 6424911 (2002-07-01), Yamashita et al.
patent: 6424933 (2002-07-01), Agrawala et al.
patent: 6546336 (2003-04-01), Matsuoka
patent: 6565610 (2003-05-01), Wang et al.
patent: 6587787 (2003-07-01), Yokota
patent: 6680694 (2004-01-01), Kanockeart et al.
patent: 6707421 (2004-03-01), Drury et al.
patent: 6952661 (2005-10-01), Agrawala et al.
patent: 7076409 (2006-07-01), Agrawala et al.
patent: 7330787 (2008-02-01), Agrawala et al.
patent: 2005/0149303 (2005-07-01), Agrawala et al.
patent: 2005/0182604 (2005-08-01), Agrawala et al.
patent: 2005/0182605 (2005-08-01), Agrawala et al.
patent: 01916700.6-2218 (2007-08-01), None
patent: PCT/US01/08439 (2001-09-01), None
Shawn Edmondson, Jon Christensen, Merl Joe Marks, Stuart M. Schieber A General Cartographic Labeling Algorithm Cartographica, vol. 33, #4, Winter 1996.
S. Kirkpatrick, C. D. Gelatt, Jr., M. P. Vecchi Optimization by Simulated Annealing Science, May 13, 1983, vol. 220, No. 4598, pp. 671-680.
Herbert Freeman, Jeffrey Doerschler System for Dense Map Name Placement Communication of the ACM, Jan. 1992, vol. 35, No. 1.
Glassner, Copyright 1989 by Academic Press Ltd., “An Introduction to Ray Tracing,” Xerox PARC, 216-227.
Samet, Jun. 1990, “Applications of Spatial Data Structures,” Computer Graphics, Image Processing, and GIS, pp. 1-9.
Visvalingam et al., Jun. 1993, “Line Generalisation by Repeated Elimination of Points,” Cartographic Information Systems Research Group, University of Hull, pp. 46-51.
Cormen et al., 1990, “Introduction to Algorithms,” Chapter 17, pp. 329-355.
Van Keveld et al., “Point Set Labeling with Sliding Labels,” Proceedings of the 14thAnnual Symposium on Computational Geometry, pp. 337-346 (1998).
Rogers et al., “An Adaptive Interactive Agent for Route Advice,” DaimlerChrysler Research and Technology Center, May 1-5, 1999, pp. 198-205.
Haigh et al., “Route Planning by Analogy,” Proc. Of Intl. Conf. on Case-Based Reasoning, 1995, pp. 1-12.
Vinson, “Design Guidelines for Landmarks to Support Navigation in Virtual Environments,” ACM Conference on Human Factors in Computing Systems, pp. 278-285 (May 1999).
U.S. Office Action dated Jul. 13, 2007 cited in U.S. Appl. No. 11/073,399.
Barkowsky et al., 2000, “Schematizing Maps: Simplification of Geographic Shape by Discrete Curve Evolution,” Special Cognition II, LNAI 1849, pp. 41-53.
Carpendale et al., 1995, “Three-Dimensional Pliable Surfaces: For the Effective Presentatioin of Visual Information,” Proceedings of the ACM Symposium on User Interface Software and Technology, UIST 95:217-226.
Cormen et al., “Introduction to Algorithms,” Chapter 17, pp. 329-355.
Douglas et al., Dec. 1973, “Algorithms for the Reduction of the Number of Points Required to Represent a Digitized Line or its Caricature,” The Canadian Cartographer, vol. 10, No. 2, pp. 112-122.
Edmonsdsen et al., 1997, “A General Cartographic Labeling Algorithm,” Cartographics 33:12-23.
Glassner, “An Introduction to Ray Tracing,” Xerox PARC, 216-227.
Keahy, “The Generalized Detail-in-Context Problem, Information Visualization, Proceedings”, IEEE Symposium, pp. 45-52 (Oct. 19-20, 1998).
Kirkpatrick et al., “Optimization by Simulated Annealing,” Science, May 1983, vol. 22 No. 4598, pp. 671-680.
Markosian et al., “Real-Time Nonphotorealistic Rendering,” In: SIGGRAPH 97 Conference Proceedings (Aug. 1997), pp. 415-420.
Mehta et al., “The Road Best Traveled,” Geo Info Systems, Mar. 1999, vol. 9, Issue 3, pp. 36-39.
Michaelwicz et al., 2000, “How to Solve It: Modern Heuristics,” pp. 125-134.
Ramer, 1972, “An Interactive Procedure for the Polygonal Approximation of Plane Curves,” Computer Graphics and Image Processing, vol. 1, pp. 244-356.
Rayson, “Aggregate Towers: Sale Sensitive Visualization and Decluttering of Geospatial Data,” IEEE 1999 Symposium on Information Visualization, 1999, pp. 92-99, 149.
Sakar et al., “Graphical Fisheye Views,” Communications of the ACM, 1994, vol. 37, Issue 12, pp. 73-83.
Samet, “Applications of Spatial Data Structures,” Computer Graphics, Image Processing, and GIS, pp. 1-9.
Seligman and Feiner, 1991, “Automated Generation of Intent-Based 3D Illustrations,” Computer Graphics 25(4): 123-132.
Visvalingam et al., “Line Generalisation by Repeated Elimination of Points,” Cartographic Information Systems Research Group, University of Hull, pp. 46-51.
U.S. Office Action dated Dec. 31, 2007, cited in U.S. Appl. No. 11/073,399.
Notice of Allowance dated Nov. 12, 2008, cited in U.S. Appl. No. 11/005,862.
Agrawala Maneesh
Stolte Chris
Luu Cuong V
Merchant & Gould P.C.
Microsoft Corporation
Shah Kamini S
LandOfFree
System and method for abstracting and visualizing a route 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 System and method for abstracting and visualizing a route map, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for abstracting and visualizing a route map will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4126774