Building Boundary

NOTE: STILL IN VERY ACTIVE DEVELOPMENT AND IS UNSTABLE. NO SUPPORT CAN BE GIVEN AT THIS TIME.

Attempts to trace the boundary of a set of points belonging to an aerial LiDAR scan of a building (part). It tries to optimize the boundary by exploiting the (most often) rectilinearity of buildings. It will look for the primary orientations of the building and try to regularize all boundary lines to these orientations (or the perpendicular).

The basic steps of the algorithm are as follows:

Determine the boundary points
Check if the shape matches a basic shape (rectangle or triangle), if so return this basic shape
Segment the boundary points in to wall segments
Fit a line to each segment
Determine the primary orientations
Regularize the lines to the primary orientations
Merge subsequent parallel lines
Compute the intersections of the lines

Prerequisites

python >= 3.6
pip >= 19.1
concave_hull >= 1.0
pymintriangle >= 0.1
CGAL (with SWIG python bindings) >= 4.12

Install

pip install .

Usage

import numpy as np
import building_boundary

points = np.array([
    [122336.637, 489292.815],
    [122336.233, 489291.98 ],
    [122336.258, 489292.865],
    [122335.234, 489293.104],
    [122336.448, 489293.46 ],
    [122334.992, 489293.68 ],
    [122335.987, 489292.778],
    [122335.383, 489292.746],
    [122336.509, 489293.173],
    [122335.794, 489293.425],
    [122335.562, 489293.121],
    [122335.469, 489293.406],
    [122335.944, 489293.734],
    [122335.3  , 489293.697],
    [122336.574, 489292.414],
    [122336.2  , 489292.31 ],
    [122335.907, 489292.296],
    [122335.599, 489292.281],
    [122335.686, 489292.762],
    [122336.842, 489293.192],
    [122335.886, 489293.139],
    [122335.094, 489292.733],
    [122336.146, 489293.444],
    [122336.193, 489293.157],
    [122335.154, 489293.389],
    [122335.643, 489293.717]
])
vertices = building_boundary.trace_boundary(
    points,
    0.3,
    max_error=0.4,
    alpha=0.5,
    k=5,
    num_points=10,
    merge_distance=0.6
)

Documentation

trace_boundary

Trace the boundary of a set of 2D points.

Parameters

points : (Mx2) array: The coordinates of the points.
ransac_threshold : float: Maximum distance for a data point to be classified as an inlier during the RANSAC line fitting.
max_error : float: The maximum error (distance) a point can have to a computed line.
alpha : float: Set to determine the boundary points using an alpha shape using this chosen alpha. If both alpha and k are set both methods will be used and the resulting shapes merged to find the boundary points.
k : int: Set to determine the boundary points using a knn based concave hull algorithm using this amount of nearest neighbors. If both alpha and k are set both methods will be used and the resulting shapes merged to find the boundary points.
num_points : int, optional: The number of points a segment needs to be supported by to be considered a primary orientation. Will be ignored if primary orientations are set manually.
angle_epsilon : float, optional: The angle (in radians) difference within two angles are considered the same. Used to merge segments.
merge_distance : float, optional: If the distance between two parallel sequential segments (based on the angle epsilon) is lower than this value the segments get merged.
primary_orientations : list of floats, optional: The desired primary orientations (in radians) of the boundary. If set manually here these orientations will not be computed.
perp_dist_weight : float, optional: Used during the computation of the intersections between the segments. If the distance between the intersection of two segments and the segments is more than perp_dist_weight times the distance between the intersection of the perpendicular line at the end of the line segment and the segments, the perpendicular intersection will be used instead.
inflate : bool, optional: If set to true the fit lines will be moved to the furthest outside point.

Returns

vertices : (Mx2) array: The vertices of the computed boundary line

jtwhu/building-boundary