Simplification of data for representing an environment, via the reduction of vertices that define structures represented in the data
First Claim
1. A method for determining visibility between points in a geographic region in which buildings are present, the method comprising:
- receiving, by a data-processing system, a first dataset that is representative of a first building that is defined by a first polyhedron having a footprint defined by a first polygon, wherein a first vertex and a second vertex define a first edge of the first polygon, and wherein the second vertex and a third vertex define a second edge of the first polygon;
reducing, by the data-processing system, the number of vertices in the first polygon, at least in part by i) removing the second vertex only if the first edge does not exceed a predetermined first length and ii) removing the third vertex, resulting in a second polygon;
transmitting, by the data-processing system to an application engine, a second dataset that comprises a second polyhedron having a footprint defined by the second polygon, wherein the second polyhedron defines the first building in the geographic region, and wherein at least some faces of the second polyhedron define outer walls of the first building;
calculating, by the application engine, visibility between two points in the geographic region that are represented in the second dataset, by determining whether any of the at least some faces of the second polyhedron obstruct a line-of-sight line between the two points; and
presenting, to a user, a result that is based on the visibility calculated.
1 Assignment
0 Petitions
Accused Products
Abstract
A technique for simplifying structure data for representing an environment. Polyhedrons can make up structure data used in an application such as modeling, visualization, and navigation. Consequently, the operations that are performed on the data often involve determining, for each polyhedron that defines a structure such as a building, whether the polyhedron obstructs a line-of-sight line between a first point in space being considered in the application and a second point. In order to determine whether a polyhedron obstructs a line-of-sight line, a data-processing system operating on the structure data must determine whether any walls of the polyhedron intersect the line. Thus, the more polyhedrons there are or the more vertices that are in each polyhedron, the more walls there are, and the more intersection checks are required, thereby adding to the computations. The disclosed technique reduces the number of walls by simplifying objects that make up the structure data.
-
Citations
20 Claims
-
1. A method for determining visibility between points in a geographic region in which buildings are present, the method comprising:
-
receiving, by a data-processing system, a first dataset that is representative of a first building that is defined by a first polyhedron having a footprint defined by a first polygon, wherein a first vertex and a second vertex define a first edge of the first polygon, and wherein the second vertex and a third vertex define a second edge of the first polygon; reducing, by the data-processing system, the number of vertices in the first polygon, at least in part by i) removing the second vertex only if the first edge does not exceed a predetermined first length and ii) removing the third vertex, resulting in a second polygon; transmitting, by the data-processing system to an application engine, a second dataset that comprises a second polyhedron having a footprint defined by the second polygon, wherein the second polyhedron defines the first building in the geographic region, and wherein at least some faces of the second polyhedron define outer walls of the first building; calculating, by the application engine, visibility between two points in the geographic region that are represented in the second dataset, by determining whether any of the at least some faces of the second polyhedron obstruct a line-of-sight line between the two points; and presenting, to a user, a result that is based on the visibility calculated. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A method for determining visibility between points in a geographic region in which buildings are present, the method comprising:
-
receiving, by a data-processing system, a first dataset that is representative of a first building that is defined by a first polyhedron having a footprint defined by a first polygon having a plurality of vertices; identifying, by the data-processing system and in the plurality, each vertex that is non-removable based on each non-removable vertex defining in part a corresponding edge that exceeds a predetermined first length; removing, by the data-processing system and from the plurality, a first vertex not identified as being non-removable, wherein the removing of the first vertex based on an edge defined by the first vertex not exceeding a predetermined second length, wherein the second length is shorter than the first length, and wherein the removing of the first vertex at least in part results in a second polygon; transmitting, by the data-processing system to an application engine, a second dataset that comprises a second polyhedron having a footprint defined by the second polygon, wherein the second polyhedron defines the first building in the geographic region, and wherein at least some faces of the second polyhedron define outer walls of the first building; calculating, by the application engine, visibility between two points in the geographic region that are represented in the second dataset, by determining whether any of the at least some faces of the second polyhedron obstruct a line-of-sight line between the two points; and presenting, to a user, a result that is based on the visibility calculated. - View Dependent Claims (12, 13, 14, 15, 16)
-
-
17. A method for determining visibility between points in a geographic region in which buildings are present, the method comprising:
-
receiving, by a data-processing system, a first dataset that is representative of a first building that is defined by a first polyhedron having a footprint defined by a first polygon having a plurality of vertices; identifying, by the data-processing system and in the plurality, each vertex that is non-removable based on each non-removable vertex defining in part a corresponding edge that exceeds a predetermined first length; assessing, by the data-processing system and in relation to a first control vertex of the first polygon, each successive vertex of the first polygon along a fixed direction, such that for each successive vertex being assessed, the data-processing system removes the vertex being assessed if it is within a predetermined second length from the first control vertex, unless the vertex being assessed is identified as being non-removable, wherein the second length is shorter than the first length, and wherein the assessing proceeds until a vertex is encountered that is not removed; identifying the vertex that is not removed as a second control vertex; assessing, by the data-processing system and in relation to the second control vertex, each successive vertex of the first polygon along the fixed direction, wherein for each successive vertex being assessed, the data-processing system removes the vertex being assessed if it is within the predetermined second length from the second control vertex, unless the vertex being assessed is identified as being non-removable, and wherein the assessing in relation to the second control vertex results at least in part in a second polygon; transmitting, by the data-processing system to an application engine, a second dataset that comprises a second polyhedron having a footprint defined by the second polygon, wherein the second polyhedron defines the first building in the geographic region, and wherein at least some faces of the second polyhedron define outer walls of the first building; calculating, by the application engine, visibility between two points in the geographic region that are represented in the second dataset, by determining whether any of the at least some faces of the second polyhedron obstruct a line-of-sight line between the two points; and presenting, to a user, a result that is based on the visibility calculated. - View Dependent Claims (18, 19, 20)
-
Specification