geodan / building-boundary Goto Github PK

Traces the boundary of a set of points belonging to an aerial LiDAR scan of a building (part).

License: MIT License

Python 100.00%

building-boundary's Introduction

Building Boundary

Traces the boundary of a set of points belonging to an aerial LiDAR scan of a building (part). It attempts to optimize the boundary by exploiting the (most often) rectilinearity of buildings. It will look for the primary orientations of the building and 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 (optional, drastically improves computation time of alpha shapes)

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

building-boundary's People

Contributors

Stargazers

Watchers

Forkers

tomvantilburg storijimmy nnu-gisa liuxinren456852 cuboidfitting duong-nguyen1994 nicolas-bch georger x-malet xzwang12345 esgn

building-boundary's Issues

max_intersect_distance is not always used as constraint

There are still situations where there are long spikes in the boundary output.
One approach might be to use a maximum_angle for a vertex? In that case vertices that have a very narrow angle from the edges can simply be discarded.

Merge alpha shape and concave hull output

Defining optimal parameter values

Hi, can someone please define optimal value for the parameters:
a) alpha
b) k
c) max_error
d) merge_angle

I am trying to use this library and would like to understand these parameters.

result?

How to achieve the visualization of the different steps: segmentation, regularize and the end result footprint?

Hi, thank you for the interesting work. could you kindly comment on how we can achieve the intermediate and end result footprint visualizations with the python script?

Have footprint_geom accept (multi)linestrings

When preprocessing the footprint it can be useful to remove certain lines but that would invalidate or introduce new angles to the polygon. Simply giving a (multi)-linestring would avoid that.

Prim. orientations not really doing anything

There are very slight differences when using Primary Orientations but nothing that looks like what is expected.

index out of range error on some point configurations

Reproduce with:

import numpy as np
from buildingboundary import trace_boundary

points=[[111011.253, 488124.147],
       [111011.319, 488123.927],
       [111011.675, 488124.571],
       [111011.679, 488124.148],
       [111011.852, 488124.393],
       [111011.96 , 488124.708],
       [111012.09 , 488124.304],
       [111012.233, 488124.553],
       [111012.404, 488124.727]]
trace_boundary(points,
        max_error= 0.3,
        merge_angle= 0.2,
        k=5
)

Print statement remained in code

Currently it is outputting a lot of numbers in the postgres logs. Likely because of this printout:
https://github.com/Geodan/building-boundary/blob/master/buildingboundary/components/boundingbox.py#L116

Include max_error_invalid check on bbox generation

Loop in merge algorithm

Code loops forever.
Reproduces with:

points = [[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 = trace_boundary(points,
       max_error=0.26,
       merge_angle=0.4,
       k=5,
       alpha=0.5,
       min_area=2,
       max_merge_distance=0.6,
       max_error_invalid=0.35
)

Merge lines that are parallel but have a small offset

Defining dependencies

Hi, in addition to the existing 4 dependencies, 'python-pcl' should also be added as a dependency. Even after cgal-bindings are installed successfully, the module needs pcl-bindings as well which has to be installed separately.

Self intersecting polygons returned

Consider the following output:

created by:

import numpy as np
from buildingboundary import trace_boundary
xarray=[125213.792,125213.511,125213.213,125212.895,125213.387,125212.801,125212.161,125209.805666667,125211.831,125210.097333333,125209.805666667,125211.341,125211.341,125211.216,125210.967,125210.92,125210.699,125210.542,125210.382,125210.331,125210.328,125210.178,125210.023,125210.021,125210.097333333,125214.458,125214.076,125213.474,125214.515,125214.684,125215.343,125215.057,125214.752,125214.442,125214.123,125215.237,125214.952,125214.654,125214.366,125213.725,125215.259,125214.954,125214.651,125214.366,125214.068,125213.436,125213.153,125214.535,125214.248,125213.35,125213.035,125214.089]
yarray=[480380.365,480380.343,480380.32,480380.296,480379.967,480379.922,480379.873,480378.319666667,480379.393,480378.027333333,480378.027333333,480379.941,480379.656,480379.347,480379.782,480379.324,480379.943,480380.726,480379.704,480379.992,480379.278,480380.774,480379.751,480379.255,480378.319666667,480383.325,480382.919,480382.872,480382.854,480382.387,480381.908,480381.885,480381.861,480381.838,480381.812,480381.506,480381.484,480381.46,480381.438,480381.389,480381.056,480381.032,480381.007,480380.986,480380.963,480380.914,480380.892,480380.679,480380.657,480380.587,480380.563,480380.388]
points = np.array((xarray, yarray)).T
trace_boundary(points,
 max_error=0.26,
 merge_angle=0.4,
 k=5,
 alpha=0.5,
 min_area=2,
 max_merge_distance=0.6,
 max_error_invalid=0.35,
 inflate=True)

Div by zero on some point configurations

Error message:
/usr/local/lib/python3.6/dist-packages/buildingboundary/components/segment.py:112: RuntimeWarning: divide by zero encountered in double_scalars