Simplification of data for representing an environment, based on the heights and elevations of polyhedrons that define structures represented in the data

• US 10,372,835 B2
• Filed: 09/15/2016
• Issued: 08/06/2019
• Est. Priority Date: 09/15/2016
• Status: Active Grant

• Current Assignee: Polaris Wireless Incorporated
• Original Assignee: Polaris Wireless Incorporated
• Inventors: Degli-Esposti, Vittorio, Lu, Jonathan, Vitucci, Enrico Maria
• Primary Examiner(s): Thangavelu, Kandasamy
• Application Number:
  US15/266,899
• Publication Number:
  US 20190042665A1
• Time in Patent Office: 1,055 Days
• CPC Class Codes: F21V 13/10 the elements being reflectors and screens
• CPC Class Codes: G06F 2111/20 Configuration CAD, e.g. designing by assembling or positioning modules selected from libraries of predesigned modules
• CPC Class Codes: G06F 30/00 Computer-aided design [CAD]
• CPC Class Codes: G06F 30/13 Architectural design, e.g. computer-aided architectural design [CAAD] related to design of buildings, bridges, landscapes, production plants or roads
• CPC Class Codes: G06F 30/367 Design verification, e.g. using simulation, simulation program with integrated circuit emphasis [SPICE], direct methods or relaxation methods
• CPC Class Codes: H04B 17/391 Modelling the propagation channel

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.

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 one or more buildings that are defined by a plurality of polyhedrons, including a control polyhedron having a control footprint, wherein each polyhedron in the plurality has a polygon footprint and one or more neighbor polyhedrons, and wherein the first dataset is characterized as having a predetermined error;

determining, by the data-processing system, that a first polyhedron, in a first non-empty set of polyhedrons whose polygon footprints overlap the control footprint, also overlaps in height with the control polyhedron;

determining, by the data-processing system, that a second polyhedron defined as a neighbor polyhedron of the first polyhedron, with a polygon footprint that overlaps the footprint of the first polyhedron, also overlaps in height with the control polyhedron, resulting in a second non-empty set of polyhedrons that overlap in height with the control polyhedron, including the first polyhedron and the second polyhedron;

dividing, by the data-processing system, each polyhedron in the second set of polyhedrons into a base part and a top part, resulting in a third set of polyhedrons;

joining, by the data-processing system, at least a portion of the control polyhedron with all of the base parts of the polyhedrons in the third set of polyhedrons, resulting in a first joined polyhedron, wherein the first joined polyhedron defines a first building in the geographic region, and wherein at least some faces of the first joined polyhedron define outer walls of the first building;

removing a top part from at least one of the polyhedrons in the third set of polyhedrons, based on the height of the top part failing to exceed a value that is based on the predetermined error;

transmitting, by the data-processing system to an application engine, a second dataset that comprises i) the first joined polyhedron and ii) a polyhedron defined by a top part of at least one of the polyhedrons in the third set of polyhedrons, but excludes iii) the removed top part;

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 first joined 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.

2. The method of claim 1 wherein at least one point of the control polyhedron is characterized as having the lowest start elevation in the plurality of polyhedrons.

3. The method of claim 1 further comprising identifying the one or more neighbor polyhedrons by determining, for each polyhedron in the plurality, which polyhedrons are within a given distance.

4. The method of claim 1, wherein the calculating of visibility is part of at least one of modeling, visualization, and navigation.

5. The method of claim 1 wherein the predetermined error is characterized as a particular resolution at which the first dataset is made available.

6. The method of claim 1 wherein the dividing is performed such that each base part has the same end elevation as the control polyhedron, and wherein each top part has a start elevation that is the same as the end elevation of the control polyhedron, the end elevation of a given polyhedron being higher than the start elevation of the given polyhedron.

7. The method of claim 1 further comprising determining, by the data-processing system, that a neighbor polyhedron of the second polyhedron, with a polygon footprint that overlaps the footprint of the second polyhedron, also overlaps in height with the control polyhedron, wherein the second non-empty set of polyhedrons further includes the neighbor polyhedron of the second polyhedron.

8. The method of claim 7 wherein the first polyhedron and the neighbor polyhedron of the second polyhedron are non-overlapping in their polygon footprints.

9. The method of claim 1 further comprising:

selecting, by the data-processing system, a new control polyhedron having a new control footprint, in a fourth set of polyhedrons that comprises all of the top parts of the polyhedrons in the third set of polyhedrons;

determining, by the data-processing system, that a third polyhedron, in a fourth non-empty set of polyhedrons whose polygon footprints overlap the new control footprint, also overlaps in height with the new control polyhedron;

determining, by the data-processing system, that a fourth polyhedron also overlaps in height with the new control polyhedron, resulting in a fifth non-empty set of polyhedrons that overlap in height with the new control polyhedron, including the third polyhedron and the fourth polyhedron;

dividing, by the data-processing system, each polyhedron in the fifth set of polyhedrons into a base part and a top part, resulting in a sixth set of polyhedrons;

joining, by the data-processing system, at least a portion of the new control polyhedron with all of the base parts of the polyhedrons in the sixth set of polyhedrons, resulting in a second joined polyhedron;

wherein the second dataset further comprises the second joined polyhedron.

10. 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 one or more buildings that are defined by a plurality of polyhedrons, including a control polyhedron having a control footprint, wherein each polyhedron in the plurality has a polygon footprint and one or more neighbor polyhedrons, and wherein the first dataset is characterized as having a predetermined error;

determining, by the data-processing system, that a first polyhedron, in a first non-empty set of polyhedrons whose polygon footprints overlap the control footprint, also overlaps in height with the control polyhedron;

determining, by the data-processing system, that a second polyhedron also overlaps in height with the control polyhedron, resulting in a second non-empty set of polyhedrons that overlap in height with the control polyhedron, including the first polyhedron and the second polyhedron;

dividing, by the data-processing system, each polyhedron in the second set of polyhedrons into a base part and a top part, resulting in a third set of polyhedrons;

joining, by the data-processing system, at least a portion of the control polyhedron with all of the base parts of the polyhedrons in the third set of polyhedrons, resulting in a first joined polyhedron, wherein the first joined polyhedron defines a first building in the geographic region, and wherein at least some faces of the first joined polyhedron define outer walls of the first building;

removing a top part from at least one of the polyhedrons in the third set of polyhedrons, based on the height of the top part failing to exceed a value that is based on the predetermined error;

transmitting, by the data-processing system to an application engine, a second dataset that comprises i) the first joined polyhedron and ii) a polyhedron defined by a top part of at least one of the polyhedrons in the third set of polyhedrons, but excludes iii) the removed top part;

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 first joined 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.

11. The method of claim 10 wherein at least one point of the control polyhedron is characterized as having the lowest start elevation in the plurality of polyhedrons.

12. The method of claim 10 wherein the dividing is performed such that each base part has the same end elevation as the control polyhedron, and wherein each top part has a start elevation that is the same as the end elevation of the control polyhedron, the end elevation of a given polyhedron being higher than the start elevation of the given polyhedron.

13. The method of claim 10 further comprising determining, by the data-processing system, that a neighbor polyhedron of the second polyhedron, with a polygon footprint that overlaps the footprint of the second polyhedron, also overlaps in height with the control polyhedron, wherein the second non-empty set of polyhedrons further includes the neighbor polyhedron of the second polyhedron.

14. The method of claim 13 wherein the first polyhedron and the neighbor polyhedron of the second polyhedron are non-overlapping in their polygon footprints.

15. The method of claim 10 further comprising:

selecting, by the data-processing system, a new control polyhedron having a new control footprint, in a fourth set of polyhedrons that comprises all of the top parts of the polyhedrons in the third set of polyhedrons;

determining, by the data-processing system, that a third polyhedron, in a fourth non-empty set of polyhedrons whose polygon footprints overlap the new control footprint, also overlaps in height with the new control polyhedron;

determining, by the data-processing system, that a fourth polyhedron also overlaps in height with the new control polyhedron, resulting in a fifth non-empty set of polyhedrons that overlap in height with the new control polyhedron, including the third polyhedron and the fourth polyhedron;

dividing, by the data-processing system, each polyhedron in the fifth set of polyhedrons into a base part and a top part, resulting in a sixth set of polyhedrons;

joining, by the data-processing system, at least a portion of the new control polyhedron with all of the base parts of the polyhedrons in the sixth set of polyhedrons, resulting in a second joined polyhedron;

wherein the second dataset further comprises the second joined polyhedron.

16. 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 one or more buildings that are defined by a plurality of polyhedrons, including a control polyhedron having a control footprint, wherein each polyhedron in the plurality has a polygon footprint and one or more neighbor polyhedrons, wherein at least one point of the control polyhedron is characterized as having the lowest start elevation in the plurality of polyhedrons, and wherein the first dataset is characterized as having a predetermined error;

determining, by the data-processing system, that a first polyhedron, in a first non-empty set of polyhedrons whose polygon footprints overlap the control footprint, also overlaps in height with the control polyhedron;

determining, by the data-processing system, that a second polyhedron also overlaps in height with the control polyhedron, resulting in a second non-empty set of polyhedrons that overlap in height with the control polyhedron, including the first polyhedron and the second polyhedron;

dividing, by the data-processing system, each polyhedron in the second set of polyhedrons into a base part and a top part, such that each base part has the same end elevation as the control polyhedron, and wherein each top part has a start elevation that is the same as the end elevation of the control polyhedron, the end elevation of a given polyhedron being higher than the start elevation of the given polyhedron, wherein the dividing results in a third set of polyhedrons;

joining, by the data-processing system, at least a portion of the control polyhedron with all of the base parts of the polyhedrons in the third set of polyhedrons, resulting in a joined polyhedron, wherein the joined polyhedron defines a first building in the geographic region, and wherein at least some faces of the joined polyhedron define outer walls of the first building;

removing a top part from at least one of the polyhedrons in the third set of polyhedrons, based on the height of the top part failing to exceed a value that is based on the predetermined error;

transmitting, by the data-processing system to an application engine, a second dataset that comprises i) the joined polyhedron and ii) a polyhedron defined by a top part of at least one of the polyhedrons in the third set of polyhedrons, but excludes iii) the removed top part;

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 joined 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.

17. The method of claim 16, wherein the calculating of visibility is part of at least one of modeling, visualization, and navigation.

18. The method of claim 16 wherein the predetermined error is characterized as a particular resolution at which the first dataset is made available.

19. The method of claim 16 further comprising determining, by the data-processing system, that a neighbor polyhedron of the second polyhedron, with a polygon footprint that overlaps the footprint of the second polyhedron, also overlaps in height with the control polyhedron, wherein the second non-empty set of polyhedrons further includes the neighbor polyhedron of the second polyhedron.

20. The method of claim 19 wherein the first polyhedron and the neighbor polyhedron of the polyhedron are non-overlapping in their polygon footprints.