Granted Patent B2

US 10,210,285 · App. 15/232,903 · Granted Feb 19, 2019

Inventors: James Wong (Union City, CA); Avideh Zakhor (Berkeley, CA)

Assignee: INDOOR REALITY INC.

G06F17/5004G06T17/00G06T17/20G06T2210/04

Abstract

Claims (88)

1. A method for generating a floor plan from a building scan of a building using an electronic computing device, the method comprising:

causing the electronic computing device to receive the building scan;

converting the building scan to the floor plan wherein the converting the building scan to the floor plan comprises:

computing a principal axis for the building scan;

straightening a plurality of walls represented by the building scan;

removing intersections of a plurality of rooms represented by the building scan;

shrinking the plurality of rooms by an offset;

collecting a plurality of edges from each of the plurality of rooms;

generating a Voronoi diagram from the plurality of edges; and

extracting and joining edges from the Voronoi diagram; and

refining the floor plan to approximate the building.

2. The method of claim 1 , wherein the causing the electronic computing device to receive the building scan further comprises:

extracting information from an input file to obtain a representation of a plurality of rooms and walls corresponding with the building scan, wherein the information is selected from the group consisting of: a set of vertices, a set of triangles, and a set of rooms.

3. The method of claim 2 , wherein:

the set of vertices are each represented as two doubles, wherein

the set of triangles are each represented as three doubles, and wherein

the set of rooms are each represented as a subset of triangles.

4. The method of claim 1 , wherein the computing a principal axis for the building scan further comprises:

binning each scanned edge based on its angle with a horizontal reference;

selecting a bin having a largest sum of edge length; and

setting the principal axis to equal an average angle of the scanned edges in the selected bin.

5. The method of claim 4 , further comprising:

setting a perpendicular axis equal to the principal axis plus 90 degrees.

6. The method of claim 1 , wherein the straightening a plurality of walls represented by the building scan further comprises:

applying a Ramer-Douglas-Peucker (RDP) algorithm to straighten regions of the plurality of walls by fitting a simplified curve to an original curve of the building scan.

7. The method of claim 1 , wherein the removing intersections of a plurality of rooms represented by the building scan further comprises:

arbitrarily selecting one of two intersecting rooms and subtracting an intersecting region of the two intersecting rooms from the selected one.

8. The method of claim 1 , wherein the collecting a plurality of edges from each of the plurality of rooms further comprises:

computing an external contour that surrounds the plurality of rooms with a contour offset.

9. The method of claim 1 , wherein the extracting and joining edges from the Voronoi diagram further comprises:

removing all tail edges from the Voronoi diagram, wherein the tail edges are all edges not parallel with at least one of the plurality of walls, and the edge is defined as the tail edge if and only if,

a) one of the plurality of vertices of the edge is a vertex to at most one additional edge vertex, or

b) a midpoint of the edge lies within one of the plurality of rooms.

10. The method of claim 1 , wherein the refining the floor plan to approximate the building further comprises:

parallelizing the plurality of edges such that all resulting edges are either parallel to or perpendicular to the principal axis.

11. The method of claim 10 , wherein the parallelizing the plurality of edges such that all resulting edges are either parallel to or perpendicular to the principal axis further comprises:

with respect to the principal axis,

selecting a misaligned edge that is misaligned with the principal axis;

intersecting the misaligned edge with the perpendicular axis;

cutting the misaligned edge into two edges;

forcing the two edges to be parallel with the principal axis; and

reconnecting the two edges, and

with respect to the perpendicular axis,

selecting the misaligned edge that is misaligned with the perpendicular axis;

intersecting the misaligned edge with the principal axis;

cutting the misaligned edge into two edges;

forcing the two edges to be parallel with the perpendicular axis; and

reconnecting the two edges.

12. The method of claim 10 , wherein the refining the floor plan to approximate the building further comprises:

approximating at least one additional user-specified angle for the plurality of edges.

13. A computing device program product for generating a floor plan from a building scan of a building using a computing device, the computing device program product comprising:

a non-transitory computer readable medium;

first programmatic instructions for causing the electronic computing device to receive the building scan;

second programmatic instructions for converting the building scan to a floor plan wherein the second programmatic instructions for converting the building scan to a floor plan comprises:

fifth programmatic instructions for computing a principal axis for the building scan;

sixth programmatic instructions for straightening a plurality of walls represented by the building scan;

seventh programmatic instructions for removing intersections of a plurality of rooms represented by the building scan;

eighth programmatic instructions for shrinking the plurality of rooms by an offset;

ninth programmatic instructions for collecting a plurality of edges from each of the plurality of rooms;

tenth programmatic instructions for generating a Voronoi diagram from the plurality of edges; and

eleventh programmatic instructions for extracting and joining edges from the Voronoi diagram; and

third programmatic instructions for refining the floor plan to approximate the building.

14. The computing device program product of claim 13 , wherein the first programmatic instructions for causing the electronic computing device to receive the building scan further comprises:

fourth programmatic instructions for extracting information from an input file to obtain a representation of a plurality of rooms and walls corresponding with the building scan, wherein the information is selected from the group consisting of: a set of vertices, a set of triangles, and a set of rooms.

15. The computing device program product of claim 13 , wherein the fifth programmatic instructions for computing a principal axis for the building scan further comprises:

twelfth programmatic instructions for binning each scanned edge based on its angle with a horizontal reference;

thirteenth programmatic instructions for selecting a bin having a largest sum of edge length; and

fourteenth programmatic instructions for setting the principal axis to equal an average angle of the scanned edges in the selected bin.

16. The computing device program product of claim 13 , wherein the eleventh programmatic instructions for extracting and joining edges from the Voronoi diagram further comprises:

fifteenth programmatic instructions for removing all tail edges from the Voronoi diagram, wherein the tail edges are all edges not parallel with at least one of the plurality of walls, and the edge is defined as the tail edge if and only if,

a) one of the plurality of vertices of the edge is a vertex to at most one additional edge vertex, or

b) a midpoint of the edge lies within one of the plurality of rooms.

17. The computing device program product of claim 13 , wherein the third programmatic instructions for refining the floor plan to approximate the building further comprises:

sixteenth programmatic instructions for parallelizing the plurality of edges such that all resulting edges are either parallel to or perpendicular to the principal axis; and

seventeenth programmatic instructions for approximating at least one additional user-specified angle for the plurality of edges.

18. A method for generating a floor plan from a building scan of a building using an electronic computing device, the method comprising:

causing the electronic computing device to receive the building scan;

converting the building scan to a floor plan, wherein the converting comprises:

computing a principal axis for the building scan,

straightening a plurality of walls represented by the building scan,

removing intersections of a plurality of rooms represented by the building scan;

shrinking the plurality of rooms by an offset,

collecting a plurality of edges from each of the plurality of rooms,

generating a Voronoi diagram from the plurality of edges, and

extracting and joining edges from the Voronoi diagram; and

refining the floor plan to approximate the building, wherein the refining comprises,

parallelizing the plurality of edges such that all resulting edges are either parallel to or perpendicular to the principal axis, and

approximating at least one additional user-specified angle for the plurality of edges.

Assignments (2)

Continuity (1)

Cited By (11)

US 12,190,581 US 12,260,156 US 12,333,655 US 12,347,033 US 12,444,139 US 12,462,435 US 12,462,483 US 12,495,390 US 12,548,218 US 12,633,119 US 12,666,163