US20160078651A1 - Proximity-Base Detail Reduction of Geographic Data - Google Patents
Proximity-Base Detail Reduction of Geographic Data Download PDFInfo
- 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
Links
- 230000009467 reduction Effects 0.000 title claims description 25
- 238000000034 method Methods 0.000 claims abstract description 39
- 238000013500 data storage Methods 0.000 claims description 8
- 230000007246 mechanism Effects 0.000 claims description 5
- 230000008569 process Effects 0.000 claims description 3
- 239000003638 chemical reducing agent Substances 0.000 description 7
- 238000012360 testing method Methods 0.000 description 6
- 238000011946 reduction process Methods 0.000 description 4
- 238000004422 calculation algorithm Methods 0.000 description 3
- 238000012545 processing Methods 0.000 description 3
- 238000012986 modification Methods 0.000 description 2
- 230000004048 modification Effects 0.000 description 2
- XLYOFNOQVPJJNP-UHFFFAOYSA-N water Substances O XLYOFNOQVPJJNP-UHFFFAOYSA-N 0.000 description 2
- 238000013459 approach Methods 0.000 description 1
- 230000005540 biological transmission Effects 0.000 description 1
- 238000004364 calculation method Methods 0.000 description 1
- 238000004883 computer application Methods 0.000 description 1
- 230000001419 dependent effect Effects 0.000 description 1
- 238000006073 displacement reaction Methods 0.000 description 1
- 230000008030 elimination Effects 0.000 description 1
- 238000003379 elimination reaction Methods 0.000 description 1
- 239000000835 fiber Substances 0.000 description 1
- 230000006870 function Effects 0.000 description 1
- 238000004091 panning Methods 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T11/00—2D [Two Dimensional] image generation
- G06T11/20—Drawing from basic elements, e.g. lines or circles
- G06T11/203—Drawing of straight lines or curves
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
- G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
- G06F16/29—Geographical information databases
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T1/00—General purpose image data processing
- G06T1/60—Memory management
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06T—IMAGE DATA PROCESSING OR GENERATION, IN GENERAL
- G06T11/00—2D [Two Dimensional] image generation
- G06T11/40—Filling a planar surface by adding surface attributes, e.g. colour or texture
-
- G—PHYSICS
- G09—EDUCATION; CRYPTOGRAPHY; DISPLAY; ADVERTISING; SEALS
- G09B—EDUCATIONAL OR DEMONSTRATION APPLIANCES; APPLIANCES FOR TEACHING, OR COMMUNICATING WITH, THE BLIND, DEAF OR MUTE; MODELS; PLANETARIA; GLOBES; MAPS; DIAGRAMS
- G09B29/00—Maps; Plans; Charts; Diagrams, e.g. route diagram
- G09B29/10—Map spot or coordinate position indicators; Map reading aids
- G09B29/106—Map 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
- 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.
- 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.
-
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 ofFIG. 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 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 anexemplary GIS system 100 according to the present invention. TheGIS 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 adata storage mechanism 110 is only exemplary. Other knowndata storage mechanisms 110 may also be used. TheGIS system 100 may then transmit the objects via aview 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 thatFIG. 2 , which shows theGIS display 140 as external to theGIS 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 adata reducer 120 to reduce the number of data points that are used to represent an object. In one exemplary embodiment of the present invention, thedata reducer 120 reduces the data points representing various objects prior to transmission of the objects by theview generator 130 to the client application (e.g., GIS display 140). In this exemplary embodiment, theGIS system 100 will continue to store all the points associated with each object indata storage 110, but thedata reducer 120 will limit the data that is sent by theview generator 130 to theGIS display 140. Specifically, the data reduction is performed when theGIS system 100 receives a specific view request from theGIS 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 indata storage 110. Specifically, the data reduction is performed when theGIS 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 theGIS 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 thedata 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 amethod 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. Instep 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). Instep 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 instep 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 atstep 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. Instep 250, the current Pn, having been included in the detail-reduced version, is established as the new Plast (the last included point). Instep 255, Pn is redefined as the next point being considered for elimination. Afterstep 255, operation of the method then repeats beginning atstep 215, which is discussed above. -
FIGS. 4 a and 4 b show an example of node reduction as performed by the exemplary method ofFIG. 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 throughFIGS. 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, andFIGS. 4 a and 4 b are not intended to be drawn to scale. -
Object 305 a comprisesnodes 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 ofFIG. 3 has been applied, and comprisesnodes - After application of the node reduction method,
nodes node 316 a tonode 317 a is comparable to the distance fromnode 310 a tonode 311 a, the weighting of the threshold distance T on the basis the proximity of Pn to the nearestdirectorial object 330 a may causenode 317 b to be kept in detail-reducedobject 305 b, whilenode 311 a may be eliminated. Similarly, becausenode 322 a is further fromdirectorial object 330 a than, for example,node 318 a,node 322 a may be eliminated whilenode 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 todirectorial object 330 b, while more detail may be eliminated further away fromdirectorial 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 exemplaryFIGS. 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)∥),
∥(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)∥),
∥(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.
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)
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)
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)
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 |
-
2007
- 2007-02-21 US US11/708,835 patent/US9208593B1/en not_active Expired - Fee Related
-
2015
- 2015-11-24 US US14/950,664 patent/US20160078651A1/en not_active Abandoned
Cited By (6)
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 |