Warping geometric objects

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
97Forward
Citations 
0
Petitions 
2
Assignments
First Claim
1. A computer implemented method for forming a first set of geometric objects, based on a second set of geometric objects and a third set of geometric objects, wherein said second set of geometric objects contains a second set of matching points and said third set of geometric objects contains a third set of matching points, wherein each matching point in said second set of matching points corresponds to a matching point in said third set of matching points, said method comprising the steps of:
 (a) identifying matching points in said second set of matching points and corresponding matching points in said third set of matching points that have potential for causing topology deviations in the first set of geometric objects; and
(b) transforming points in said second set of geometric objects to obtain points in said first set of geometric objects, based on relationships between corresponding matching points in said second set of matching points and said third set of matching points other than said matching points identified in said step (a).
2 Assignments
0 Petitions
Accused Products
Abstract
A system is disclosed for warping models made from geometric objects, such as electronic maps, to correct local distortions in the models without compromising model topology. A set of transformation functions are derived from relationships between points in a first model that match points in a second model. The transformation functions are then applied to the points in the first model to generate a new model with reduced distortion. In order to provide for reducing local distortions, warping is applied to selected corresponding regions of the first model and the second model by triangulating these regions and generating transformation functions for each corresponding pair of triangles. Topology preservation is achieved by identifying matching points in the first model and the second model that have a potential for causing topology deviations. Such matching points are then excluded from the process of developing transformation equations to be used in the warping process. Matching points with potential for causing topology deviations are identified by triangulating matching points in the selected regions of the first model and the second model and analyzing the resulting triangles.
108 Citations
View as Search Results
GPSgenerated traffic information  
Patent #
US 7,880,642 B2
Filed 06/10/2009

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Triangle Software LLC

Mobile Device and Geographic Information System Background and Summary of the Related Art  
Patent #
US 20110124351A1
Filed 12/15/2010

Current Assignee
Intel Corporation

Sponsoring Entity
Intel Corporation

BIASING OF SEARCH RESULT CLUSTERING TO ENSURE MORE EFFECTIVE POINT OF INTEREST (POI) TARGETING  
Patent #
US 20110166957A1
Filed 07/09/2010

Current Assignee
Oath Inc.

Sponsoring Entity
Oath Inc.

Mobile device and geographic information system background and summary of the related art  
Patent #
US 8,023,962 B2
Filed 06/11/2007

Current Assignee
Intel Corporation

Sponsoring Entity
IPOINTER INC.

Mobile device and geographic information system background and summary of the related art  
Patent #
US 8,060,112 B2
Filed 03/04/2009

Current Assignee
Intel Corporation

Sponsoring Entity
IPOINTER INC.

System and method for provisioning a vehicle interface module  
Patent #
US 7,818,098 B2
Filed 12/19/2006

Current Assignee
Spireon Incorporated

Sponsoring Entity
Inilex Incorporated

Gesture Based Interaction with Traffic Data  
Patent #
US 20100333045A1
Filed 09/14/2010

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Uber Technologies Inc.

Biasing of search result clustering to ensure more effective point of interest (POI) targeting  
Patent #
US 7,761,350 B1
Filed 08/16/2006

Current Assignee
Oath Inc.

Sponsoring Entity
AOL Inc.

System and Method for Exploring 3D Scenes by Pointing at a Reference Object  
Patent #
US 20100306707A1
Filed 12/22/2009

Current Assignee
INTELLIGENT SPATIAL TECHNOLOGIES INC.

Sponsoring Entity
INTELLIGENT SPATIAL TECHNOLOGIES INC.

Modifying a path in a drawing  
Patent #
US 7,646,386 B2
Filed 04/19/2005

Current Assignee
Adobe Inc.

Sponsoring Entity
Adobe Systems Incorporated

MAP DISPLAY DEVICE  
Patent #
US 20100309227A1
Filed 02/18/2008

Current Assignee
Mitsubishi Electric Corporation

Sponsoring Entity
Mitsubishi Electric Corporation

System and Method for Initiating Actions and Providing Feedback by Pointing at Object of Interest  
Patent #
US 20100303339A1
Filed 12/22/2009

Current Assignee
INTELLIGENT SPATIAL TECHNOLOGIES INC.

Sponsoring Entity
INTELLIGENT SPATIAL TECHNOLOGIES INC.

Controlling a ThreeDimensional Virtual Broadcast Presentation  
Patent #
US 20100225643A1
Filed 03/04/2009

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Uber Technologies Inc.

Image enhancement method and system for fiducialless tracking of treatment targets  
Patent #
US 7,840,093 B2
Filed 12/15/2008

Current Assignee
Accuray Incorporated

Sponsoring Entity
Accuray Incorporated

Touch Screen Based Interaction with Traffic Data  
Patent #
US 20100312462A1
Filed 08/20/2010

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Uber Technologies Inc.

System and Method for Linking RealWorld Objects and Object Representations by Pointing  
Patent #
US 20100303293A1
Filed 12/22/2009

Current Assignee
IPOINTER INC.

Sponsoring Entity
IPOINTER INC.

Storage medium storing animation image generating program  
Patent #
US 7,477,253 B2
Filed 05/20/2003

Current Assignee
SEGA Corporation

Sponsoring Entity
SEGA Corporation

IMAGE FORMING APPARATUS, INFORMATION PROCESSING APPARATUS AND DISPLAY CONTROL METHOD  
Patent #
US 20090015569A1
Filed 11/27/2007

Current Assignee
Fuji Xerox Company Limited

Sponsoring Entity
Fuji Xerox Company Limited

System and method for predicting travel time for a travel route  
Patent #
US 7,508,321 B2
Filed 08/15/2006

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Triangle Software LLC

Assigning region attributes in a drawing  
Patent #
US 7,502,028 B1
Filed 04/19/2005

Current Assignee
Adobe Inc.

Sponsoring Entity
Adobe Systems Incorporated

Image enhancement method and system for fiducialless tracking of treatment targets  
Patent #
US 7,522,779 B2
Filed 06/30/2004

Current Assignee
Accuray Incorporated

Sponsoring Entity
Accuray Incorporated

IMAGE ENHANCEMENT METHOD AND SYSTEM FOR FIDUCIALLESS TRACKING OF TREATMENT TARGETS  
Patent #
US 20090091567A1
Filed 12/15/2008

Current Assignee
Accuray Incorporated

Sponsoring Entity
Accuray Incorporated

GPSgenerated traffic information  
Patent #
US 7,557,730 B2
Filed 05/21/2007

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Triangle Software LLC

METHODS AND SYSTEMS FOR USER CONFIGURABLE EMBEDDED TELEMATICS SERVICE ARCHITECTURE  
Patent #
US 20090248237A1
Filed 03/31/2008

Current Assignee
Inilex Incorporated

Sponsoring Entity
Inilex Incorporated

Assigning subpath attributes in a drawing  
Patent #
US 7,633,504 B2
Filed 07/03/2007

Current Assignee
Adobe Inc.

Sponsoring Entity
Adobe Systems Incorporated

GPSGenerated Traffic Information  
Patent #
US 20090309758A1
Filed 06/10/2009

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Uber Technologies Inc.

Image segmentation for DRR generation and image registration  
Patent #
US 20080037843A1
Filed 08/11/2006

Current Assignee
Accuray Incorporated

Sponsoring Entity
Accuray Incorporated

GPSGenerated Traffic Information  
Patent #
US 20080109153A1
Filed 05/21/2007

Current Assignee
Uber Technologies Inc.

Sponsoring Entity


Traffic routing based on segment travel time  
Patent #
US 7,375,649 B2
Filed 08/24/2006

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Triangle Software LLC

SYSTEM AND METHOD FOR PROVISIONING A VEHICLE INTERFACE MODULE  
Patent #
US 20080147245A1
Filed 12/19/2006

Current Assignee
Spireon Incorporated

Sponsoring Entity


Mobile geographic information system and method  
Patent #
US 20080162032A1
Filed 06/30/2006

Current Assignee
IPOINTER INC.

Sponsoring Entity


DRR generation using a nonlinear attenuation model  
Patent #
US 20080159612A1
Filed 03/05/2008

Current Assignee
Gopinath Kuduvalli, Fu Dongshan

Sponsoring Entity
Gopinath Kuduvalli

System and method for the selection of a unique geographic feature  
Patent #
US 7,418,341 B2
Filed 09/12/2005

Current Assignee
IPOINTER INC.

Sponsoring Entity
INTELLIGENT SPATIAL TECHNOLOGIES

Motion field generation for nonrigid image registration  
Patent #
US 7,426,318 B2
Filed 06/30/2004

Current Assignee
Accuray Incorporated

Sponsoring Entity
Accuray Incorporated

SYSTEM AND METHOD FOR THE SELECTION OF A UNIQUE GEOGRAPHIC FEATURE  
Patent #
US 20080262723A1
Filed 06/30/2008

Current Assignee
IPOINTER INC.

Sponsoring Entity
IPOINTER INC.

Transfer of motion between animated characters  
Patent #
US 20080303831A1
Filed 07/22/2008

Current Assignee
Autodesk Inc.

Sponsoring Entity
Autodesk Inc.

Traffic routing based on segment travel time  
Patent #
US 20070038362A1
Filed 08/24/2006

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Uber Technologies Inc.

System and method for the selection of a unique geographic feature  
Patent #
US 20070061072A1
Filed 09/12/2005

Current Assignee
IPOINTER INC.

Sponsoring Entity
IPOINTER INC.

Assigning subpath attributes in a drawing  
Patent #
US 20070252844A1
Filed 07/03/2007

Current Assignee
Adobe Inc.

Sponsoring Entity
Adobe Inc.

Image enhancement method and system for fiducialless tracking of treatment targets  
Patent #
US 20060002615A1
Filed 06/30/2004

Current Assignee
Accuray Incorporated

Sponsoring Entity
Accuray Incorporated

Motion field generation for nonrigid image registration  
Patent #
US 20060002632A1
Filed 06/30/2004

Current Assignee
Accuray Incorporated

Sponsoring Entity
Accuray Incorporated

Method for solving frequency, frequency distribution and sequencematching problems using multidimensional attractor tokens  
Patent #
US 7,061,491 B2
Filed 06/03/2002

Current Assignee
OMNIGON TECHNOLOGIES LTD.

Sponsoring Entity
OMNIGON TECHNOLOGIES LTD.

Migrating spatial data between databases  
Patent #
US 20060117034A1
Filed 12/01/2004

Current Assignee
Autodesk Inc.

Sponsoring Entity
Autodesk Inc.

Modifying a path in a drawing  
Patent #
US 20060232603A1
Filed 04/19/2005

Current Assignee
Adobe Inc.

Sponsoring Entity
Adobe Inc.

Method for solving waveform sequencematching problems using multidimensional attractor tokens  
Patent #
US 20050165566A1
Filed 09/27/2002

Current Assignee
OMNIGON TECHNOLOGIES LTD.

Sponsoring Entity
OMNIGON TECHNOLOGIES LTD.

Method of detecting, interpreting, recognizing, identifying and comparing ndimensional shapes, partial shapes, embedded shapes and shape collages using multidimensional attractor tokens  
Patent #
US 20040037474A1
Filed 09/27/2002

Current Assignee
OMNIGON TECHNOLOGIES LTD.

Sponsoring Entity
OMNIGON TECHNOLOGIES LTD.

Storage medium storing animation image generating program  
Patent #
US 20040085320A1
Filed 05/20/2003

Current Assignee
SEGA Corporation

Sponsoring Entity
SEGA Corporation

Method of detecting, interpreting, recognizing, identifying and comparing ndimensional shapes, partial shapes, embedded shapes and shape collages using multidimensional attractor tokens  
Patent #
US 6,747,643 B2
Filed 09/27/2002

Current Assignee
OMNIGON TECHNOLOGIES LTD.

Sponsoring Entity
OMNIGON TECHNOLOGIES LTD.

Method for solving frequency, frequency distribution and sequencematching problems using multidimensional attractor tokens  
Patent #
US 20040107059A1
Filed 06/03/2002

Current Assignee
OMNIGON TECHNOLOGIES LTD.

Sponsoring Entity
OMNIGON TECHNOLOGIES LTD.

Mobile device and geographic information system background and summary of the related art  
Patent #
US 20070288196A1
Filed 06/11/2007

Current Assignee
Intel Corporation

Sponsoring Entity
Intel Corporation

System and method for linking realworld objects and object representations by pointing  
Patent #
US 8,184,858 B2
Filed 12/22/2009

Current Assignee
IPOINTER INC.

Sponsoring Entity
IPOINTER INC.

METHOD OF SIMULATING DEFORMABLE OBJECT USING GEOMETRICALLY MOTIVATED MODEL  
Patent #
US 20120218271A1
Filed 05/14/2012

Current Assignee
Heidelberger Bruno Heinz, MllerFischer Matthais Heinz, Markus Gross, Teschner Matthias

Sponsoring Entity
Heidelberger Bruno Heinz, MllerFischer Matthais Heinz, Markus Gross, Teschner Matthias

METHOD OF SIMULATING DEFORMABLE OBJECT USING GEOMETRICALLY MOTIVATED MODEL  
Patent #
US 20120232854A1
Filed 05/14/2012

Current Assignee
Heidelberger Bruno Heinz, MllerFischer Matthais Heinz, Markus Gross, Teschner Matthias

Sponsoring Entity
Heidelberger Bruno Heinz, MllerFischer Matthais Heinz, Markus Gross, Teschner Matthias

GPSgenerated traffic information  
Patent #
US 8,358,222 B2
Filed 12/13/2010

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Mobile image search and indexing system and method  
Patent #
US 8,483,519 B2
Filed 12/30/2009

Current Assignee
INTELLIGENT SPATIAL TECHNOLOGIES INC.

Sponsoring Entity
INTELLIGENT SPATIAL TECHNOLOGIES INC.

System and method for linking realworld objects and object representations by pointing  
Patent #
US 8,494,255 B2
Filed 03/06/2012

Current Assignee
IPOINTER INC.

Sponsoring Entity
IPOINTER INC.

Method for choosing a traffic route  
Patent #
US 8,531,312 B2
Filed 07/30/2012

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Mobile geographic information system and method  
Patent #
US 8,538,676 B2
Filed 06/30/2006

Current Assignee
IPOINTER INC.

Sponsoring Entity
IPOINTER INC.

System and method for the selection of a unique geographic feature  
Patent #
US 8,560,225 B2
Filed 06/30/2008

Current Assignee
IPOINTER INC.

Sponsoring Entity
IPOINTER INC.

Generating visual information associated with traffic  
Patent #
US 8,564,455 B2
Filed 07/30/2012

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Controlling a threedimensional virtual broadcast presentation  
Patent #
US 8,619,072 B2
Filed 03/04/2009

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Biasing of search result clustering to ensure more effective point of interest (POI) targeting  
Patent #
US 8,645,235 B2
Filed 07/09/2010

Current Assignee
Oath Inc.

Sponsoring Entity
AOL Inc.

System and method for delivering departure notifications  
Patent #
US 8,660,780 B2
Filed 12/09/2011

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Method of simulating deformable object using geometrically motivated model  
Patent #
US 8,666,713 B2
Filed 05/14/2012

Current Assignee
NVIDIA Corporation

Sponsoring Entity
NVIDIA Corporation

System and method for initiating actions and providing feedback by pointing at object of interest  
Patent #
US 8,675,912 B2
Filed 12/22/2009

Current Assignee
INTELLIGENT SPATIAL TECHNOLOGIES INC.

Sponsoring Entity
INTELLIGENT SPATIAL TECHNOLOGIES INC.

BIASING OF SEARCH RESULT CLUSTERING TO ENSURE MORE EFFECTIVE POINT OF INTEREST (POI) TARGETING  
Patent #
US 20140114566A1
Filed 12/23/2013

Current Assignee
AOL Inc.

Sponsoring Entity
AOL Inc.

Crowd sourced traffic reporting  
Patent #
US 8,718,910 B2
Filed 11/14/2011

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

System for providing traffic data and driving efficiency data  
Patent #
US 8,725,396 B2
Filed 05/18/2012

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

System and method for exploring 3D scenes by pointing at a reference object  
Patent #
US 8,745,090 B2
Filed 12/22/2009

Current Assignee
INTELLIGENT SPATIAL TECHNOLOGIES INC.

Sponsoring Entity
INTELLIGENT SPATIAL TECHNOLOGIES INC.

Estimating time travel distributions on signalized arterials  
Patent #
US 8,781,718 B2
Filed 01/28/2013

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

GPS generated traffic information  
Patent #
US 8,786,464 B2
Filed 01/22/2013

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Mobile image search and indexing system and method  
Patent #
US 8,873,857 B2
Filed 07/08/2013

Current Assignee
INTELLIGENT SPATIAL TECHNOLOGIES INC.

Sponsoring Entity
INTELLIGENT SPATIAL TECHNOLOGIES INC.

Method of simulating deformable object using geometrically motivated model  
Patent #
US 8,886,501 B2
Filed 05/14/2012

Current Assignee
NVIDIA Corporation

Sponsoring Entity
NVIDIA Corporation

Reshaping interfaces using contentpreserving warps  
Patent #
US 8,887,073 B2
Filed 12/01/2010

Current Assignee
Empire Technology Development LLC

Sponsoring Entity
Empire Technology Development LLC

Mobile device and geographic information system background and summary of the related art  
Patent #
US 8,929,911 B2
Filed 12/15/2010

Current Assignee
Intel Corporation

Sponsoring Entity
Intel Corporation

Transfer of motion between animated characters  
Patent #
US 8,952,969 B2
Filed 07/22/2008

Current Assignee
Autodesk Inc.

Sponsoring Entity
Autodesk Inc.

Method for choosing a traffic route  
Patent #
US 8,958,988 B2
Filed 09/10/2013

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Touch screen based interaction with traffic data  
Patent #
US 8,982,116 B2
Filed 08/20/2010

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Gesture based interaction with traffic data  
Patent #
US 9,046,924 B2
Filed 09/14/2010

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Method for predicting a travel time for a traffic route  
Patent #
US 9,070,291 B2
Filed 09/17/2013

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Generating visual information associated with traffic  
Patent #
US 9,082,303 B2
Filed 09/17/2013

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

System and method for delivering departure notifications  
Patent #
US 9,127,959 B2
Filed 01/14/2014

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Mobile device and geographic information system background and summary of the related art  
Patent #
US 9,237,420 B2
Filed 01/02/2015

Current Assignee
Intel Corporation

Sponsoring Entity
Intel Corporation

Estimating time travel distributions on signalized arterials  
Patent #
US 9,293,039 B2
Filed 07/03/2014

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

GPS generated traffic information  
Patent #
US 9,368,029 B2
Filed 07/09/2014

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

System for providing traffic data and driving efficiency data  
Patent #
US 9,390,620 B2
Filed 05/12/2014

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Pelmorex Canada Inc.

Method for predicting a travel time for a traffic route  
Patent #
US 9,401,088 B2
Filed 04/21/2015

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Muddy River Series 97 of Allied Security Trust I

Controlling a threedimensional virtual broadcast presentation  
Patent #
US 9,448,690 B2
Filed 12/09/2013

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Muddy River Series 97 of Allied Security Trust I

Method for choosing a traffic route  
Patent #
US 9,489,842 B2
Filed 02/17/2015

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Muddy River Series 97 of Allied Security Trust I

System for providing traffic data and driving efficiency data  
Patent #
US 9,547,984 B2
Filed 07/11/2016

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Muddy River Series 97 of Allied Security Trust I

GPS generated traffic information  
Patent #
US 9,602,977 B2
Filed 06/13/2016

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Muddy River Series 97 of Allied Security Trust I

Generating visual information associated with traffic  
Patent #
US 9,640,073 B2
Filed 07/08/2015

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Muddy River Series 97 of Allied Security Trust I

System and method for delivering departure notifications  
Patent #
US 9,644,982 B2
Filed 09/04/2015

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Uber Technologies Inc.

Mobile device and geographic information system background and summary of the related art  
Patent #
US 9,913,098 B2
Filed 01/08/2016

Current Assignee
Intel Corporation

Sponsoring Entity
Intel Corporation

Estimating time travel distributions on signalized arterials  
Patent #
US 10,223,909 B2
Filed 10/18/2013

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Uber Technologies Inc.

Controlling a threedimensional virtual broadcast presentation  
Patent #
US 10,289,264 B2
Filed 09/20/2016

Current Assignee
Uber Technologies Inc.

Sponsoring Entity
Uber Technologies Inc.

Stack of maps  
Patent #
US 10,295,347 B2
Filed 09/04/2015

Current Assignee
Urban Engines Inc.

Sponsoring Entity
Google LLC

Interleaved segmental method for handwriting recognition  
Patent #
US 5,878,164 A
Filed 10/08/1997

Current Assignee
Lucent Technologies Inc.

Sponsoring Entity
Lucent Technologies Inc.

Method of recognizing objects within twodimensional and threedimensional images  
Patent #
US 6,026,189 A
Filed 11/13/1997

Current Assignee
National Research Council Canada

Sponsoring Entity
National Research Council Canada

Method and apparatus for performing local to global multiframe alignment to construct mosaic images  
Patent #
US 6,078,701 A
Filed 05/29/1998

Current Assignee
Sarnoff Corporation

Sponsoring Entity
Sarnoff Corporation

Method and system for rendering graphical objects to image chunks  
Patent #
US 5,864,342 A
Filed 06/27/1996

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity


Vehicleroute computing apparatus  
Patent #
US 5,845,228 A
Filed 09/16/1996

Current Assignee
Mitsubishi Electric Corporation

Sponsoring Entity
Mitsubishi Electric Corporation

Apparatus and method for geometric morphing  
Patent #
US 5,850,229 A
Filed 12/15/1995

Current Assignee
3D Systems

Sponsoring Entity
RAINDROP GEOMAGIC INC.

Optimum route determination  
Patent #
US 5,486,822 A
Filed 05/26/1994

Current Assignee
Sumitomo Electric Industries Limited

Sponsoring Entity
Sumitomo Electric Industries Limited

Automatic chainbased conflation of digital maps  
Patent #
US 5,546,107 A
Filed 04/05/1994

Current Assignee
Tele Atlas North America

Sponsoring Entity
Etak Inc.

Method for modelling a surface and device for implementing same  
Patent #
US 5,465,323 A
Filed 05/20/1991

Current Assignee
Cggveritas Services SA

Sponsoring Entity
ASSOCIATION SCIENTIFIQUE POUR LA GEOLOGIE ET SES APPLICATIONS

Method and apparatus for generating a mesh for finite element analysis  
Patent #
US 4,912,664 A
Filed 02/01/1988

Current Assignee
Mentor Graphics Corporation

Sponsoring Entity
Mentor Graphics Corporation

Image describing apparatus  
Patent #
US 4,805,127 A
Filed 03/11/1986

Current Assignee
Mitsubishi Electric Corporation

Sponsoring Entity
Mitsubishi Electric Corporation

42 Claims
 1. A computer implemented method for forming a first set of geometric objects, based on a second set of geometric objects and a third set of geometric objects, wherein said second set of geometric objects contains a second set of matching points and said third set of geometric objects contains a third set of matching points, wherein each matching point in said second set of matching points corresponds to a matching point in said third set of matching points, said method comprising the steps of:
 (a) identifying matching points in said second set of matching points and corresponding matching points in said third set of matching points that have potential for causing topology deviations in the first set of geometric objects; and
(b) transforming points in said second set of geometric objects to obtain points in said first set of geometric objects, based on relationships between corresponding matching points in said second set of matching points and said third set of matching points other than said matching points identified in said step (a).  View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
 (a) identifying matching points in said second set of matching points and corresponding matching points in said third set of matching points that have potential for causing topology deviations in the first set of geometric objects; and
 15. A processor readable storage medium having processor readable code embodied on said processor readable storage medium, said processor readable code for programming a processor to perform a method for forming a first set of geometric objects, based on a second set of geometric objects and a third set of geometric objects, wherein said second set of geometric objects contains a second set of matching points and said third set of geometric objects contains a third set of matching points, wherein each matching point in said second set of matching points corresponds to a matching point in said third set of matching points, said method comprising the steps of:
 (a) identifying matching points in said second set of matching points and corresponding matching points in said third set of matching points that have potential for causing topology deviations in the first set of geometric objects; and
(b) transforming points in said second set of geometric objects to obtain points in said first set of geometric objects, based on relationships between corresponding matching points in said second set of matching points and said third set of matching points other than said matching points identified in said step (a).  View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28)
 (a) identifying matching points in said second set of matching points and corresponding matching points in said third set of matching points that have potential for causing topology deviations in the first set of geometric objects; and
 29. An apparatus for forming a first set of geometric objects, based on a second set of geometric objects and a third set of geometric objects, wherein said second set of geometric objects contains a second set of matching points and said third set of geometric objects contains a third set of matching points, wherein each matching point in said second set of matching points corresponds to a matching point in said third set of matching points, said apparatus comprising:
 a processor; and
a processor readable storage medium, in communication with said processor, said processor readable storage medium storing code for programming said processor to perform the steps of;
(a) identifying matching points in said second set of matching points and corresponding matching points in said third set of matching points that have potential for causing topology deviations in the first set of geometric objects; and
(b) transforming points in said second set of geometric objects to obtain points in said first set of geometric objects, based on relationships between corresponding matching points in said second set of matching points and said third set of matching points other than said matching points identified in said step (a).  View Dependent Claims (30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42)
 a processor; and
1 Specification
This Application is related to the following Application:
Matching Geometric Objects, by Hongche Liu and Shyam Kuttikkad, Ser. No. 09/176,243, filed Oct. 21, 1998.
The abovecited Application is incorporated herein by reference.
BACKGROUND OF THE INVENTION1. Field of Invention
The present invention is directed toward the field of warping sets of geometric objects.
2. Description of Related Art
Physical areas are often modeled using geometric objects. Examples of such physical areas include a geographic region and a building's floor plan. One example of a model using twodimensional geometric objects is a map of a geographic region, such as a city.
<FGREF>FIG. 1</FGREF> illustrates a map that is formed by a set of geometric objects. The objects in <FGREF>FIG. 1</FGREF> include points 6070, arcs 8091, and polygons 5051. Each arc 8091 represents a road and is bounded at each of its ends by a point. For example, arc 80 is bounded at one end by point 60 and at another end by point 62. Each arc can be cobounded by one or two polygons. For example, arc 86 is cobounded by polygons 50 and 51, while arc 85 is only cobounded by polygon 50. Each polygon 50 and 51 is formed by a set of arcs that define the boundary of the polygon. For example, polygon 50 is defined by boundary arcs 81, 82, 83, 84, 85, and 86.
Different models of the same physical area often provide different quality details about the area. Differences between models of the same area can occur, because models can be distorted, so that all the features in the model are not depicted in their true positions. Such distortions are often localized, with different regions of the model being distorted differently. In paper models, distortion can be caused by paper stretching, folding, and scaling. In electronic models, distortion can be caused when the model is transformed into digital form.
By repositioning different models of the same area, a more accurate new model can be created. <FGREF>FIG. 2</FGREF> illustrates a map 100 of an area that is neither very smooth nor accurate. <FGREF>FIG. 3</FGREF> shows a more accurate map 10 of the same area as map 100. The differences between maps 100 and 10 are illustrated in <FGREF>FIG. 4</FGREF>, which shows an overlay of maps 100 and 110. A repositioning process can be performed to utilize the details of both maps 100 and 110 to obtain an improved new map.
The use of repositioning is particularly beneficial and practical is generating electronic maps. There are often many different maps available for a particular region. By making use of a computer to reposition the many maps that are available for a region, a very accurate new map can be generated in a time efficient and cost efficient manner.
One known method for repositioning two models is to warp one model based on the weighted sum of local displacements between points in the two models. In this method, a set of matching points in the models is obtained for selected regions of the models. Displacements between matching points in each selected region are then employed to generate a warping transformation for the selected region. The warping transformation is then used to transform points in one of the models into points in a new model.
However, such a method is inadequate, because it does not provide for maintaining the topology of the original models in the new model. Topology refers to the relative connections and orientations of geometric objects in the model, and its preservation is critical to ensuring the accuracy of the new model. For example, if topology is not preserved, arc intersections which do not exist in either of the original models may be inserted into the new model.
In order to better maintain topology, modelbased warping can be employed. One known method of such warping includes the creation of a global transformation model that provides for transforming all of the points in a model into points in a new model. In such a method, all matching points from two existing models are employed to determine parameters for the global transformation model using numerical analysis, such as least mean squares techniques. However, this global approach does not provide for eliminating local distortions, which constitute many of the distortions that are encountered.
Accordingly, there is a need for a warping process that can be applied to models to correct local distortions without compromising topology.
SUMMARY OF THE INVENTIONThe present invention, roughly described, provides for warping models made from geometric objects, such as electronic maps, to correct local distortions in the models without compromising model topology. The warping is performed by using a set of transformation functions that are derived from relationships between points in a first model that match points in a second model with more accurate positioning. The transformation functions are applied to the points in the first model to generate a new model with reduced distortion.
In order to provide for reducing local distortions, warping is applied to selected corresponding regions of the first model and the second model by triangulating these regions and generating transformation functions for each corresponding pair of triangles. Topology preservation is achieved by identifying matching points in the first model and the second model that have a potential for causing topology deviations. Such matching points are then excluded from the process of developing transformation equations to be used in the warping process.
Matching points with potential for causing topology deviations are identified by triangulating matching points in the selected regions of the first model and the second model and analyzing the resulting triangles. A matching point is identified as having potential for causing topology deviations, if it is a vertex in a triangle in one model that has an inverted corresponding triangle in the other model. A matching point is also identified as having potential for causing topology deviations, if it is a vertex in a triangle having too small an area or height. An iterative process is performed to identify such undesirable matching points.
These and other objects and advantages of the present invention will appear more clearly from the following description in which the preferred embodiment of the present invention has been set forth in conjunction with the drawings.
BRIEF DESCRIPTIONS OF THE DRAWINGSThe present invention will be described with reference to the following drawings, in which:
<FGREF>FIG. 1</FGREF> illustrates a model using geometric objects.
<FGREF>FIG. 2</FGREF> is a first map of an area.
<FGREF>FIG. 3</FGREF> is a second map of the area shown in FIG. 2.
<FGREF>FIG. 4</FGREF> depicts the map in <FGREF>FIG. 2</FGREF> being overlaid by the map in FIG. 3.
<FGREF>FIG. 5</FGREF> illustrates a sequence of operations for repositioning one model to another.
<FGREF>FIG. 6</FGREF> illustrates a sequence of operations for identifying matching arcs in accordance with the present invention.
<FGREF>FIG. 7</FGREF> illustrates a sequence of operations for identifying matching polygons.
<FGREF>FIG. 8</FGREF> illustrates a sequence of operations for determining the degree of similarity between a pair of polygons.
<FGREF>FIG. 9</FGREF> illustrates two sets of polygons for which proximity is being measured.
<FGREF>FIG. 10</FGREF> illustrates polygons for which area values are being determined.
<FGREF>FIG. 11</FGREF> illustrates a sequence of operations for assigning attributes to matching arcs.
<FGREF>FIG. 12</FGREF> illustrates a sequence of operations for warping a model in accordance with the present invention.
<FGREF>FIG. 13</FGREF> illustrates a sequence of operations for identifying matching points that have potential for causing topology deviations.
<FGREF>FIGS. 14</FGREF> illustrates the results of performing a triangulation on a first set of matching points and applying the same triangulation to a corresponding second set of matching points.
<FGREF>FIG. 15</FGREF> illustrates a sequence of operations for initially identifying matching points that may cause topology deviations.
<FGREF>FIG. 16</FGREF> illustrates a sequence of operations for replacing matching points.
FIGS. 17(a)(b) illustrate the successful replacement of a matching point in one embodiment of the present invention.
FIGS. 18(a)(b) illustrate the successful replacement of a matching point in an alternate embodiment of the present invention.
<FGREF>FIG. 19</FGREF> illustrates a sequence of operations for transforming selected regions of a model.
FIGS. 20(a)(c) illustrate intersection points.
<FGREF>FIG. 21</FGREF> illustrates a block diagram of one exemplar hardware architecture that can be used to practice the present invention.
DETAILED DESCRIPTION<FGREF>FIG. 5</FGREF> illustrates a sequence of operations for performing a repositioning of two sets of geometric objects, in accordance with the present invention. In one embodiment of the present invention, each set of geometric objects is an electronic map. In such an embodiment, the repositioning process is carried out by a computer system which is able to access both of the electronic maps and a set of instructions that provides for repositioning the two electronic maps. Such a computer system will be described in greater detail below.
In describing aspects of the present invention, maps, and in particular electronic maps, will be used as an example of a set of geometric objects. However, one with ordinary skill in the art will recognize that a set of geometric objects can be used to represent a number of other things, such as the floor plan of a building, a layout of an integrated circuit, and a machine drawing. Accordingly, the invention is in no way limited to electronic maps and can be practiced using any set of geometric objects.
As shown in <FGREF>FIG. 5</FGREF>, repositioning is initiated in step 130 by identifying arcs in a first electronic map (first set of geometric objects) for which there is a matching arc in a second electronic map (second set of geometric objects). The matching arcs are then employed in step 132 to identify points in the first map that match points in the second map in step 132. Next, geometric objects in the first map are warped to create a new map, based on a transformation function that is derived from a set of the matching points identified in step 132.
In embodiments of the present invention, the arc matching performed in step 130 is based on geometry and topology information associated with the maps. This avoids any reliance on arc attributes, which may not be supplied. In general, arc matching is performed by identifying arcs in the first map that are cobounded on both sides by polygons which match the corresponding cobounding polygons of the arc in the second map.
In order to identify matching polygons, a set of similarity metrics are determined for each pairing of a polygon in the first map and a polygon in the second map. The similarity metrics are then employed to determine the degree of similarity between polygons and whether or not they match. In one embodiment of the present invention, the similarity metrics include isolated metrics that indicate the similarity of the shape, proximity, area, and rotation of polygons being compared.
The identification of matching points in step 132 is based on the matching arcs identified in step 130 and can be performed in a number of ways that are well known in the art. One such process for identifying matching points is disclosed in U.S. Pat. No. 5,546,107, entitled Automatic ChainBased Conflation of Digital Maps. However, many other processes can be employed.
In accordance with the present invention, the warping of the first map in step 134 is performed so that local distortions in the first and second maps are removed without compromising the topology represented in the two maps. In one embodiment of the present invention, selected corresponding regions of each map are employed in the warping process. For the selected regions, it is determined which matching points have potential for causing topology deviations to occur in the new map being created. These points are regarded as outliers and are rejected from the set of matching points. Transformation equations are then derived using the remaining matching points. Finally, the transformation equations are used to transform points in the first map to generate the new map.
In order to perform the repositioning process described in <FGREF>FIG. 5</FGREF>, several requirements must be met. The positions and shapes of all geometric objects (points, arcs, and polygons) must be provided with respect to a common coordinate system. The origin for each coordinate system is to represent the same physical location. All topological information relating to the maps must also be provided. Such information includes the points bounding each arc, the arcs defining each polygon, the arcs connected to each point, and the polygons cobounding each arc.
When warping, it is also critical that the selected region of interest in each map represents the same physical location. This can be ensured by having the vertices for a selected region in the first map represent the same real world locations as the vertices for the selected region in the second map. The need for this requirement will be explained below.
<FGREF>FIG. 6</FGREF> illustrates a sequence of operations that are performed to identify matching arcs (step 130, <FGREF>FIG. 5</FGREF>) in the two selected maps. First, matching polygons in the two maps are identified in step 140. The matching polygons are then employed to designate matching arcs in step 142.
<FGREF>FIG. 7</FGREF> illustrates a sequence of operations employed in one embodiment of the present invention for identifying matching polygons in different maps (step 140, FIG. 6). First, a pair of polygons is selected in step 150, with one polygon being in the first map and the other polygon being in the second map. Next, the degree of similarity of the selected polygons is determined in step 152. Once the degree of similarity is determined, a determination is made of whether there are any unselected pairs of polygons in step 154. If it is determined that there is a pair of polygons that has not yet been selected, a new pair is selected in step 150 and the above described process is repeated. Otherwise, matching polygons are paired in step 156, based on the similarity determinations made in step 152.
<FGREF>FIG. 8</FGREF> illustrates a sequence of operations that is employed in one embodiment of the present invention for determining the degree of similarity between two polygons (step 152, FIG. 7). First, a set of similarity metrics for the selected pair of polygons is determined (steps 160, 162, 164, and 166). Next, the degree of similarity between the selected pair of polygons is calculated in step 168, based on the set of similarity metrics. As shown in <FGREF>FIG. 8</FGREF>, similarity metrics are obtained for the relative proximity, area, shape, and rotation of the selected polygons. However, in alternate embodiments of the present invention, other similarity metrics, or a subset of the similarity metrics shown in <FGREF>FIG. 8</FGREF>, or a combination thereof are included in the set of similarity metrics.
As shown in <FGREF>FIG. 8</FGREF>, a proximity similarity metric is first determined in step 160, independent of the area, shape, and rotation metrics. As a first step in determining the proximity, a centroid is computed for each polygon in the selected pair. In order to determine the centroid for a geometric object, N number of points are selected along the polygon's perimeter. In one embodiment of the present invention, the N number of points are selected with each of the selected points being separated by an equal distance along the polygon's perimeter. The coordinates of the centroid are then calculated according to the following equation: <CWU><MATHUS><MATHEMATICA></MATHEMATICA><MATHML><math><mtable><mtr><mtd><mrow><mi>C</mi><mo>=</mo><mrow><mo>(</mo><mrow><mfrac><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover><mo></mo><msub><mi>x</mi><mi>i</mi></msub></mrow><mi>N</mi></mfrac><mo>,</mo><mfrac><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover><mo></mo><msub><mi>y</mi><mi>i</mi></msub></mrow><mi>N</mi></mfrac></mrow><mo>)</mo></mrow></mrow></mtd><mtd><mstyle><mtext>Equation 1</mtext></mstyle></mtd></mtr></mtable></math></MATHML><EMI></EMI></MATHUS></CWU>
wherein:
C is the x and y coordinates for the centroid;
x<HIL><SB>i </SB></HIL>is an x coordinate for the ith selected point on the polygon's perimeter; and
y<HIL><SB>i </SB></HIL>is the y coordinate for the ith selected point on the polygon's perimeter.
Although the invention is described in terms of the Cartesian coordinate system (x, y), one with ordinary skill in the art will recognize that the use of other coordinate systems is within the scope of the present invention.
Once the centroid for each of the selected polygons has been determined, the displacement between the centroids is calculated according to the following equation:
<F>D={square root over ((x<HIL><SB>A</SB></HIL>−x<HIL><SB>B</SB></HIL>)<HIL><SP>2</SP></HIL>+(y<HIL><SB>A</SB></HIL>−y<HIL><SB>B</SB></HIL>)<HIL><SP>2</SP></HIL>)} Equation 2 </F>
wherein:
D is the displacement;
x<HIL><SB>A </SB></HIL>is the x coordinate for the centroid in the polygon from the first map;
x<HIL><SB>B </SB></HIL>is the x coordinate for the centroid in the polygon from the second map;
y<HIL><SB>A </SB></HIL>is the y coordinate for the centroid in the polygon from the first map; and
y<HIL><SB>B </SB></HIL>is the y coordinate for the centroid in the polygon from the second map.
Once the displacement has been determined, the proximity similarity metric is calculated according to the following equation: <CWU><MATHUS><MATHEMATICA></MATHEMATICA><MATHML><math><mtable><mtr><mtd><mrow><mrow><mrow><mi>P</mi><mo>=</mo><mrow><mrow><mfrac><mrow><mo>(</mo><mrow><mi>B</mi><mo></mo><mi>D</mi></mrow><mo>)</mo></mrow><mrow><mo>(</mo><mrow><mi>B</mi><mo>+</mo><mi>D</mi></mrow><mo>)</mo></mrow></mfrac><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>if</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>B</mi></mrow><mo>></mo><mi>D</mi></mrow></mrow><mo>,</mo><mi>else</mi></mrow><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mi>P</mi><mo>=</mo><mn>0</mn></mrow></mrow></mtd><mtd><mstyle><mtext>Equation 3</mtext></mstyle></mtd></mtr></mtable></math></MATHML><EMI></EMI></MATHUS></CWU>
wherein:
P is the proximity similarity metric; and
B is a normalizing constant.
In one embodiment of the present invention, N is equal to 32, and normalizing constant B is user selectable based on the quality of the maps being repositioned. In a typical example, the first map has a 1:24K scale, yielding an accuracy tolerance of 40 feet, and the second map has a 1:100K scale, yielding an accuracy tolerance of 160 feet. In such an example, normalizing constant B is equal to the sum of the tolerances of the two maps, which is equal to 200 feet.
<FGREF>FIG. 9</FGREF> illustrates the effective usefulness of the proximity similarity metric. <FGREF>FIG. 9</FGREF> includes a first set of polygons 170 and a second set of polygons 172. Each of the polygons in sets 170 and 172 are similar in area, rotation, and shape. If the proximity similarity metric is determined individually for each combination of polygon 174 in set 170 and each of the polygons in set 172, then the proximity similarity metric will be best for polygon 176. This is because the centroid of polygon 176 has the smallest displacement from the centroid of polygon 174.
Once the proximity similarity metric has been determined (step 160, FIG. 8), an area similarity metric is determined in step 162. First, N number of preliminary vectors are generated for each of the selected polygons. Each polygon's preliminary vectors are generated to extend from the polygon's centroid to each of the N points that were selected along the polygon's perimeter in determining the proximity similarity metric.
Next, a vector set is established for each polygon. For each polygon, the polygon's centroid is subtracted from the start point and end point of each preliminary vector in the polygon. As a result, the vectors each appear to extend from the origin. This removes the influence of the polygon's location on subsequent metrics.
<FGREF>FIG. 10</FGREF> illustrates sets of vector generated for a pair of polygons 180, 181. Vectors V<HIL><SB>A1</SB></HIL>V<HIL><SB>AN </SB></HIL>have been generated for polygon 180. Each of vectors V<HIL><SB>A1</SB></HIL>V<HIL><SB>AN </SB></HIL>extends from origin 184 to one of N points 182<HIL><SB>1−N </SB></HIL>along the perimeter 186 of polygon 180. Vectors V<HIL><SB>B1</SB></HIL>V<HIL><SB>BN </SB></HIL>have been generated for polygon 181. Each of vectors V<HIL><SB>B1</SB></HIL>V<HIL><SB>BN </SB></HIL>extends from origin 184 to one of N points 183<HIL><SB>1−N </SB></HIL>along the perimeter 187 of polygon 181.
Next an area value is calculated for each selected polygon, according to the following equation: <CWU><MATHUS><MATHEMATICA></MATHEMATICA><MATHML><math><mtable><mtr><mtd><mrow><mi>AV</mi><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover><mo></mo><msup><mrow><mo>&LeftDoubleBracketingBar;</mo><msub><mi>V</mi><mi>i</mi></msub><mo>&RightDoubleBracketingBar;</mo></mrow><mn>2</mn></msup></mrow></mrow></mtd><mtd><mstyle><mtext>Equation 4</mtext></mstyle></mtd></mtr></mtable></math></MATHML><EMI></EMI></MATHUS></CWU>
wherein:
AV is the area value; and
∥V<HIL><SB>i</SB></HIL>∥ is the length of an ith one of the vectors in the polygon.
Once an area value has been determined for each polygon, an area similarity metric is determined according to the following equation: <CWU><MATHUS><MATHEMATICA></MATHEMATICA><MATHML><math><mtable><mtr><mtd><mrow><mi>A</mi><mo>=</mo><mfrac><mrow><mi>MIN</mi><mo></mo><mrow><mo>(</mo><mrow><msub><mi>AV</mi><mi>A</mi></msub><mo>,</mo><msub><mi>AV</mi><mi>B</mi></msub></mrow><mo>)</mo></mrow></mrow><mrow><mi>MAX</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mo>(</mo><mrow><msub><mi>AV</mi><mi>A</mi></msub><mo>,</mo><msub><mi>AV</mi><mi>B</mi></msub></mrow><mo>)</mo></mrow></mrow></mfrac></mrow></mtd><mtd><mstyle><mtext>Equation 5</mtext></mstyle></mtd></mtr></mtable></math></MATHML><EMI></EMI></MATHUS></CWU>
wherein:
A is the area similarity metric;
AV<HIL><SB>A </SB></HIL>is the area value for the polygon in the first map;
AV<HIL><SB>B </SB></HIL>is the area value for the polygon in the second map;
MIN( ) is an instruction indicating that the lowest value appearing within the parentheses is to be selected; and
MAX( ) is an operation indicating that the maximum value appearing between the parentheses is to be selected.
Accordingly, the area similarity metric will represent the ratio of the smallest area value to the largest area value for the two selected polygons.
Once the area similarity metric has been determined (step 162, FIG. 8), a shape similarity metric is determined in step 164. In order to determine the shape similarity metric, each of the vectors generated in each selected polygon is normalized according to the following equation: <CWU><MATHUS><MATHEMATICA></MATHEMATICA><MATHML><math><mtable><mtr><mtd><mrow><msub><mi>V</mi><mi>norm</mi></msub><mo>=</mo><mrow><mo>(</mo><mrow><mfrac><mi>x</mi><msqrt><mi>AV</mi></msqrt></mfrac><mo>,</mo><mfrac><mi>y</mi><msqrt><mi>AV</mi></msqrt></mfrac></mrow><mo>)</mo></mrow></mrow></mtd><mtd><mstyle><mtext>Equation 6</mtext></mstyle></mtd></mtr></mtable></math></MATHML><EMI></EMI></MATHUS></CWU>
wherein:
V<HIL><SB>norm </SB></HIL>is the normalized vector;
x is the vector's xaxis component;
y is the vector's yaxis component; and
AV is the area value for the polygon in which the vector resides.
The normalization discounts any area difference between the polygons, thereby allowing the shape determination to be made in isolation.
Next, a set of shape measures are obtained as the sum of the squares of vector differences between the two selected polygons' sets of normalized vectors at different rotations. The minimum shape measure value that is then designated as the shape similarity metric.
A shape measure for the ith rotation of the polygons is determined according to the following equation: <CWU><MATHUS><MATHEMATICA></MATHEMATICA><MATHML><math><mtable><mtr><mtd><mrow><msub><mi>SM</mi><mi>i</mi></msub><mo>=</mo><mrow><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover><mo></mo><msup><mrow><mo>&LeftDoubleBracketingBar;</mo><mrow><mover><msub><mi>V</mi><mi>Aj</mi></msub><mi>_</mi></mover><mo></mo><mover><msub><mi>V</mi><mrow><mi>B</mi><mo></mo><mrow><mo>(</mo><mrow><mi>j</mi><mo>+</mo><mi>i</mi></mrow><mo>)</mo></mrow></mrow></msub><mi>_</mi></mover></mrow><mo>&RightDoubleBracketingBar;</mo></mrow><mn>2</mn></msup></mrow></mrow></mtd><mtd><mstyle><mtext>Equation 7</mtext></mstyle></mtd></mtr></mtable></math></MATHML><EMI></EMI></MATHUS></CWU>
wherein:
SM<HIL><SB>i </SB></HIL>is the ith shape measure;
{overscore (V<HIL><SB>Aj</SB></HIL>)} is the jth normalized vector in the polygon from the first map; and
{overscore (V<HIL><SB>B(j+i)</SB></HIL>)} is the (j+i)th normalized vector in the polygon from the second map, wherein (j+i) is equal to the sum of j and i if the sum is less than or equal to N, else (j+i) is equal to the sum of j and i minus N.
The shape similarity metric is the minimum SM<HIL><SB>i </SB></HIL>value that is determined for i spanning a range from 0 to (N−1). By allowing i to span from 0 to (N−1), all of the possible shape measures between the two polygons are made.
In order to determine the shape similarity metric, the following equation is employed:
<F>S=MIN(SM<HIL><SB>i </SB></HIL>for 0≦i≦(N−1)) Equation 8 </F>
wherein:
S is the shape similarity metric.
Once the shape similarity metric has been determined (step 164, FIG. 8), a rotation similarity metric is determined in step 166. Using the rotation i value that yielded the minimum shape measure value (SM<HIL><SB>i</SB></HIL>) a rotation measure is made of the angles between the corresponding vectors in the two polygons. The corresponding vectors are those that were subtracted (Equation 7) from each other when determining the shape measure value (SM<HIL><SB>i</SB></HIL>) that was selected to be used as the shape similarity metric.
In one embodiment of the present invention, the rotation measure is calculated according to the following equation: <CWU><MATHUS><MATHEMATICA></MATHEMATICA><MATHML><math><mtable><mtr><mtd><mrow><mi>θ</mi><mo>=</mo><mrow><mo>&LeftBracketingBar;</mo><mfrac><mrow><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></munderover><mo></mo><mrow><mi>∠</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mo>(</mo><mrow><msub><mi>V</mi><mi>Aj</mi></msub><mo></mo><msub><mi>V</mi><mrow><mi>B</mi><mo></mo><mrow><mo>(</mo><mrow><mi>j</mi><mo>+</mo><mi>i</mi></mrow><mo>)</mo></mrow></mrow></msub></mrow><mo>)</mo></mrow></mrow></mrow><mi>N</mi></mfrac><mo>&RightBracketingBar;</mo></mrow></mrow></mtd><mtd><mstyle><mtext>Equation 9</mtext></mstyle></mtd></mtr></mtable></math></MATHML><EMI></EMI></MATHUS></CWU>
wherein:
θ is the rotation measure;
∠(V<HIL><SB>Aj</SB></HIL>−V<HIL><SB>B(j+i)</SB></HIL>) is an operation indicating that a measure is taken of the angle between the V<HIL><SB>Aj </SB></HIL>vector and the V<HIL><SB>B(j+i) </SB></HIL>vector;
V<HIL><SB>Aj </SB></HIL>is the jth vector in the selected polygon from the first map;
V<HIL><SB>B(j+i) </SB></HIL>is the (j+i)th vector in the selected polygon from the second map, wherein i is equal to the i value that yielded the shape measure value (SM<HIL><SB>i</SB></HIL>) that was selected as the shape similarity metric, and wherein (j+i) is the same as described above with reference to Equation 7.
In one embodiment of the present invention, the angle between the vectors is determined by taking the arc tangent of the two vectors (V<HIL><SB>Aj </SB></HIL>and V<HIL><SB>B(j+i)</SB></HIL>).
Once the rotation measure is obtained, it is used to calculate a rotation similarity metric according to the following equation: <CWU><MATHUS><MATHEMATICA></MATHEMATICA><MATHML><math><mtable><mtr><mtd><mrow><mrow><mrow><mi>R</mi><mo>=</mo><mrow><mrow><mfrac><mrow><mo>(</mo><mrow><mi>Φ</mi><mo></mo><mi>θ</mi></mrow><mo>)</mo></mrow><mrow><mo>(</mo><mrow><mi>Φ</mi><mo>+</mo><mi>θ</mi></mrow><mo>)</mo></mrow></mfrac><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>if</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>Φ</mi></mrow><mo>></mo><mi>θ</mi></mrow></mrow><mo>,</mo><mi>else</mi></mrow><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mrow><mi>R</mi><mo>=</mo><mn>0</mn></mrow></mrow></mtd><mtd><mstyle><mtext>Equation 10</mtext></mstyle></mtd></mtr></mtable></math></MATHML><EMI></EMI></MATHUS></CWU>
wherein:
R is the rotation similarity metric; and
Φ is a normalizing constant.
In one embodiment of the present invention, Φ is equal to 45°.
Once the rotation similarity metric is determined (step 166, FIG. 8), a matching metric is calculated for the selected pair of geometric objects in step 168. The matching metric is calculated by multiplying the proximity similarity metric (P), area similarity metric (A), shape similarity metric (S), and rotation similarity metric (R). This will yield a value ranging from negative infinity to 1, with 1 being the strongest level of matching.
As described above with reference to <FGREF>FIG. 7</FGREF>, the matching metric indicates a degree of similarity between polygons that is employed to pair matching polygons in the two maps (step 156, FIG. 7). In order for two polygons to be paired as matching, their matching metric must be equal to or greater than a minimum matching threshold. In one embodiment of the present invention, the minimum matching threshold is 0.35.
In some instances, polygons in one map can have matching metrics that exceed the minimum matching threshold for multiple polygons in the other map. However, each polygon in a map can only be paired with one other polygon in the other map to form a pair of matching polygons. No polygon can be paired as matching more than one other polygon.
In one embodiment of the present invention, when such multiple high matching metrics occur, the following rules are applied in pairing polygons as matching (step 156, FIG. 7):
1. For each polygon in the second map, pair it with the polygon in the first map that has the highest matching metric that exceeds the minimum matching threshold. In the case of a tie, select either one of the polygons in the first map that tied.
2. If multiple polygons in the second map are then paired to the same polygon in the first map, then select the pairing with the highest matching metric. In the case of a tie, select either one of the pairings.
As shown in <FGREF>FIG. 6</FGREF>, the matching polygons are now employed to designate matching arcs in the maps (step 142, FIG. 6). <FGREF>FIG. 11</FGREF> illustrates a sequence of operations for designating the matching arcs. First, an arc in the first map is selected in step 190. Next, a determination is made of whether the arc is cobounded on both sides by polygons that have been paired with a matching polygon in the second map (step 191).
If it is determined that the selected arc is cobounded on both sides by polygons that have been paired with matching polygons in the second map, then the arc is assigned an attribute in step 192. The assigned attribute can then be employed in a process for identifying nodes in the first map that match nodes in the second map. In one embodiment of the present invention, the assigned attribute is a label formed by a concatenation of assigned unique identifiers for each cobounding matched polygon. In an alternate embodiment, the assigned attribute is a label, such as a street name.
If the selected arc is determined not to be bounded on both sides by polygons that have been paired with matching polygons in the second map, or once an arc is assigned an attribute in step 192, then it is determined in step 194 whether any of the arcs in the first map have not yet been selected. If there are unselected arcs, then a new arc is selected in step 190 and the abovedescribed process is repeated. Otherwise, the process of designating matching arcs is completed.
Once matching arcs have been identified (step 130 FIG. 5), matching points in the two maps are identified. As described above with reference to FIG. 5 (step 132), processes for identifying matching points are well known in the art.
In particular, a process described in U.S. Pat. No. 5,546,107 can be employed to identify such matching points by utilizing matching arcs for the two maps.
Once matching points in the two maps are identified (step 132, FIG. 5), the warping process (step 134) as described above with reference to <FGREF>FIG. 5</FGREF> is initiated. <FGREF>FIG. 12</FGREF> illustrates a sequence of operations that are performed in order to effectuate the warping in one embodiment of the present invention. First, a corresponding pair of regions are identified in the first map and the second map in step 200. As described above, these regions must correspond to the same physical area in each map. The importance of this requirement will be explained in greater detail below. By performing the warping on selected regions, local distortions in the first and second maps are effectively corrected, without being affected by distortions in other regions.
Once the regions are selected, the matching points in the selected regions that have potential for causing a topology deviation in the new map that is to result from warping are identified in step 201. An example of such a topology deviation is an inversion of geometric objects. These points are identified, so that they will not be incorporated in the creation of transformation equations that are used in the warping process. A process for identifying such points in one embodiment of the present invention will be described in greater detail below.
After the point identification process in step 201 is complete, the selected region in the first map is transformed to form a new map in step 216. This transformation is performed using a set of equation that are derived from the relationship between corresponding matching points in the first and second maps, except for the points identified in step 201. A process for performing such a transformation in one embodiment of the present invention will be described in greater detail below.
After the transformation of the selected region in the first map (step 216) is done, a determination is made in step 217 of whether more warping is desired. If more warping is desired, then a new pair of regions is selected in step 200 and the abovedescribed process steps are updated. Otherwise, the warping is done.
<FGREF>FIG. 13</FGREF> illustrate a sequence of operation performed in one embodiment of the present invention for identifying matching point having potential for causing topology deviations (step 201, FIG. 12). First, the selected region in the first map is triangulated in step 202. A triangulation is performed by forming a set of triangles within the region using the matching points in the region and the boundary points that define the vertices of the region selected for warping. For purposes of this Application, these boundary points will also be referred to as matching points. In triangulation, one edge is drawn between each matching point in the selected region of the first map, such that each edge belongs to either two triangles or one triangle and the area outside of the selected region.
In one embodiment of the present invention, a Delaunay triangulation is performed. For each set of points in a twodimensional plane, there exists a unique Delaunay triangulation. In a Delaunay triangulation, the triangles that are formed are all made to be as close as possible to being equilateral triangles. In a Delaunay triangulation of a set of points, no point in the set of points falls in the interior of a circle that passes through all three vertices of any triangle in the triangulation. Methods for performing Delaunay triangulation are well known in the art and in fact are prior art with respect to this Application.
A further explanation of Delaunay triangulation can be found in the following references:
“Mesh Generation and Optimal Triangulation” by Marshall Bern and David Epstein, which was published in Computing and Euclidean Geometry, DingZhu Du and Frank Hwang editors, World Scientific, Singapore, pp. 2390, 1992;
Jonathan Richard Shewchuk, “Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator”, First Workshop on Applied Computational Geometry (Philadelphia, Pennsylvania) pages 124133, ACM, May 1996; and
Jim Ruppert, “A Delaunay Refinement Algorithm for Quality 2Dimensional Mesh Generation”, Journal of Algorithms 18(3): 548585, May 1995.
The abovecited references are hereby incorporated by reference. Further information concerning Delaunay triangulation can be found at the following location on the Internet: http://www.cs.cmu.edu/˜quake/triangle.html.
Once the triangulation of the selected region in the first map is completed, the same triangulation is applied to the selected region in the second map in step 202. In applying the triangulation to the second map, a new triangulation process is not executed. Instead, edges are formed between the same matching points in the selected region in the second map as were formed between the corresponding matching points in the selected region in the first map.
<FGREF>FIG. 14</FGREF> illustrates the results of the triangulation of a selected region in the first map and a selected region in the second map, in accordance with the present invention. In <FGREF>FIG. 14</FGREF>, a set 240 of points P<HIL><SB>1</SB></HIL>P<HIL><SB>6 </SB></HIL>are all of the matching points in the selected region of the first map. A triangulation of these points could result in the following triangles being formed (Please note that these triangles are not drawn to scale for the purpose of demonstrating a Delaunay triangulation):
(P<HIL><SB>1</SB></HIL>, P<HIL><SB>6</SB></HIL>, P<HIL><SB>5</SB></HIL>)
(P<HIL><SB>5</SB></HIL>, P<HIL><SB>6</SB></HIL>, P<HIL><SB>4</SB></HIL>)
(P<HIL><SB>6</SB></HIL>, P<HIL><SB>4</SB></HIL>, P<HIL><SB>3</SB></HIL>)
(P<HIL><SB>6</SB></HIL>, P<HIL><SB>3</SB></HIL>, P<HIL><SB>2</SB></HIL>)
(P<HIL><SB>1</SB></HIL>, P<HIL><SB>2</SB></HIL>, P<HIL><SB>6</SB></HIL>).
A set 242 of points P<HIL><SB>1</SB></HIL>′P<HIL><SB>6</SB></HIL>′ are the matching points in the selected region of the second map that match points P<HIL><SB>1</SB></HIL>P<HIL><SB>6</SB></HIL>, respectively. As shown in <FGREF>FIG. 14</FGREF>, the same triangles that were formed using points P<HIL><SB>1</SB></HIL>P<HIL><SB>6 </SB></HIL>are formed in the selected region of the second map to form the following corresponding triangles:
(P<HIL><SB>1</SB></HIL>′, P<HIL><SB>6</SB></HIL>′, P<HIL><SB>5</SB></HIL>′)
(P<HIL><SB>5</SB></HIL>′, P<HIL><SB>6</SB></HIL>′, P<HIL><SB>4</SB></HIL>′)
(P<HIL><SB>6</SB></HIL>′, P<HIL><SB>4</SB></HIL>′, P<HIL><SB>3</SB></HIL>′)
(P<HIL><SB>6</SB></HIL>′, P<HIL><SB>3</SB></HIL>′, P<HIL><SB>2</SB></HIL>′)
(P<HIL><SB>1</SB></HIL>′, P<HIL><SB>2</SB></HIL>′, P<HIL><SB>6</SB></HIL>′).
Once the triangulation is completed for both of the selected regions, an initial identification of topology deviating matching points is performed in step 206. This determination is made in one embodiment by comparing each triangle in the selected region of the first map to a corresponding triangle in the selected region of the second map. In one such embodiment, the comparison is made to determine whether the triangles being compared are inverted. Such an inversion indicates that there is a potential for topology deviations. The fact that an inversion identifies potential for topology deviation is a result of the selected regions corresponding to the same physical area in the first and second maps, as described above.
<FGREF>FIG. 15</FGREF> illustrates a sequence of operations performed in a accordance with the present invention to make an initial identification of whether matching points in the selected regions of the first and second maps have potential for causing topology deviations (step 206, FIG. 13). First, a pair of triangles is selected in step 230. The selected pair includes a triangle from the selected region of the first map and a triangle from the selected region of the second map, wherein the triangle in the second map has vertices that are matching points of the vertices of the triangle in the first map.
Next, the selected triangles are analyzed to determine whether the matching points making up the vertices of the triangles have potential for causing topology deviations. One aspect of this determination is determining whether the triangles are inverted from one another. As described above, such an inversion signals the existence of a matching point with potential for causing topology deviations.
<FGREF>FIG. 14</FGREF> illustrates a pair of inverted triangles. As described above, <FGREF>FIG. 14</FGREF> shows a set 240 of triangulated matching points (P<HIL><SB>1</SB></HIL>P<HIL><SB>6</SB></HIL>) for a selected region in the first map and a set 242 of triangulated matching points (P<HIL><SB>1</SB></HIL>′P<HIL><SB>6</SB></HIL>′) for a corresponding selected region in the second map. Triangle (P<HIL><SB>6</SB></HIL>, P<HIL><SB>3</SB></HIL>, P<HIL><SB>2</SB></HIL>) and corresponding triangle (P<HIL><SB>6</SB></HIL>′, P<HIL><SB>2</SB></HIL>′, P<HIL><SB>3</SB></HIL>′) are inverted with respect to one another. These triangles are considered to be inverted, because the P<HIL><SB>6 </SB></HIL>and P<HIL><SB>6</SB></HIL>′ points lie on opposite sides of the edge passing between P<HIL><SB>3</SB></HIL>, P<HIL><SB>2 </SB></HIL>and P<HIL><SB>2</SB></HIL>′, P<HIL><SB>3</SB></HIL>′.
In order to determine whether triangles are inverted in one embodiment of the present invention, cross product calculations are employed. A cross product is taken of any two edges in the selected triangle in the first map, and a cross product is taken of the same two edges in the corresponding triangle in the second map. For example, with reference to <FGREF>FIG. 14</FGREF>, the cross products could be taken of the P<HIL><SB>3</SB></HIL>, P<HIL><SB>6 </SB></HIL>edge and P<HIL><SB>3</SB></HIL>, P<HIL><SB>2 </SB></HIL>edge in set 240 and the P<HIL><SB>3</SB></HIL>′, P<HIL><SB>6</SB></HIL>′ edge and P<HIL><SB>3</SB></HIL>′, P<HIL><SB>2</SB></HIL>′ edge in set 242.
In taking the cross product of two edges, each edge is treated as a vector extending from the point where the edges intersect. For example, the P<HIL><SB>3</SB></HIL>, P<HIL><SB>6 </SB></HIL>edge and P<HIL><SB>3</SB></HIL>, P<HIL><SB>2 </SB></HIL>edge are treated as a first vector from P<HIL><SB>3 </SB></HIL>to P<HIL><SB>6 </SB></HIL>and a second vector from P<HIL><SB>3 </SB></HIL>to P<HIL><SB>2</SB></HIL>. When taking the cross product of these vectors, the following equation is employed:
<F>CP=(x<HIL><SB>e1</SB></HIL>−x<HIL><SB>s1</SB></HIL>)×(y<HIL><SB>e2</SB></HIL>−y<HIL><SB>s2</SB></HIL>)−(x<HIL><SB>e2</SB></HIL>x<HIL><SB>e2</SB></HIL>)×(y<HIL><SB>e1</SB></HIL>y<HIL><SB>s1</SB></HIL>) Equation 11 </F>
wherein:
CP is the cross product;
x<HIL><SB>e1 </SB></HIL>is the x coordinate of the end point of the first vector;
x<HIL><SB>s1 </SB></HIL>is the x coordinate of the start point of the first vector;
y<HIL><SB>e1 </SB></HIL>is the y coordinate of the end point of the first vector;
y<HIL><SB>s1 </SB></HIL>is the y coordinate of the start point of the first vector;
x<HIL><SB>e2 </SB></HIL>is the x coordinate of the end point of the second vector;
x<HIL><SB>s2 </SB></HIL>is the x coordinate of the start point of the second vector;
y<HIL><SB>e2 </SB></HIL>is the y coordinate of the end point of the second vector; and
y<HIL><SB>s2 </SB></HIL>is the y coordinate of the start point of the second vector.
If cross products for both of the triangles being compared have the same sign (i.e. positivepositive or negativenegative), then there is no inversion. However, if the cross products are of opposite signs, such as positivenegative or negativepositive, then the triangles are inverted and both considered to contain matching points that have potential for causing topology deviations. If either of the cross products is 0, then the matching points associated with both triangles are also considered to have a potential for causing topology deviations.
In addition to determining whether triangles are inverted in step 232 (FIG. 15), in one embodiment of the present invention, triangle dimensions are also evaluated. For example, if either triangle in a selected pair of corresponding triangles does not have at least a minimum area, then the associated matching points for both triangles are considered to have the potential for causing topology deviations. Additionally, if either triangle of a corresponding pair of triangles does not have at least a minimum height, as its smallest height, then the matching points for both triangles are considered to have potential for causing topology deviations. In one such embodiment, the minimum area threshold is 15 square inches, and the minimum height threshold is 3 inches. Testing for minimum height and area accounts for potential problems with precision on a digital computer. Without this test, a triangle with all its contents can be potentially warped to become a tiny triangle, which may not have enough room to hold all the contents of the original triangle.
Once the selected triangles have been analyzed (step 232, FIG. 15), a determination is made of whether any pair of triangles has not yet been selected in step 236 (FIG. 15). If it is determined that there is a pair of triangles that has not yet been selected, then a new pair of triangles is selected in step 230 and the abovedescribed process is repeated. Otherwise, the initial identification of matching points that have potential for causing topology deviations is completed.
Once the matching points with potential for causing topology deviations have been identified (step 206, FIG. 13), a determination is made in step 208 (<FGREF>FIG. 13</FGREF>) of whether any such points were in fact identified in the last time that step 206 was executed. If it is determined that such undesirable matching points were identified, then a set of these undesirable matching points lose their status as matching points and are placed in a bad point queue in step 210. When a matching point loses its matching status, any triangle having the point as a vertex is considered to be removed. In one embodiment of the present invention, the matching points that lose their status are the matching points that were most frequently identified as having potential for causing topology deviations the last time that step 206 was executed. In an alternate embodiment, points continue to lose matching status, until all inverted or undesirably dimensioned triangles are removed.
After matching status is removed, the selected region from the first map and the selected region in the second map are triangulated again in steps 202 and 204, respectively, using only the matching points that have not lost their matching point status. The abovedescribed initial identification step (206) is then repeated.
If it is determined in step 208 that no matching points were identified as having potential for causing topology deviations in the last time that step 206 was executed, then a determination is made of whether the bad point queue is empty in step 212. The bad point queue is considered to be empty when it contains either no points or only points that are incapable of regaining matching status, as will be described below. If the bad point queue is not empty, then an attempt is made to replace a point in the queue in the selected regions in step 214. If the point can be successfully replaced into the selected regions, so that it no longer is considered to have potential for causing a topology deviation, then the point's status as a matching point is returned. A method for attempting such a replacement will be described below.
Once a replacement attempt (step 214) has been made, it is once again determined whether or not the bad point queue is empty in step 212. If it is determined that the bad point queue is empty, then the process of identifying matching points with potential for causing topology deviations (step 201, <FGREF>FIG. 12</FGREF>) is done.
<FGREF>FIG. 16</FGREF> illustrates a sequence of operations for attempting to replace a point from the bad point queue into the selected regions (step 214, FIG. 13). First, a point in the bad point queue is selected in step 250. Next, a determination is made of whether the point resides within corresponding triangles in the selected region in the first map and the selected region in the second map (step 252). FIG. 17(a) illustrates a situation in which point 272 resides within both triangle 270 with vertices (P<HIL><SB>1</SB></HIL>, P<HIL><SB>2</SB></HIL>, P<HIL><SB>3</SB></HIL>) in the selected region of the first map and corresponding triangle 274 with vertices (P<HIL><SB>1</SB></HIL>′, P<HIL><SB>2</SB></HIL>′, P<HIL><SB>3</SB></HIL>′) in the selected region of the second map.
If it is determined that the selected point does not reside within corresponding triangles, then it is determined in step 254 whether the selected point resides within adjoining triangles in the selected regions of the first and second maps. Such a circumstance of a point residing in adjoining triangles is shown in FIG. 18(a). In the selected region in the first map, point 294 resides within triangle 292 with vertices (P<HIL><SB>1</SB></HIL>, P<HIL><SB>2</SB></HIL>, P<HIL><SB>3</SB></HIL>), which adjoins triangle 290 with vertices (P<HIL><SB>4</SB></HIL>, P<HIL><SB>2</SB></HIL>, P<HIL><SB>3</SB></HIL>). In the selected region in the second map, point 294 resides within triangle 296, which has vertices (P<HIL><SB>4</SB></HIL>′, P<HIL><SB>2</SB></HIL>′, P<HIL><SB>3</SB></HIL>′) and corresponds to triangle 290. Triangle 296 is also adjoined by triangle 298 which corresponds to triangle 292 and has vertices (P<HIL><SB>1</SB></HIL>′, P<HIL><SB>2</SB></HIL>′, P<HIL><SB>3</SB></HIL>′). If it is determined in step 254 that the selected point does not reside in adjoining regions, then the point is not replaced, and the replacement attempt is done.
If it is determined in step 252 that the point resides in corresponding triangles in the selected regions of the first and second maps, then a new triangulation is performed in each of the corresponding triangles using the selected point in step 260. In each corresponding triangle, the point is connected by an arc to each vertex of the triangle to achieve the new triangulation. An example of such a triangulation for a point 272 that resides in corresponding triangles 270 and 274 is shown in FIG. 17(b).
Once the triangulation is complete, a determination is made of whether any of the matching points involved in either of the new triangulations or the replaced bad point have the undesirable potential for causing topology deviations (step 264). In one embodiment, this determination is made as described above with respect to step 206 in FIG. 13. If such undesirable points are identified in step 264, then the selected bad point is not replaced, and the triangulations performed with the selected bad point are undone in step 266. Otherwise, the replacement process for the selected point is complete, with the selected point regaining its status as a matching point and being removed from the bad point queue, and the new triangulations being left in place.
If it was determined in step 254 (<FGREF>FIG. 16</FGREF>) that the selected point resides in adjoining triangles in the selected regions (as shown in FIG. 18(a)), then the corresponding adjoining triangles in each region are made into a single polygon in step 256. This is achieved by removing the common edge that the adjoining triangles share in each of the selected regions.
Next, a triangulation is performed in step 260 as described above, using the vertices of the adjoining triangles in each selected region and the selected bad point. Such a triangulation is illustrated in FIG. 18(b), for the triangles and selected point 294 shown in FIG. 18(a). As shown in FIG. 18(b), the corresponding edges between points P<HIL><SB>2 </SB></HIL>and P<HIL><SB>3 </SB></HIL>and points P<HIL><SB>2</SB></HIL>′ and P<HIL><SB>3</SB></HIL>′ were removed before triangulating.
After the triangulation process (step 260), a determination is made in step 264, as described above, to detect the existence of points with the potential for causing topology deviations. If such points are detected in step 264, then both triangulations are undone; the edges removed to facilitate the triangulation are replaced, and the selected bad point maintains its bad point status. Otherwise, the bad point regains its matching point status and is removed from the bad point queue; the new triangulations remain in place, and the replacement process (step 214, <FGREF>FIG. 13</FGREF>) is done.
As shown in <FGREF>FIG. 13</FGREF>, once the bad point queue is determined to be empty (step 212), such that it contains no bad points or only bad points that cannot be triangulated without causing potential for topological deviations, the identification of matching points with potential for causing topology deviations (step 201, <FGREF>FIG. 12</FGREF>) is done. At this point, the transformation process (step 216, <FGREF>FIG. 12</FGREF>) is initiated.
<FGREF>FIG. 19</FGREF> illustrates a sequence of operations that are performed in one embodiment of the present invention to execute the transformation. First, a set of transformation equations are generated in step 360. A set of transformation equations are generated for each pair of corresponding triangles in the selected region of the first map and the selected region of the second map. Each point within a triangle in the selected region in the first map is referred to by a pair of coordinates (x, y), and each point within a triangle in the selected region in the second map is identified by a set of coordinates (x′, y′). Each x′ coordinate can be expressed by the following equation:
<F>x′=ax+by+c Equation 12 </F>
wherein:
a, b, and c are constants for a pair of corresponding triangles.
Each y′ coordinate can be identified according to the following equation:
<F>y′=dx+ey+f Equation 13 </F>
wherein:
d, e, and f are constants for a pair of corresponding triangles.
Equations 12 and 13 are known as affine equations, which can be used to transform points within one geometric object and to points in another geometric object. In accordance with the present invention, each pair of corresponding triangles is employed to solve for a set of the a, b, c, d, e, and f constants, so that a set of affine equations is defined for each pair of corresponding triangles. Each set of affine equations for a triangle in the selected region of the first map is then used, as described below, for transforming points in the triangle into points in a new map.
The constants in the affine equations for each pair of corresponding triangles are determined by applying well known algebra techniques. Each vertex in a triangle in the selected region of the first map and a corresponding triangle vertex in the second map are known. The coordinates for each vertex in a pair of corresponding triangles are plugged into the affine equations to obtain 6 affine equations for the pair of corresponding triangles These 6 equations are then employed to solve for the six a, b, c, d, e, and f constants using standard well known algebra techniques.
For example, if a triangle in the selected region of the first map has vertices {(x<HIL><SB>1</SB></HIL>, y<HIL><SB>1</SB></HIL>), (x<HIL><SB>2</SB></HIL>, y<HIL><SB>2</SB></HIL>), (x<HIL><SB>3</SB></HIL>, y<HIL><SB>3</SB></HIL>)} and a corresponding triangle in the second selected region of the map has corresponding matching point vertices {(x<HIL><SB>1</SB></HIL>′, y<HIL><SB>1</SB></HIL>′), (x<HIL><SB>2</SB></HIL>′, y<HIL><SB>2</SB></HIL>′), (x<HIL><SB>3</SB></HIL>′, y<HIL><SB>3</SB></HIL>′)}, then the following affine equations can be set forth for determining the a, b, c, d, e, and f constants:
<F>x<HIL><SB>1</SB></HIL>′=ax<HIL><SB>1</SB></HIL>+by<HIL><SB>1</SB></HIL>+c Equation 14 </F>
<F>x<HIL><SB>2</SB></HIL>′=ax<HIL><SB>2</SB></HIL>+by<HIL><SB>2</SB></HIL>+c Equation 15 </F>
<F>x<HIL><SB>3</SB></HIL>′=ax<HIL><SB>3</SB></HIL>+by<HIL><SB>3</SB></HIL>+c Equation 16 </F>
<F>y<HIL><SB>1</SB></HIL>′=dx<HIL><SB>1</SB></HIL>+ey<HIL><SB>1</SB></HIL>+f Equation 17 </F>
<F>y<HIL><SB>2</SB></HIL>′=dx<HIL><SB>2</SB></HIL>+ey<HIL><SB>2</SB></HIL>+f Equation 18 </F>
<F>y<HIL><SB>3</SB></HIL>′=dx<HIL><SB>3</SB></HIL>+ey<HIL><SB>3</SB></HIL>+f Equation 19 </F>
These equations can be solved to find the a, b, c, d, e, and f constants for the pair of corresponding triangles, thereby making the affine equations for the pair of corresponding triangles known. This process is repeated, so that affine equations are determined for each pair of triangles in the selected regions of the first and second maps.
Once the set of affine equations are determined for each pair of corresponding triangles in the selected regions of the first and second maps (step 360, FIG. 19), a set of arc intersection points in the selected region of the first map are identified in step 362. Each arc in the selected region in the first map is evaluated to determine whether is contains a location that is to be identified as an arc intersection point.
An arc intersection point is a location on an arc in the selected region of the first map at which the arc crosses an edge belonging to two adjoining triangles. Such a location 370 is illustrated in FIG. 20(a). Arc 376 extends between point 380 in triangle 372 and point 381 in triangle 374. Point 370 is a location on arc 376 that intersects edge 382, which is shared by triangles 372 and 374. Prior to transformation, arc 378 does not intersect arc 376. In order to preserve topology when performing a transformation to obtain a new map, transformations of arc 376 and arc 378 must also not intersect in the new map.
FIG. 20(b) shows the desirable result after transformation, with arc 376 being reshaped into two arc portions 376a and 376b that do not intersect arc 378′. However, if no special measures are taken, it is possible that transformation will result in the situation shown in FIG. 20(c). In FIG. 20(c), the end points of transformed arc 376′ are the only points on arc 376 that were transformed. As a result, the transformation causes transformed arc 376′ to be falsely intersected with transformed arc 378′.
In order to avoid the topology deviation shown in FIG. 20(c), the location where arc 376 intersects edge 382 (FIG. 20(a)) is identified as an arc intersection point. As a result, an arc intersection point is created at location 370. This shape point will be transformed in step 364 (FIG. 19), as described below, to generate point 370′, which will be connected to arc portions 376a and 376b, as shown in FIG. 20(b).
Once all of the arc intersection points in the selected region of the first map have been identified, the point transformation in step 364 (<FGREF>FIG. 19</FGREF>) is performed. In the point transformation step 364, each point (x, y) in the selected region of the first map is transformed to a point (x′, y′) in a new map, using the affine equations for the triangle in which the first map point (x, y) resides. The point transformation step is also performed on all arc intersection points identified in step 362. As a result, all points of a new map of the selected region are generated.
Once the points in the selected region of the first map are all transformed, the arc connections between the points in the selected region of the first map are replicated between the corresponding newly generated points in step 366. For example, an arc connected to point (x, y) in the first map is connected to point (x′, y′) in the new map, wherein x′ and y′ are derived from x and y using the affine equations.
A system for performing repositioning in accordance with the present invention, as described above, may be implemented in hardware and/or software. In one implementation, the system for repositioning comprises a dedicated processor including processor instructions for performing the functions described herein. Circuits may also be developed to perform the functions described herein. In one embodiment, the system for performing repositioning is part of a repositioning system. The repositioning system can be a general purpose computer with repositioning software. In another implementation, the system for repositioning includes a plurality of computer executable instructions for implementation on a general purpose computer system. Prior to loading into a general purpose computer system, the software may reside as encoded information on a computer readable medium, such as a magnetic floppy disk, magnetic tape, and compact disc read only memory (CDROM).
<FGREF>FIG. 21</FGREF> illustrates a high level block diagram of a general purpose computer system 410 in which the present inventions system for performing repositioning is implemented in one embodiment. In particular, system 410 can be employed to perform the process steps described above with reference to <FGREF>FIGS. 520</FGREF>.
Computer system 410 contains a processor unit 412 and main memory 414. Processor unit 412 is a single microprocessor in one embodiment, and contains a plurality of microprocessors for configuring the computer system 410 as a multiprocessor system in another embodiment. Main memory 414 stores, in part, instructions and data for execution by processor unit 412. When the process steps of the present invention for performing repositioning are wholly or partially implemented in software, main memory 414 stores the executable code during the system's operation. Main memory 414 can include banks of dynamic random access memory (DRAM) as well as high speed cache memory.
Computer system 410 further includes a mass storage device 416, peripheral device(s) 418, input device(s) 420, portable storage medium drive(s) 422, a graphics subsystem 424 and an output display 426. For purposes of simplicity, the components in computer system 410 are shown in <FGREF>FIG. 21</FGREF> as being connected via a single bus 428. However, in alternate embodiments, computer system 410 is connected through one or more data transport means. For example, processor unit 412 and main memory 414 may be connected via a local microprocessor bus, and the mass storage device 416, peripheral device(s) 418, portable storage medium drive(s) 422, and graphics subsystem 424 may be connected via one or more input/output (I/O) buses. Mass storage device 416, which may be implemented with a magnetic disk drive or an optical disk drive, is a nonvolatile storage device for storing data and instructions for use by processor unit 412. In one embodiment, mass storage device 416 stores the system software for performing repositioning for purposes of loading to main memory 14.
Portable storage medium drive 422 operates in conjunction with a portable nonvolatile storage medium, such as a floppy disk, to input and output data and code to and from computer system 410. In one embodiment, the system software for determining a path is stored on such a portable medium, and is input to the computer system 410 via the portable storage medium drive 422. Peripheral device(s) 418 may include any type of computer support device, such as an input/output (I/O) interface, to add additional functionality to the computer system 410. For example, peripheral device(s) 418 may include a network interface card for interfacing computer system 410 to a network, a modem, etc.
Input device(s) 420 provide a portion of the user interface for a user of computer system 410. Input device(s) 420 may include an alphanumeric keypad for inputting alphanumeric and other key information, or a cursor control device, such as a mouse, a trackball, stylus, or cursor direction keys. In order to display textual and graphical information, computer system 410 contains graphics subsystem 424 and the output display 426. Output display 426 may include a cathode ray tube (CRT) display, liquid crystal display (LCD) or other suitable display device. Graphics subsystem 424 receives textual and graphical information, and processes the information for output to output display 426. Output display 426 can be used to report the results of a repositioning. The components contained in computer system 410 are those typically found in general purpose computer systems, and are intended to represent a broad category of such computer components that are well known in the art. The system of <FGREF>FIG. 21</FGREF> illustrates one platform which can be used for the present invention. Numerous other platforms can also suffice, such as Macintoshbased platforms available from Apple Computer, Inc., platforms with different bus configurations, networked platforms, multiprocessor platforms, other personal computers, workstations, mainframes, navigation systems, and so on.
The foregoing detailed description of the invention has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed, and obviously many modifications and variations are possible in light of the above teaching. The described embodiments were chosen in order to best explain the principles of the invention and its practical application to thereby enable others skilled in the art to best utilize the invention in various embodiments and with various modifications as are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the claims appended hereto.