+

US20160078651A1 - Proximity-Base Detail Reduction of Geographic Data - Google Patents

Proximity-Base Detail Reduction of Geographic Data Download PDF

Info

Publication number
US20160078651A1
US20160078651A1 US14/950,664 US201514950664A US2016078651A1 US 20160078651 A1 US20160078651 A1 US 20160078651A1 US 201514950664 A US201514950664 A US 201514950664A US 2016078651 A1 US2016078651 A1 US 2016078651A1
Authority
US
United States
Prior art keywords
data
data point
data points
distance
point
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Abandoned
Application number
US14/950,664
Inventor
Michael L. Asher
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
AT&T Intellectual Property II LP
Original Assignee
AT&T Intellectual Property II LP
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by AT&T Intellectual Property II LP filed Critical AT&T Intellectual Property II LP
Priority to US14/950,664 priority Critical patent/US20160078651A1/en
Assigned to AT&T INTELLECTUAL PROPERTY II, LP reassignment AT&T INTELLECTUAL PROPERTY II, LP ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: ASHER, MICHAEL L.
Publication of US20160078651A1 publication Critical patent/US20160078651A1/en
Abandoned legal-status Critical Current

Links

Images

Classifications

    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06TIMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T11/002D [Two Dimensional] image generation
    • G06T11/20Drawing from basic elements, e.g. lines or circles
    • G06T11/203Drawing of straight lines or curves
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06FELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/29Geographical information databases
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06TIMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T1/00General purpose image data processing
    • G06T1/60Memory management
    • GPHYSICS
    • G06COMPUTING; CALCULATING OR COUNTING
    • G06TIMAGE DATA PROCESSING OR GENERATION, IN GENERAL
    • G06T11/002D [Two Dimensional] image generation
    • G06T11/40Filling a planar surface by adding surface attributes, e.g. colour or texture
    • GPHYSICS
    • G09EDUCATION; CRYPTOGRAPHY; DISPLAY; ADVERTISING; SEALS
    • G09BEDUCATIONAL OR DEMONSTRATION APPLIANCES; APPLIANCES FOR TEACHING, OR COMMUNICATING WITH, THE BLIND, DEAF OR MUTE; MODELS; PLANETARIA; GLOBES; MAPS; DIAGRAMS
    • G09B29/00Maps; Plans; Charts; Diagrams, e.g. route diagram
    • G09B29/10Map spot or coordinate position indicators; Map reading aids
    • G09B29/106Map spot or coordinate position indicators; Map reading aids using electronic means

Definitions

  • GIS Geographic Information Systems
  • the data is typically stored as geometric objects, each constituting one or more longitude/latitude points (e.g., points, polylines, polygons and polypolygons).
  • Such geometric representations of geographic objects can be extremely complex, depending on the precision of the representation. For example, a state boundary may constitute ten thousand points (sometimes referred to as “nodes”) or more, and a small stretch of coastline can require millions of points if submeter resolution is required.
  • a system having a data storage mechanism storing a plurality data points, each data point representing a geographic location, a first set of data points representing a first geometric object and a second set of data points representing a second geometric object and a data reducer removing a first data point from the first set of data points representing the first geometric object based on at least a distance between a first location represented by the first data point and a second location represented by a second data point of the second set of data points representing a second geometric object.
  • a system having a memory for storing a set of instructions and a processor to execute the set of instructions.
  • the set of instructions being operable to store a plurality data points, each data point representing a geographic location, a first set of data points representing a first geometric object and a second set of data points representing a second geometric object and remove a first data point from the first set of data points representing the first geometric object based on at least a distance between a first location represented by the first data point and a second location represented by a second data point of the second set of data points representing a second geometric object.
  • FIG. 1 shows an exemplary table of layers that may be included in a GIS application.
  • FIG. 2 illustrates an exemplary data reduction system for use with GIS applications according to the present invention.
  • FIG. 3 illustrates an exemplary embodiment of a method to determine whether to include a node P n in a detail-reduced version of a geometric representation of a geographic object according to the present invention.
  • FIGS. 4 a and 4 b illustrate views of an exemplary geometric representation of a geographic object as contained in a GIS application, before and after application of the exemplary data reduction method of FIG. 3 .
  • the present invention may be further understood with reference to the following description and the appended drawings, wherein like elements are referred to with the same reference numerals.
  • the exemplary embodiments of the present invention describe a system and method for determining whether to include a point P n when reducing the detail of a geometric representation of geographic objects. The exemplary system and method will be further discussed in detail below.
  • An exemplary GIS display may show various geographical features at varying levels of detail depending on the zoom factor desired by the user.
  • the GIS display may include different types of geographical features on different layers.
  • FIG. 1 shows an exemplary Table 1 showing exemplary layers 10 - 60 in an exemplary GIS display.
  • This exemplary display includes six (6) layers including Layer 1 ( 10 ) having land/water boundaries (e.g., coastline, rivers, etc.); Layer 2 ( 20 ) having roads; Layer 3 ( 30 ) having buildings; Layer 4 ( 40 ) having fiber optic cable runs; Layer 5 ( 50 ) having electrical cable runs; and Layer 6 ( 60 ) having water line runs.
  • Each of the geographic features in each of the layers 10 - 60 may be combined to provide exemplary GIS display for the desired geographic area.
  • each layer may include sub-layers.
  • Layer 5 ( 50 ) having electrical cables may include a first sub-layer showing all 480V electrical cables and a second sub-layer showing all 2 kV electrical cables.
  • the layering model is only exemplary and that the GIS display/system does not need to implement geographical features by layers.
  • FIG. 2 shows an exemplary GIS system 100 according to the present invention.
  • the GIS system 100 may store each of the geometric objects in a data storage 110 (e.g., a database) as a set of points or nodes.
  • a data storage 110 e.g., a database
  • points e.g., a latitude/longitude pair
  • this data is a latitude/longitude pair defining a geographic location, e.g., each point or node includes data representing a latitude/longitude location.
  • a database as a data storage mechanism 110 is only exemplary. Other known data storage mechanisms 110 may also be used.
  • the GIS system 100 may then transmit the objects via a view generator 130 to a client application (e.g., GIS display 140 ), that allows “panning” and “zooming” of the GIS display.
  • a client application e.g., GIS display 140
  • each of the objects may include hundreds or thousands of nodes and there may be many objects on any particular display.
  • zoom levels i.e. lower magnification
  • FIG. 2 which shows the GIS display 140 as external to the GIS system 100 , is only exemplary, and that a GIS system may have a GIS display as part of the system.
  • the exemplary GIS system 100 includes a data reducer 120 to reduce the number of data points that are used to represent an object.
  • the data reducer 120 reduces the data points representing various objects prior to transmission of the objects by the view generator 130 to the client application (e.g., GIS display 140 ).
  • the GIS system 100 will continue to store all the points associated with each object in data storage 110 , but the data reducer 120 will limit the data that is sent by the view generator 130 to the GIS display 140 .
  • the data reduction is performed when the GIS system 100 receives a specific view request from the GIS display 140 .
  • the data reducer 120 is used to limit the number of data points that are stored for each object in data storage 110 .
  • the data reduction is performed when the GIS system 100 is storing the objects representing the geographical information, resulting in a reduced-size data set.
  • the data reduction may be used to limit storage and/or processing requirements within the GIS system 100 , in addition to the reduced set of transmitted points described in the above exemplary embodiment.
  • the data reducer 120 may be used to implement both of the above described data reductions (e.g., when the objects are being stored and when the objects are being formatted for a view).
  • FIG. 3 shows an exemplary embodiment of a method 200 to determine whether to include a node P n in a detail-reduced version of a geometric representation of a geographic object according to the present invention.
  • the identity of node P last is established.
  • P last may be, for example, an endpoint if the geometric object to be simplified is a polyline, or may be some other beginning point if the geometric object is, for example, a polygon or a polypolygon.
  • P last is repeatedly redefined, as will be discussed below.
  • a threshold distance value (“T”) is defined.
  • T may be any distance that is selected to achieve a desired level of detail reduction in order to improve performance and/or meet storage or processing constraints.
  • the initial threshold value is dynamically adjusted based on Euclidian distance from “directorial objects.
  • the level of detail in any particular location may be dependent on the type of objects that are present in the area.
  • the identity of the nearest directorial object (“O”) to the object that is to be detail-reduced is determined.
  • a directorial object is an object that controls the level of detail reduction. Any object or set of objects may be defined as directorial. For example, in a GIS application displaying fiber-optic cables, the fiber-optic cable layer may be classified as “directorial.” Thus, every fiber-optic cable object will be a directorial object.
  • the objects on other layers e.g., streets, political boundaries, hydrologic features, etc.
  • more than one layer or more than one type of object may be defined to be directorial.
  • step 220 the distance from the previous included point, P last , to the point being evaluated, P n , is determined.
  • P last may be, for example, an endpoint. It may be assumed that the endpoint will remain in the data set. Thus, the evaluated point P n will be the next closest node to the endpoint. As the data reduction process continues, P last will increment to be the node that was the last node to remain in the data set (i.e. a node that was evaluated and not reduced from the data set).
  • step 225 the distance from P n to the nearest directorial object O is determined.
  • the threshold value T is weighted based on the proximity of P n to O.
  • the weighted value is set to T*ln(1+ ⁇ (P n ,O).
  • the weighting may be based on any other function of the threshold value T and the distance between P n and O.
  • Other data reduction algorithms may be used to evaluate whether to exclude P n from the data set.
  • Another exemplary data reduction algorithm may evaluate P n based on angular displacement.
  • a ray drawn from P last to P n would be compared to a ray drawn from P last-1 (the included node prior to P last ) to P last , and P n would be included in the detail-reduced version if the angle between the two rays exceeded a given threshold angle.
  • the threshold angle could be weighted based on the distance between P n and the nearest directorial object O.
  • the test being applied in step 230 is a node inclusion test, i.e., if the value is greater than the weighted threshold, the node remains included in the data set.
  • the node inclusion test performed in step 230 may be represented as ⁇ (P n ,P last )
  • step 230 If, in step 230 , the current node P n does not pass the node inclusion test, the process continues to step 235 , where the current P n being evaluated is removed from the detail-reduced version of the geometric representation. The method then moves to step 240 to consider the next P n Operation of the method then repeats beginning at step 215 , which is discussed above.
  • step 230 If, in step 230 , the current node P n passes the node inclusion test, the process continues to step 245 , where P n is included in the detail-reduced version of the geometric object being detail-reduced.
  • step 250 the current P n , having been included in the detail-reduced version, is established as the new P last (the last included point).
  • step 255 P n is redefined as the next point being considered for elimination. After step 255 , operation of the method then repeats beginning at step 215 , which is discussed above.
  • FIGS. 4 a and 4 b show an example of node reduction as performed by the exemplary method of FIG. 3 .
  • FIG. 4 a shows an exemplary geometric representation of a geographic object before node reduction;
  • FIG. 4 b shows the same geometric representation after node reduction has been performed.
  • the node reduction illustrated through FIGS. 4 a and 4 b is only intended to demonstrate, in general terms, the results of the exemplary method, calculations pertaining to the method discussed above will not be shown.
  • the Euclidian distance is used in the node reduction, and FIGS. 4 a and 4 b are not intended to be drawn to scale.
  • Object 305 a comprises nodes 310 a , 311 a , 312 a , 313 a , 314 a , 315 a , 316 a , 317 a , 318 a , 319 a , 320 a , 321 a , 322 a , 323 a , 324 a , 325 a .
  • Directorial object 330 a / 330 b is of the type discussed above in reference to step 215 .
  • Object 305 b shows object 305 a after the exemplary method of FIG.
  • 3 has been applied, and comprises nodes 310 b , 312 b , 314 b , 316 b , 317 b , 318 b , 319 b , 320 b , 321 b , 323 b , 325 b.
  • nodes 311 a , 313 a , 315 a , 322 a , and 324 a may be eliminated (resulting in the absence of nodes 311 b , 313 b , 315 b , 322 b , and 324 b ). While the distance from node 316 a to node 317 a is comparable to the distance from node 310 a to node 311 a , the weighting of the threshold distance T on the basis the proximity of P n to the nearest directorial object 330 a may cause node 317 b to be kept in detail-reduced object 305 b , while node 311 a may be eliminated.
  • node 322 a is further from directorial object 330 a than, for example, node 318 a , node 322 a may be eliminated while node 318 b is not, though both are of comparable distance from their preceding nodes.
  • a higher level of detail may remain in the portion of object 305 b that is closest to directorial object 330 b , while more detail may be eliminated further away from directorial object 330 b .
  • very large reductions in data set size and increases in performances can be achieved, without sacrificing image detail where it is relevant to the needs of the application.
  • detail reduction shown by exemplary FIGS. 4 a and 4 b is 31.25% (removal of 5 nodes from an original set of 16)
  • the exemplary method can achieve significantly larger detail reduction, on the order of 1,000%.
  • the exemplary method is suited for both demand-based detail reduction and for batch processing of large GIS data sets.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Databases & Information Systems (AREA)
  • Educational Administration (AREA)
  • Business, Economics & Management (AREA)
  • Educational Technology (AREA)
  • Mathematical Physics (AREA)
  • Remote Sensing (AREA)
  • Data Mining & Analysis (AREA)
  • General Engineering & Computer Science (AREA)
  • Processing Or Creating Images (AREA)

Abstract

A system and method for storing a plurality data points, each data point representing a geographic location, a first set of data points representing a first geometric object and a second set of data points representing a second geometric object. The system and method then remove a first data point from the first set of data points representing the first geometric object based on at least a distance between a first location represented by the first data point and a second location represented by a second data point of the second set of data points representing a second geometric object.

Description

    BACKGROUND INFORMATION
  • Geographic Information Systems (“GIS”) are computer applications used to manipulate and display geographic data. The data is typically stored as geometric objects, each constituting one or more longitude/latitude points (e.g., points, polylines, polygons and polypolygons). Such geometric representations of geographic objects can be extremely complex, depending on the precision of the representation. For example, a state boundary may constitute ten thousand points (sometimes referred to as “nodes”) or more, and a small stretch of coastline can require millions of points if submeter resolution is required.
  • SUMMARY OF THE INVENTION
  • A method for storing a plurality data points, each data point representing a geographic location, a first set of data points representing a first geometric object and a second set of data points representing a second geometric object and removing a first data point from the first set of data points representing the first geometric object based on at least a distance between a first location represented by the first data point and a second location represented by a second data point of the second set of data points representing a second geometric object.
  • A system having a data storage mechanism storing a plurality data points, each data point representing a geographic location, a first set of data points representing a first geometric object and a second set of data points representing a second geometric object and a data reducer removing a first data point from the first set of data points representing the first geometric object based on at least a distance between a first location represented by the first data point and a second location represented by a second data point of the second set of data points representing a second geometric object.
  • A method for storing a plurality data points, each data point representing a geographic location, a first set of data points representing a first geometric object and a second set of data points representing a second geometric object, determining a first distance between a first location represented by a first data point of the first set of data points representing the first geometric object and a second location represented by a second data point of the first set of data points representing the first geometric object, determining a second distance between the first location and a third location represented by a third data point of the second set of data points representing the second geometric object and determining a relationship between the first and second distances, wherein the first data point is one of removed from the first set of data points and maintained in the first set of data points based on the relationship between the first and second distances.
  • A method for storing a plurality data points, each data point representing a geographic location, a first set of data points representing a first geometric object and a second set of data points representing a second geometric object, determining spatial relationships between a plurality of data points of the first set of data points and at least one data point of the second set of data points and removing one data point from the first set of data points based on the spatial relationships.
  • A system having a memory for storing a set of instructions and a processor to execute the set of instructions. The set of instructions being operable to store a plurality data points, each data point representing a geographic location, a first set of data points representing a first geometric object and a second set of data points representing a second geometric object and remove a first data point from the first set of data points representing the first geometric object based on at least a distance between a first location represented by the first data point and a second location represented by a second data point of the second set of data points representing a second geometric object.
  • DESCRIPTION OF THE DRAWINGS
  • FIG. 1 shows an exemplary table of layers that may be included in a GIS application.
  • FIG. 2 illustrates an exemplary data reduction system for use with GIS applications according to the present invention.
  • FIG. 3 illustrates an exemplary embodiment of a method to determine whether to include a node Pn in a detail-reduced version of a geometric representation of a geographic object according to the present invention.
  • FIGS. 4 a and 4 b illustrate views of an exemplary geometric representation of a geographic object as contained in a GIS application, before and after application of the exemplary data reduction method of FIG. 3.
  • DETAILED DESCRIPTION
  • The present invention may be further understood with reference to the following description and the appended drawings, wherein like elements are referred to with the same reference numerals. The exemplary embodiments of the present invention describe a system and method for determining whether to include a point Pn when reducing the detail of a geometric representation of geographic objects. The exemplary system and method will be further discussed in detail below.
  • An exemplary GIS display may show various geographical features at varying levels of detail depending on the zoom factor desired by the user. The GIS display may include different types of geographical features on different layers. FIG. 1 shows an exemplary Table 1 showing exemplary layers 10-60 in an exemplary GIS display. This exemplary display includes six (6) layers including Layer 1 (10) having land/water boundaries (e.g., coastline, rivers, etc.); Layer 2 (20) having roads; Layer 3 (30) having buildings; Layer 4 (40) having fiber optic cable runs; Layer 5 (50) having electrical cable runs; and Layer 6 (60) having water line runs. Each of the geographic features in each of the layers 10-60 may be combined to provide exemplary GIS display for the desired geographic area.
  • Those skilled in the art will understand that the layers described above are only exemplary, and that these and other layers may also be included in or excluded from the GIS display based on the needs of the user. These additional layers may include natural features (e.g., mountains, forests, etc.), man-made features (e.g., streets, gas lines, sewer lines, etc.), and political subdivisions (e.g., state, county, city boundaries, etc.). In addition, each layer may include sub-layers. For example, Layer 5 (50) having electrical cables may include a first sub-layer showing all 480V electrical cables and a second sub-layer showing all 2 kV electrical cables. Those skilled in the art will also understand that the layering model is only exemplary and that the GIS display/system does not need to implement geographical features by layers.
  • FIG. 2 shows an exemplary GIS system 100 according to the present invention. The GIS system 100 may store each of the geometric objects in a data storage 110 (e.g., a database) as a set of points or nodes. Throughout this description the terms “points” and “nodes” will be used interchangeably to describe the data used to create the geometric objects. In one exemplary embodiment, this data is a latitude/longitude pair defining a geographic location, e.g., each point or node includes data representing a latitude/longitude location. Those skilled in the art will understand that the use of a database as a data storage mechanism 110 is only exemplary. Other known data storage mechanisms 110 may also be used. The GIS system 100 may then transmit the objects via a view generator 130 to a client application (e.g., GIS display 140), that allows “panning” and “zooming” of the GIS display. As described previously, each of the objects may include hundreds or thousands of nodes and there may be many objects on any particular display. Thus, due to the immense amount of data involved, it may be desirable for objects shown at higher zoom levels (i.e. lower magnification) to be transmitted and represented in reduced detail. It should be noted that FIG. 2, which shows the GIS display 140 as external to the GIS system 100, is only exemplary, and that a GIS system may have a GIS display as part of the system.
  • Therefore, the exemplary GIS system 100 includes a data reducer 120 to reduce the number of data points that are used to represent an object. In one exemplary embodiment of the present invention, the data reducer 120 reduces the data points representing various objects prior to transmission of the objects by the view generator 130 to the client application (e.g., GIS display 140). In this exemplary embodiment, the GIS system 100 will continue to store all the points associated with each object in data storage 110, but the data reducer 120 will limit the data that is sent by the view generator 130 to the GIS display 140. Specifically, the data reduction is performed when the GIS system 100 receives a specific view request from the GIS display 140.
  • In another exemplary embodiment, the data reducer 120 is used to limit the number of data points that are stored for each object in data storage 110. Specifically, the data reduction is performed when the GIS system 100 is storing the objects representing the geographical information, resulting in a reduced-size data set. Thus, in this exemplary embodiment, the data reduction may be used to limit storage and/or processing requirements within the GIS system 100, in addition to the reduced set of transmitted points described in the above exemplary embodiment. Those skilled in the art will also understand that the data reducer 120 may be used to implement both of the above described data reductions (e.g., when the objects are being stored and when the objects are being formatted for a view).
  • The data reducer 120 is used to remove some fraction of the object's points/nodes based on a desired level of detail reduction. FIG. 3 shows an exemplary embodiment of a method 200 to determine whether to include a node Pn in a detail-reduced version of a geometric representation of a geographic object according to the present invention. In step 205, the identity of node Plast is established. At the beginning of the detail reduction process, Plast may be, for example, an endpoint if the geometric object to be simplified is a polyline, or may be some other beginning point if the geometric object is, for example, a polygon or a polypolygon. As the method iterates, Plast is repeatedly redefined, as will be discussed below.
  • In step 210, a threshold distance value (“T”) is defined. T may be any distance that is selected to achieve a desired level of detail reduction in order to improve performance and/or meet storage or processing constraints. As will be described in greater detail below, in the exemplary data reduction method, the initial threshold value is dynamically adjusted based on Euclidian distance from “directorial objects. Thus, the level of detail in any particular location may be dependent on the type of objects that are present in the area.
  • In step 215, the identity of the nearest directorial object (“O”) to the object that is to be detail-reduced is determined. A directorial object is an object that controls the level of detail reduction. Any object or set of objects may be defined as directorial. For example, in a GIS application displaying fiber-optic cables, the fiber-optic cable layer may be classified as “directorial.” Thus, every fiber-optic cable object will be a directorial object. The objects on other layers (e.g., streets, political boundaries, hydrologic features, etc.) may then be node-reduced on the basis of their proximity to fiber-optic cable objects. For example, a highway may have less detail removed in areas where it closely approaches a fiber-optic cable, and more detail removed in other areas. Those skilled in the art will understand that more than one layer or more than one type of object may be defined to be directorial.
  • In step 220, the distance from the previous included point, Plast, to the point being evaluated, Pn, is determined. As described above, at the beginning of the reduction process Plast may be, for example, an endpoint. It may be assumed that the endpoint will remain in the data set. Thus, the evaluated point Pn will be the next closest node to the endpoint. As the data reduction process continues, Plast will increment to be the node that was the last node to remain in the data set (i.e. a node that was evaluated and not reduced from the data set). In step 225, the distance from Pn to the nearest directorial object O is determined.
  • In step 230, the threshold value T is weighted based on the proximity of Pn to O. In this exemplary embodiment, the weighted value is set to T*ln(1+∥(Pn,O). Those skilled in the art will understand that the above weighted value is only exemplary, and that the weighting may be based on any other function of the threshold value T and the distance between Pn and O. It should be noted that other data reduction algorithms may be used to evaluate whether to exclude Pn from the data set. Another exemplary data reduction algorithm may evaluate Pn based on angular displacement. For example, a ray drawn from Plast to Pn would be compared to a ray drawn from Plast-1 (the included node prior to Plast) to Plast, and Pn would be included in the detail-reduced version if the angle between the two rays exceeded a given threshold angle. As in the previous exemplary algorithm, the threshold angle could be weighted based on the distance between Pn and the nearest directorial object O.
  • It should also be noted that while the determination is shown in equation form, other methods of making the determination (e.g., using a lookup array that substitutes fixed threshold values for given distance ranges) may also be used. While this description describes a node reduction process, the test being applied in step 230 is a node inclusion test, i.e., if the value is greater than the weighted threshold, the node remains included in the data set. The node inclusion test performed in step 230 may be represented as ∥(Pn,Plast)|>T*ln(1+∥(Pn,O)∥), wherein node Pn is included in the detail-reduced data set if the indicated greater-than test is true.
  • If, in step 230, the current node Pn does not pass the node inclusion test, the process continues to step 235, where the current Pn being evaluated is removed from the detail-reduced version of the geometric representation. The method then moves to step 240 to consider the next Pn Operation of the method then repeats beginning at step 215, which is discussed above.
  • If, in step 230, the current node Pn passes the node inclusion test, the process continues to step 245, where Pn is included in the detail-reduced version of the geometric object being detail-reduced. In step 250, the current Pn, having been included in the detail-reduced version, is established as the new Plast (the last included point). In step 255, Pn is redefined as the next point being considered for elimination. After step 255, operation of the method then repeats beginning at step 215, which is discussed above.
  • FIGS. 4 a and 4 b show an example of node reduction as performed by the exemplary method of FIG. 3. FIG. 4 a shows an exemplary geometric representation of a geographic object before node reduction; FIG. 4 b shows the same geometric representation after node reduction has been performed. As the node reduction illustrated through FIGS. 4 a and 4 b is only intended to demonstrate, in general terms, the results of the exemplary method, calculations pertaining to the method discussed above will not be shown. Specifically, as described above, the Euclidian distance is used in the node reduction, and FIGS. 4 a and 4 b are not intended to be drawn to scale.
  • Object 305 a comprises nodes 310 a, 311 a, 312 a, 313 a, 314 a, 315 a, 316 a, 317 a, 318 a, 319 a, 320 a, 321 a, 322 a, 323 a, 324 a, 325 a. Directorial object 330 a/330 b is of the type discussed above in reference to step 215. Object 305 b shows object 305 a after the exemplary method of FIG. 3 has been applied, and comprises nodes 310 b, 312 b, 314 b, 316 b, 317 b, 318 b, 319 b, 320 b, 321 b, 323 b, 325 b.
  • After application of the node reduction method, nodes 311 a, 313 a, 315 a, 322 a, and 324 a may be eliminated (resulting in the absence of nodes 311 b, 313 b, 315 b, 322 b, and 324 b). While the distance from node 316 a to node 317 a is comparable to the distance from node 310 a to node 311 a, the weighting of the threshold distance T on the basis the proximity of Pn to the nearest directorial object 330 a may cause node 317 b to be kept in detail-reduced object 305 b, while node 311 a may be eliminated. Similarly, because node 322 a is further from directorial object 330 a than, for example, node 318 a, node 322 a may be eliminated while node 318 b is not, though both are of comparable distance from their preceding nodes.
  • By application of the exemplary method, a higher level of detail may remain in the portion of object 305 b that is closest to directorial object 330 b, while more detail may be eliminated further away from directorial object 330 b. Thus, by applying the exemplary method, very large reductions in data set size and increases in performances can be achieved, without sacrificing image detail where it is relevant to the needs of the application. While the detail reduction shown by exemplary FIGS. 4 a and 4 b is 31.25% (removal of 5 nodes from an original set of 16), it should be noted that, when used in actual GIS applications, the exemplary method can achieve significantly larger detail reduction, on the order of 1,000%. The exemplary method is suited for both demand-based detail reduction and for batch processing of large GIS data sets.
  • Those skilled in the art will understand that the above described exemplary embodiment may be implemented in any number of manners, including, for example, as a separate software module, as a combination of software, etc.
  • It will be apparent to those skilled in the art that various modifications may be made in the present invention, without departing from the spirit or scope of the invention. Thus, it is intended that the present invention cover the modifications and variations of this invention provided they come within the scope of the appended claims and their equivalents.

Claims (21)

1-23. (canceled)
24. A system, comprising:
a data storage mechanism that stores data points, wherein each data point comprises of a latitudinal and longitudinal coordinate; and
a processor that executes instructions to cause the processor to perform operations, comprising:
removing a first data point from a first set of the data points based on i) a first distance between a first coordinate represented by the first data point and a second coordinate represented by a second data point of a second set of the data points, ii) a second distance between the first coordinate represented by the first data point and a third coordinate represented by a third data point of the first set of data points, and iii) a relationship between the first and second distances.
25. The system of claim 24, wherein the first set of data points represents a first geometric object and the second set of data points represents a second geometric object.
26. The system of claim 25, wherein the operations further comprise:
generating a viewable display including the first geometric object without the first data point; and
generating the viewable display including the second geometric object.
27. The system of claim 26, further comprising:
a display displaying the viewable display of the first and second geometric objects.
28. The system of claim 26, wherein a value of one of the first distance, the second distance or the relationship between the first and second distances is based on a level of detail reduction of the first geometric object in the viewable display.
29. The system of claim 24, wherein after the first data point is removed, the first set of data points are re-stored in the data storage mechanism without the first data point.
30. The system of claim 25, wherein the operations further comprise:
removing a fourth data point from the first set of data points based on i) a third distance between a fourth coordinate represented by the fourth data point and a fifth coordinate represented by a fifth data point of the second set of data points, ii) a fourth distance between the fourth coordinate represented by the fourth data point and a sixth coordinate represented by a sixth data point of the first set of data points, and iii) a relationship between the third and fourth distances.
31. The system of claim 30, wherein the second data point and the fifth data point are the same data points.
32. The system of claim 30, wherein the removing processes are repeated until a desired level of detail reduction of the first geometric object is achieved.
33. A method, comprising:
storing a plurality of data points, wherein each data point comprises of a latitudinal and longitudinal coordinate;
removing a first data point from a first set of data points based on i) a first distance between a first coordinate represented by the first data point and a second coordinate represented by a second data point of a second set of data points, ii) a second distance between the first coordinate represented by the first data point and a third coordinate represented by a third data point of the first set of data points, and iii) a relationship between the first and second distances.
34. The method of claim 33, wherein the first set of data points represents a first geometric object and the second set of data points represents a second geometric object.
35. The method of claim 34, wherein the removing is further based on a dynamic threshold value, the dynamic threshold value being set based on a zoom level at which the first and second geometric objects are to be displayed.
36. The method of claim 33, further comprising:
generating a viewable display including the first geometric object without the first data point; and
generating the viewable display including the second geometric object.
37. The method of claim 33, further comprising:
receiving an indication defining the second geometric object as a directorial object.
38. The method of claim 33, wherein the removing is based on the following formula:

∥(P n ,P last)|>T*ln(1+∥(P n ,O)∥),
where Pn is the first data point, Plast is a further data point of the first geometric object, T is a threshold value and O is the second data point.
39. A method, comprising:
determining a first distance between a first location represented by a first data point of a first set of data points and a second location represented by a second data point of the first set of data points, wherein each data point represents a latitude and longitude coordinate;
determining a second distance between the first location and a third location represented by a third data point of the second set of data points; and
determining a relationship between the first and second distances.
40. The method of claim 39, wherein each set of data points is organized into a geometric object.
41. The method of claim 39, wherein the relationship between the first and second distances is determined based on the following formula:

∥(P n ,P last)|>T*ln(1+∥(P n ,O)∥),
where Pn is the first data point, Plast is the second data point, T is a threshold value and O is the third data point.
42. The method of claim 39, further comprising:
removing the first data point from the first set of data points based on the relationship between the first and second distances;
determining, when the first data point is removed from the first set of data points, a third distance between a fourth location represented by a fourth data point of the first set of data points and the second location;
determining a fourth distance between the fourth location and the third location; and
determining a further relationship between the third and fourth distances, wherein the fourth data point is one of removed from the first set of data points and maintained in the first set of data points based on the further relationship between the third and fourth distances.
43. The non-transitory memory of claim 39, wherein the method further comprises:
maintaining the first data point in the first set of data points based on the relationship between the first and second distances;
determining, when the first data point is maintained in the first set of data points, a third distance between a fourth location represented by a fourth data point of the first set of data points and the first location;
determining a fourth distance between the fourth location and the third location; and
determining a further relationship between the third and fourth distances, wherein the fourth data point is one of removed from the first set of data points and maintained in the first set of data points based on the further relationship between the third and fourth distances.
US14/950,664 2007-02-21 2015-11-24 Proximity-Base Detail Reduction of Geographic Data Abandoned US20160078651A1 (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
US14/950,664 US20160078651A1 (en) 2007-02-21 2015-11-24 Proximity-Base Detail Reduction of Geographic Data

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US11/708,835 US9208593B1 (en) 2007-02-21 2007-02-21 Proximity-based detail reduction of geographic data
US14/950,664 US20160078651A1 (en) 2007-02-21 2015-11-24 Proximity-Base Detail Reduction of Geographic Data

Related Parent Applications (1)

Application Number Title Priority Date Filing Date
US11/708,835 Continuation US9208593B1 (en) 2007-02-21 2007-02-21 Proximity-based detail reduction of geographic data

Publications (1)

Publication Number Publication Date
US20160078651A1 true US20160078651A1 (en) 2016-03-17

Family

ID=54708356

Family Applications (2)

Application Number Title Priority Date Filing Date
US11/708,835 Expired - Fee Related US9208593B1 (en) 2007-02-21 2007-02-21 Proximity-based detail reduction of geographic data
US14/950,664 Abandoned US20160078651A1 (en) 2007-02-21 2015-11-24 Proximity-Base Detail Reduction of Geographic Data

Family Applications Before (1)

Application Number Title Priority Date Filing Date
US11/708,835 Expired - Fee Related US9208593B1 (en) 2007-02-21 2007-02-21 Proximity-based detail reduction of geographic data

Country Status (1)

Country Link
US (2) US9208593B1 (en)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2017165470A3 (en) * 2016-03-25 2017-11-30 Microsoft Technology Licensing, Llc Multiple texture variable opacity stroke rendering and blending
US9888396B2 (en) * 2016-03-22 2018-02-06 Toyota Jidosha Kabushiki Kaisha RF resource allocation device and method, and radio communication system

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US10839569B2 (en) * 2016-02-03 2020-11-17 NorthStar Memorial Group LLC System for geospatial mapping of cemetery properties

Family Cites Families (12)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5566288A (en) * 1994-09-02 1996-10-15 Caterpillar Inc. System and method for automatically fitting a B-spline curve to a set of data points
US5859651A (en) 1996-08-19 1999-01-12 International Business Machines Corporation Method and apparatus for block data transfer to reduce on-chip storage for interpolative video resizing
US5983224A (en) 1997-10-31 1999-11-09 Hitachi America, Ltd. Method and apparatus for reducing the computational requirements of K-means data clustering
US6249740B1 (en) * 1998-01-21 2001-06-19 Kabushikikaisha Equos Research Communications navigation system, and navigation base apparatus and vehicle navigation apparatus both used in the navigation system
JP2000059227A (en) 1998-08-07 2000-02-25 Matsushita Electric Ind Co Ltd Encoding and decoding device and its method
JP3283005B2 (en) 1998-11-05 2002-05-20 インターナショナル・ビジネス・マシーンズ・コーポレーション A data transfer method that prevents the transition of image data
US6343301B1 (en) * 1999-02-24 2002-01-29 Navigation Technologies Corp. Method and system for collecting data for updating a geographic database
US6674434B1 (en) * 1999-10-25 2004-01-06 Navigation Technologies Corp. Method and system for automatic generation of shape and curvature data for a geographic database
US7552008B2 (en) * 2001-07-18 2009-06-23 Regents Of The University Of Minnesota Populating geospatial database for onboard intelligent vehicle applications
US6704648B1 (en) * 2002-05-29 2004-03-09 Navigation Technologies Corp. Bearing data for route guidance
US6993538B2 (en) * 2003-01-28 2006-01-31 Microsoft Corporation System and process for identifying objects and/or points nearby a given object or point
US7477988B2 (en) * 2006-05-16 2009-01-13 Navteq North America, Llc Dual road geometry representation for position and curvature-heading

Cited By (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9888396B2 (en) * 2016-03-22 2018-02-06 Toyota Jidosha Kabushiki Kaisha RF resource allocation device and method, and radio communication system
US10212616B2 (en) 2016-03-22 2019-02-19 Toyota Jidosha Kabushiki Kaisha RF resource allocation device and method, and radio communication system
WO2017165470A3 (en) * 2016-03-25 2017-11-30 Microsoft Technology Licensing, Llc Multiple texture variable opacity stroke rendering and blending
US10235778B2 (en) 2016-03-25 2019-03-19 Microsoft Technology Licensing, Llc GPU-accelerated pencil ink effect rendering
US10269143B2 (en) 2016-03-25 2019-04-23 Microsoft Technology Licensing, Llc Multiple texture variable opacity stroke rendering and blending
US10282867B2 (en) 2016-03-25 2019-05-07 Microsoft Technology Licensing, Llc Shading for variable opacity stroke rendering

Also Published As

Publication number Publication date
US9208593B1 (en) 2015-12-08

Similar Documents

Publication Publication Date Title
EP3828720A2 (en) Method and apparatus for merging data of building blocks, device and storage medium
US11703352B2 (en) Vector tile pyramiding
US20070182743A1 (en) Displaying visual content using multiple nodes
US8237745B1 (en) Label positioning technique to reduce crawling during zoom activities
CN110832278B (en) Rendering map data using a description of raster differences
US20080294332A1 (en) Method for Image Based Navigation Route Corridor For 3D View on Mobile Platforms for Mobile Users
EP2518445B1 (en) Database for a navigation device, method of outputting a three-dimensional representation of a terrain and method of generating a database
Ferrais et al. Asteroid (16) Psyche’s primordial shape: A possible Jacobi ellipsoid
JP2005228320A (en) High-speed visualization method, apparatus, and program for 3D graphic data based on depth image
CN103403769A (en) Planetary scale object rendering
US20160078651A1 (en) Proximity-Base Detail Reduction of Geographic Data
Faust et al. Real-time global data model for the digital earth
CN105960659A (en) Method for selecting data files for downloading
CN113722409A (en) Method and device for determining spatial relationship, computer equipment and storage medium
CN112115226A (en) Map rendering method and map rendering device
WO2009055184A2 (en) Method and system for rendering simplified point finding maps
US7395257B2 (en) Automated method and system to calculate the surface distance between two geographical locations, and to filter a data set based on the calculation
CN108446303B (en) Method and device for aggregation display and hierarchical aggregation of map nodes
KR101487454B1 (en) method for parallel processing of LOD image
US20070229510A1 (en) Displaying of Vector Graphics, in Particular of Geographical Maps
US10460427B2 (en) Converting imagery and charts to polar projection
US20190156455A1 (en) Converting Spatial Features to Map Projection
She et al. A building label placement method for 3D visualizations based on candidate label evaluation and selection
CN114022518A (en) Method, device, equipment and medium for acquiring optical flow information of image
Amiraghdam et al. LOOPS: LOcally Optimized Polygon Simplification

Legal Events

Date Code Title Description
AS Assignment

Owner name: AT&T INTELLECTUAL PROPERTY II, LP, GEORGIA

Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:ASHER, MICHAEL L.;REEL/FRAME:037134/0458

Effective date: 20070207

STCV Information on status: appeal procedure

Free format text: ON APPEAL -- AWAITING DECISION BY THE BOARD OF APPEALS

STCV Information on status: appeal procedure

Free format text: BOARD OF APPEALS DECISION RENDERED

STCB Information on status: application discontinuation

Free format text: ABANDONED -- AFTER EXAMINER'S ANSWER OR BOARD OF APPEALS DECISION

点击 这是indexloc提供的php浏览器服务,不要输入任何密码和下载