System and Method for Extracting Features from Data Having Spatial Coordinates

A method for a computing device to extract a building model from a set of data points with three-dimensional spatial coordinates, the method comprising:

• the computing device obtaining a set of ground surface points from the set of data points, the ground surface points classified as base points;
• the computing device applying a triangulation algorithm to the data points that are not the base points to construct a triangulated surface;
• the computing device removing edges from the triangulated surface that have at least one point classified as a base point;
• the computing device re-applying the triangulation algorithm to the triangulated surface to generate one or more subsets of triangulated and interconnected paints;
• the computing device identifying a large subset defined by a plan-view area of the large subset being above a predetermined threshold;
• and
• the computing device classifying the large subset as the building model.

A method for a computing device to remove data points representing vegetation from a set of data points, the set of data points with three-dimensional spatial coordinates of at least the vegetation and a ground surface, the method comprising:

• the computing device obtaining a set of ground surface points and non-ground surface points from the set of data points;
• the computing device applying a triangulation algorithm to the non-ground surface points to construct a triangulated surface;
• the computing device removing edges from the triangulated surface that are longer than a predetermined length and are at an angle greater then 45° above the horizontal plane;
• and
• the computing device removing small subsets having a plan-view area smaller than a predetermined threshold.

A method for a computing device to construct a polygonal building model from a set of data points with three-dimensional spatial coordinates of a building, the method comprising:

• the computing device computing a histogram of the number of data points along a vertical axis;
• the computing device classifying a height of each local maximum of the histogram as a height of a separate building layer;
• the computing device applying a triangulation algorithm to the data points lying within each of the separate building layers to construct a triangulated layer correspond to each separate building layer;
• the computing device removing long edges, that are longer than a threshold, from each of the triangulated layers;
• the computing device forming a boundary line for each triangulated layer, the boundary line formed from the outer edges of each triangulated layer;
• and
• for each triangulation layer, the computing device projecting the boundary line downwards to a triangulated layer below to generate walls of the polygonal building model.

A method for a computing device to extract a wire from a set of data points with three-dimensional spatial coordinates, the method comprising:

• the computing device obtaining ground surface points, representative of the ground surface, and non-ground surface points from the set of data points;
• the computing device applying a triangulation algorithm to the non-ground surface points to construct a triangulated surface;
• the computing device removing points from the triangulated surface that are lower than a predetermined height from the ground surface;
• the computing device removing points from the triangulated surface that are sparsely located;
• the computing device removing edges from the triangulated surface that have a length greater than a predetermined length Dmin;
• the computing device identifying a largest subset of interconnected data points in the triangulated surface;
• the computing device computing a line through the largest subset;
• and
• wherein the line is the wire.

A method for a computing device to extract a wire from a set of data points with three-dimensional spatial coordinates, the method comprising:

• the computing device constructing an XYZ frame of reference comprising an origin O at an end of a known wire segment represented by line LR, a Y axis collinear with the line LR, and a plane XOY that is parallel to a ground surface;
• computing a first polygon and a second polygon both coplanar with a plane XOZ and both having the origin O at their centre, the second polygon larger than the first polygon;
• computing a line S of finite length extending from the origin O and collinear with the line LR;
• computing a number of data points n1 that project on to the line S and project on to the plane XOZ within a perimeter of the first polygon;
• computing a number of data points n2 that project on to the line S and project on to plane XOZ within a perimeter of the second polygon;
• determining if the line S represents a segment of the wire by using the number of points n1 and n2;
• and
• if so, forming the wire by combing the lines S and LR

A method for a computing device to classify a relief of a ground surface from a set of data points with three-dimensional spatial coordinates, the method comprising:

• the computing device separating the set of data points into horizontal tiles;
• the computing device forming a triangulated surface comprised of the lowest point from each of the horizontal tiles, the triangulated surface identified as the ground surface;
• and
• the computing device classifying the relief of the ground surface based on computed inclination angles of each triangle within the ground surface relative to a horizontal plane.

A method for a computing device to classify a ground surface by vegetation from a set of data points with three-dimensional spatial coordinates, the method comprising:

• the computing device separating the set of data points into horizontal tiles;
• the computing device forming a triangulated surface comprised of the lowest point from each of the horizontal tiles, the triangulated surface identified as the ground surface;
• computing for each tile a standard deviation of the data points' heights relative to the ground surface;
• and
• the computing device classifying the ground surface by vegetation based on a percentage of tiles having the standard deviation above a predetermined height Hdev.

A method for extracting features from a data set representing spatial coordinates, the method comprising:

• extracting an approximate ground surface from the data;
• characterising the relief and terrain of the approximate ground surface;
• extracting an accurate ground surface based on the characterised relief and terrain;
• extracting building points from data located above the accurate ground surface;
• and,
• reconstructing a building model from the building points.