4. Octrees, descriptors and neighbourhood

4.1. Octrees

class cloudComPy.DgmOctree

Bases: pybind11_object

GenerateTruncatedCellCode(self: _cloudComPy.DgmOctree, arg0: Tuple3Tpl<T>, arg1: int) → int

Generates the truncated cell code of a cell given its position at a given level of subdivision.

For a given level of subdivision (lets call it N), the cell position can be expressed as 3 integer coordinates between 0 and 2^N-1 (the number of cells along each dimension). This method computes the corresponding cell code, truncated at the level N (meaning that it is only valid for the Nth level, not for other levels).

Parameters

cellPos (tuple) – the cell position (3 int indices)
level (int) – the level of subdivision

Returns

the truncated cell code

Return type

int

computeCellCenter(*args, **kwargs)

Overloaded function.

computeCellCenter(self: _cloudComPy.DgmOctree, code: int, level: int, isCodeTruncated: bool = False) -> Vector3Tpl<T>

Returns the cell center for a given level of subdivision of a cell designated by its code.

Parameters

code (int) – the cell code
level (int) – the level of subdivision
isCodeTruncated (bool,optional) – (default False) indicates if the given code is truncated or not

Returns

computed center coordinates

Return type

tuple

computeCellCenter(self: _cloudComPy.DgmOctree, arg0: Tuple3Tpl<T>, arg1: int) -> Vector3Tpl<T>

Returns the cell center for a given level of subdivision of a cell designated by its position.

Parameters

cellPos (tuple) – the cell position (3 int indices)
level (int) – the level of subdivision

Returns

computed center coordinates

Return type

tuple

findBestLevelForAGivenCellNumber(self: _cloudComPy.DgmOctree, arg0: int) → int

Determines the best subdivision level of the octree to match a given number of cells.

Parameters: indicativeNumberOfCells (int) – ‘desired’ number of cells
Returns: the ‘best’ level
Return type: int

findBestLevelForAGivenNeighbourhoodSizeExtraction(self: _cloudComPy.DgmOctree, arg0: float) → int

Determines the best level of subdivision of the octree at which to apply the nearest neighbours search algorithm (inside a sphere) depending on the sphere radius.

Parameters: radius (float) – the sphere radius
Returns: the ‘best’ level
Return type: int

findBestLevelForAGivenPopulationPerCell(self: _cloudComPy.DgmOctree, arg0: int) → int

Determines the best subdivision level of the octree that gives the average population per cell closest to the input value.

Parameters: indicativeNumberOfPointsPerCell (int) – ‘desired’ average number of points per cell
Returns: the ‘best’ level
Return type: int

findNearestNeighborsStartingFromCell(self: _cloudComPy.DgmOctree, arg0: _cloudComPy.NearestNeighboursSearchStruct, arg1: bool) → int

Advanced form of the nearest neighbours search algorithm (multiple neighbours).

This version is optimized for a multiple nearest neighbours search that is applied around several query points included in the same octree cell. See NearestNeighboursSearchStruct for more details.

Parameters

nNSS (NearestNeighboursSearchStruct) – search parameters
getOnlyPointsWithValidScalar (bool) – whether to ignore points having an invalid associated scalar value

Returns

the number of neighbours found

Return type

int

findNeighborsInASphereStartingFromCell(self: _cloudComPy.DgmOctree, arg0: _cloudComPy.NearestNeighboursSearchStruct, arg1: float, arg2: bool) → int

Advanced form of the nearest neighbours search algorithm (in a sphere).

This version is optimized for a spatially bounded search instead of a search bounded by a number of neighbours. WARNING the number of points in the output buffer (nNSS.pointsInNeighbourhood) may be greater than the actual count of closest points inside the sphere! (which is returned by the method). Only the ‘k’ first points are actually inside the sphere (the others are not removed for the sake of performance).

Parameters

nNSS (NearestNeighboursSearchStruct) – a pack of parameters
radius (float) – the sphere radius
sortValues (bool) – specifies if the neighbours needs to be sorted by their distance to the query point or not

Returns

the number of neighbours found

Return type

int

findPointNeighbourhood(self: _cloudComPy.DgmOctree, _queryPoint: Vector3Tpl<T>, Yk: _cloudComPy.ReferenceCloud, maxNumberOfNeighbors: int, level: int, maxSearchDist: float = 0) → tuple

Finds the nearest neighbours around a query point.

This is the simplest form of the nearest neighbour search algorithm. It should only be used for unique/few requests as it is not optimized for repetitive search around points lying in the same octree cell (see findNearestNeighborsStartingFromCell() for example). Moreover, distances between each neighbour and the query aren’t stored in this version of the algorithm.

Parameters

_queryPoint (tuple) – the query point (coordinates)
Yk (ReferenceCloud) – RefefenceCloud for the nearest neighbours
maxNumberOfNeighbors (int) – the maximal number of points to find
level (int) – the subdivision level of the octree at which to perform the search
maxSearchDist (float,optional) – (default 0) the maximum search distance (ignored if <= 0)

Returns

tuple

number of neighbours found,
final neighborhood (half)size,
square distance between the farthest “nearest neighbour” and the query point

Return type

tuple

findTheNearestNeighborStartingFromCell(self: _cloudComPy.DgmOctree, arg0: _cloudComPy.NearestNeighboursSearchStruct) → float

Advanced form of the nearest neighbour search algorithm (unique neighbour).

This version is optimized for a unique nearest-neighbour search. See NearestNeighboursSearchStruct for more details.

Parameters: nNSS (NearestNeighboursSearchStruct) – search parameters
Returns: the square distance between the query point and its nearest neighbour (or -1 if none was found - i.e. maxSearchDist was reached)
Return type: float

getBoundingBox(self: _cloudComPy.DgmOctree) → List[Vector3Tpl<T>]

Returns the octree bounding box.

Method to request the octree bounding box limits.

Returns: ((Xmin,Ymin,Zmin), (Xmax,Ymax,Zmax))
Return type: tuple

getCellCode(self: _cloudComPy.DgmOctree, arg0: int) → int

Returns the ith cell code.

WARNING: i is NOT the point index in cloud! Very specific use! (the table giving index in cloud and CellCode is sorted by CellCodes)

Returns: CellCode
Return type: int

getCellCodes(self: _cloudComPy.DgmOctree, level: int, truncatedCodes: bool = False) → List[int]

Returns the list of codes corresponding to the octree cells for a given level of subdivision.

Only the non empty cells are represented in the octree structure.

Parameters

level (int) – the level of subdivision
truncatedCodes (bool,optional) – (default False) indicates if the resulting codes should be truncated or not

Returns

the list of codes

Return type

list

getCellCodesAndIndexes(self: _cloudComPy.DgmOctree, level: int, truncatedCodes: bool = False) → List[_cloudComPy.IndexAndCode]

Returns the list of indexes and codes corresponding to the octree cells for a given level of subdivision.

Only the non empty cells are represented in the octree structure. Cell indexes are expressed relatively to the DgmOctree structure. They correspond to the indexes of the first points of each cell.

Parameters

level (int) – the level of subdivision
truncatedCodes (bool) – indicates if the resulting codes should be truncated or not

Returns

the list of IndexAndCode

Return type

list

getCellDistanceFromBorders(*args, **kwargs)

Overloaded function.

getCellDistanceFromBorders(self: _cloudComPy.DgmOctree, arg0: Tuple3Tpl<T>, arg1: int) -> List[int]

Returns distance from a cell to the filled octree borders in all directions (3 int).

WARNING: distance values may be negative! (if cell is outside)

Parameters

cellPos (tuple) – cell position
level (int) – level at which octree grid is considered

Returns

cellDists output (3 int)

Return type

tuple

getCellDistanceFromBorders(self: _cloudComPy.DgmOctree, arg0: Tuple3Tpl<T>, arg1: int, arg2: int) -> List[int]

Returns distance from cell center to cell neighbourhood INSIDE filled octree (3 int).

WARNING: if cell neighbourhood is totally outside filled octree, the method returns invalid cellDists (empty list).

Parameters

cellPos (tuple) – center cell position
level (int) – level at which octree grid is considered
neighbourhoodLength (float) – cell neighbourhood “radius”

Returns

cellDists output (3 int)

Return type

tuple

getCellIndexes(self: _cloudComPy.DgmOctree, arg0: int) → List[int]

Returns the list of indexes corresponding to the octree cells for a given level of subdivision.

Only the non empty cells are represented in the octree structure. Cell indexes are expressed relatively to the DgmOctree structure. They correspond to the indexes of the first points of each cell.

Parameters: level (int) – the level of subdivision
Returns: the list of indexes
Return type: list

getCellNumber(self: _cloudComPy.DgmOctree, arg0: int) → int

Returns the number of cells for a given level of subdivision.

Parameters: level (int) – the level of subdivision
Returns: the number of cells at this level
Return type: int

getCellPos(self: _cloudComPy.DgmOctree, arg0: int, arg1: int, arg2: bool) → Tuple3Tpl<T>

Returns the cell position for a given level of subdivision of a cell designated by its code.

Parameters

code (int) – the cell code
level (int) – the level of subdivision
isCodeTruncated (bool) – indicates if the given code is truncated or not

Returns

the computed cell position

Return type

tuple

getCellSize(self: _cloudComPy.DgmOctree, arg0: int) → float

Returns the octree cells length for a given level of subdivision.

As the octree is cubical, cells are cubical.

Parameters: level (int) – the level of subdivision (up to MAX_OCTREE_LEVEL+1 for convenience)
Returns: the cell size
Return type: float

getMaxFillIndexes(self: _cloudComPy.DgmOctree, arg0: int) → List[int]

Returns the highest cell positions in the octree along all dimensions and for a given level of subdivision.

For example, at a level n, the octree length is 2^n cells along each dimension. The highest cell position along each dimension will be expressed between 0 and 2^n-1.

Parameters: level (int) – the level of subdivision
Returns: the highest cell position along X,Y and Z for a given level of subdivision
Return type: tuple

getMinFillIndexes(self: _cloudComPy.DgmOctree, arg0: int) → List[int]

Returns the lowest cell positions in the octree along all dimensions and for a given level of subdivision.

For example, at a level n, the octree length is 2^n cells along each dimension. The lowest cell position along each dimension will be expressed between 0 and 2^n-1.

Parameters: level (int) – the level of subdivision
Returns: the lowest cell position along X,Y and Z for a given level of subdivision
Return type: tuple

getNumberOfProjectedPoints(self: _cloudComPy.DgmOctree) → int

Returns the number of points projected into the octree.

Returns: the number of projected points
Return type: int

getOctreeMaxs(self: _cloudComPy.DgmOctree) → Vector3Tpl<T>

Returns the higher boundaries of the octree.

Returns: the higher coordinates along X,Y and Z
Return type: tuple

getOctreeMins(self: _cloudComPy.DgmOctree) → Vector3Tpl<T>

Returns the lower boundaries of the octree.

Returns: the lower coordinates along X,Y and Z
Return type: tuple

getPointsInBoxNeighbourhood(self: _cloudComPy.DgmOctree, arg0: _cloudComPy.BoxNeighbourhood) → List[_cloudComPy.PointDescriptor]

Returns the points falling inside a box.

Use findBestLevelForAGivenNeighbourhoodSizeExtraction() to get the right value for ‘level’ (only once as it only depends on the radius or max dimension value).

WARNING the ‘squareDistd’ field of each neighbour returned is not used/set

Parameters: neighbourhood (BoxNeighbourhood) – the box in which to search points
Returns: list of PointDescriptor
Return type: list

getPointsInCell(self: _cloudComPy.DgmOctree, cellCode: int, level: int, subset: _cloudComPy.ReferenceCloud, isCodeTruncated: bool = False, clearOutputCloud: bool = True) → bool

Returns the points lying in a specific cell.

Parameters

cellCode (int) – the unique cell code
level (int) – the level of subdivision
subset (ReferenceCloud,[in,out]) – set of points lying in the cell (references, no duplication)
isCodeTruncated (bool,optional) – (default False) specifies if the code is given in a truncated form or not
clearOutputCloud (bool,optional) – (default True) whether to clear or not the output cloud (subest) if no points lie in the specified cell

Returns

success

Return type

bool

getPointsInCellByCellIndex(self: _cloudComPy.DgmOctree, cloud: _cloudComPy.ReferenceCloud, cellIndex: int, level: int, clearOutputCloud: bool = True) → bool

Returns the points lying in a specific cell.

Each cell at a given level of subdivision can be recognized by the index in the DgmOctree structure of the first point that lies inside it. By construction, we are assured that every point lying in the same cell for a given level of subdivision are next to each others in the octree structure (which is the vector “m_thePointsAndTheirCellCodes” in practical). This is the quickest way to access the points inside a given cell (but its kind of hard to know directly what is the index of a given cell) See getCellIndexes(), getCellCodesAndIndexes().

Parameters

cloud (ReferenceCloud,[in,out]) – ReferenceCloud to store the points lying inside the cell
cellIndex (int) – the cell index
level (int) – the level of subdivision
clearOutputCloud (bool,optional) – (default True) whether to clear the input cloud prior to inserting the points or not

Returns

success

Return type

bool

getPointsInCellsWithSortedCellCodes(self: _cloudComPy.DgmOctree, cellCodes: List[int], level: int, subset: _cloudComPy.ReferenceCloud, areCodesTruncated: bool = False) → _cloudComPy.ReferenceCloud

Returns the points lying in multiple cells.

Cells are recognized here by their unique “code”. They should be sorted along by codes, with an ascendant order. See getPointsInCellByCellIndex() for more information.

param list cellCodes: the cells codes param int level: the level of subdivision param ReferenceCloud,[in,out] subset: set of points lying in the cell (references, no duplication) param bool,optional areCodesTruncated: (default False) specifies if the codes are given in a truncated form or not return the set of points lying in the cell (references, no duplication)

Returns: the set of points lying in the cell
Return type: ReferenceCloud

getPointsInCylindricalNeighbourhood(self: _cloudComPy.DgmOctree, arg0: _cloudComPy.CylindricalNeighbourhood) → List[_cloudComPy.PointDescriptor]

Returns the points falling inside a cylinder.

Use findBestLevelForAGivenNeighbourhoodSizeExtraction() to get the right value for ‘level’ (only once as it only depends on the radius value).

WARNING the ‘squareDistd’ field of each neighbour in the NeighboursSet structure is in fact the signed distance (not squared) of the point relatively to the cylinder’s center and projected along its axis.

Parameters: neighbourhood (CylindricalNeighbourhood) – parameters structure
Returns: the extracted points: list of PointDescriptor
Return type: list

getPointsInCylindricalNeighbourhoodProgressive(self: _cloudComPy.DgmOctree, arg0: _cloudComPy.ProgressiveCylindricalNeighbourhood) → List[_cloudComPy.PointDescriptor]

Same as getPointsInCylindricalNeighbourhood with progressive approach.

Can be called multiple times (the ‘currentHalfLength’ parameter will increase each time until ‘maxHalfLength’ is reached).

WARNING the ‘squareDistd’ field of each neighbour in the NeighboursSet structure is in fact the signed distance (not squared) of the point relatively to the cylinder’s center and projected along its axis.

Parameters: neighbourhood (CylindricalNeighbourhood) – parameters structure
Returns: the extracted points (list of PointDescriptor)
Return type: list

getPointsInSphericalNeighbourhood(self: _cloudComPy.DgmOctree, arg0: Vector3Tpl<T>, arg1: float, arg2: int) → List[_cloudComPy.PointDescriptor]

Returns the points falling inside a sphere.

Use findBestLevelForAGivenNeighbourhoodSizeExtraction() to get the right value for ‘level’ (only once as it only depends on the radius value).

Parameters

sphereCenter (tuple) – center coordinates
radius (float) – radius
level (int) – subdivision level at which to apply the extraction process

Returns

neighbours points falling inside the sphere (list of PointDescriptor)

Return type

list

getTheCellPosWhichIncludesThePoint(*args, **kwargs)

Overloaded function.

getTheCellPosWhichIncludesThePoint(self: _cloudComPy.DgmOctree, arg0: Vector3Tpl<T>) -> Tuple3Tpl<T>

Returns the position FOR THE DEEPEST LEVEL OF SUBDIVISION of the cell that includes a given point.

The cell coordinates can be negative or greater than 2^MAX_OCTREE_LEVEL-1 as the point can lie outside the octree bounding-box.

Parameters: thePoint (tuple) – the query point coordinates
Returns: cellPos the computed position (3 int indices)
Return type: tuple

getTheCellPosWhichIncludesThePoint(self: _cloudComPy.DgmOctree, arg0: Vector3Tpl<T>, arg1: int) -> Tuple3Tpl<T>

Returns the position for a given level of subdivision of the cell that includes a given point.

The cell coordinates can be negative or greater than 2^N-1 (where N is the level of subdivision) as the point can lie outside the octree bounding-box.

Parameters

thePoint (tuple) – the query point coordinates
level (int) – the level of subdivision

Returns

cellPos the computed position (3 int indices)

Return type

tuple

getTheCellPosWhichIncludesThePointInbBounds(self: _cloudComPy.DgmOctree, arg0: Vector3Tpl<T>, arg1: int) → tuple

Returns the position for a given level of subdivision of the cell that includes a given point.

The cell coordinates can be negative or greater than 2^N-1 (where N is the level of subdivision) as the point can lie outside the octree bounding-box. In this version, method indicates if the query point is inside (“inbounds”) or outside the octree bounding-box.

Parameters

thePoint (tuple) – the query point coordinates
level (int) – the level of subdivision

Returns

tuple (cellPos the computed position, inBounds indicates if the query point is inside or outside the octree bounding-box)

Return type

tuple

4.2. Descriptors structures

class cloudComPy.PointDescriptor

Structure used during nearest neighbour search.

Association between a point, its index and its square distance to the query point. The structure is made persistent, by copying the coordinates.

Variables

point (tuple) – point coordinates
index (int) – point index
squareDistd (float) – point associated distance value

class cloudComPy.CellDescriptor

Structure used during nearest neighbour search.

Variables

center (tuple) – Cell center coordinates
index (int) – First point index in associated NeighboursSet

class cloudComPy.IndexAndCode

Association between an index and the code of an octree cell Index could be the index of a point, in which case the code would correspond to the octree cell where the point lies.

Variables

index (int) – the index
code (int) – theCode

static codeComp(arg0: _cloudComPy.IndexAndCode, arg1: _cloudComPy.IndexAndCode) → bool

Compares two IndexAndCode instances based on their code.

Parameters

a (IndexAndCode) – first IndexAndCode structure
b (IndexAndCode) – second IndexAndCode structure

Returns

whether the code of ‘a’ is smaller than the code of ‘b’

Return type

bool

static indexComp(arg0: _cloudComPy.IndexAndCode, arg1: _cloudComPy.IndexAndCode) → bool

Compares two IndexAndCode instances based on their index.

Parameters

a (IndexAndCode) – first structure
b (IndexAndCode) – second structure

Returns

whether the index of ‘a’ is smaller than the index of ‘b’

Return type

bool

4.3. Neighbourhood structures

class cloudComPy.CylindricalNeighbourhood

Parameters structure for getPointsInCylindricalNeighbourhood.

Use findBestLevelForAGivenNeighbourhoodSizeExtraction to get the right value for ‘level’ (only once as it only depends on the radius value).

Variables

center (tuple) – Cylinder center, default (0,0,0)
dir (tuple) – Cylinder axis (direction), default (0,0,1)
radius (float) – Cylinder radius, default 0
maxHalfLength (float) – Cylinder (half) length, default 0
level (int) – subdivision level at which to apply the extraction process, default 0
onlyPositiveDir (bool) – Whether to look in both directions or only along the positive direction (i.e. half cylinder), default False

class cloudComPy.ProgressiveCylindricalNeighbourhood

Bases: CylindricalNeighbourhood

Input/output parameters structure for getPointsInCylindricalNeighbourhoodProgressive.

Derived from CylindricalNeighbourhood. See CylindricalNeighbourhood for generic data members.

Specific data members

Variables

currentHalfLength (float) – Current search depth
potentialCandidates (list) – list of PointDescriptor to store potential candidates for the next pass. Candidates are points close enough to the cylinder’s axis but too far from its actual center.
prevMinCornerPos (tuple) – Previous search box (min corner)
prevMaxCornerPos (tuple) – Previous search box (max corner)

class cloudComPy.BoxNeighbourhood

Input/output parameters structure for getPointsInBoxNeighbourhood.

Use findBestLevelForAGivenNeighbourhoodSizeExtraction to get the right value for ‘level’ (only once as it only depends on the radius value ;).

Variables

center (tuple) – Box center (3 coordinates), default initialization (0, 0, 0)
axes (list) – 3 axes, optional, default initialization None
dimensions (tuple) – dimensions of the box, default initialization (0, 0, 0)
level (int) – subdivision level at which to apply the extraction process

class cloudComPy.NearestNeighboursSearchStruct

Container of in/out parameters for nearest neighbour(s) search.

This structure is generic and can be used in multiple cases. It is particularly useful when searching nearest neighbours around points that lie in the same octree cell. In this case, several informations about this cell should be given to the search algorithm through this structure, but only once,before the first search. Then the search algorithm can be called multiple times, and only few informations need to be updated (the query point, etc.).

Information to set before search

Variables

queryPoint (tuple) – Query point coordinates. Should be updated each time.
level (int) – Level of subdivision of the octree at which to start the search, Should be set once and for all.
minNumberOfNeighbors (int) – Minimal number of neighbours to find used only during multiple neighbours search (see findNearestNeighborsStartingFromCell). This is only indicative and not guaranteed.
cellPos (tuple) – Cell position in the octree of the cell including the query point. The position is expressed for the level of subdivision at which the search will be processed. Use see getCellPos() to determine this position. This information should only be updated if the cell changes.
cellCenter (tuple) – Coordinates of the center of the cell including the query point. Use DgmOctree::computeCellCenter to determine these coordinates. This information should only be updated if the cell changes.
maxSearchSquareDistd (float) – Maximum neihgbours distance. The NN search process will stop if it reaches this radius even if it hasn’t find any neighbour (acceleration). To disable this behavior, set the maxSearchSquareDistd to something <= 0).

Information to set to 0 before search

Variables

minimalCellsSetToVisit (list) – List of indexes of the cells that have been already visited by the algorithm. This field is updated by the search algorithm. It should only be emptied if the cell that includes the query points change. Only used by the “unique nearest point” search algorithm.
pointsInNeighbourhood (list) – List of PointDescriptor. All the points that belong to the cubical neighbourhood of the current cell. This structure is only used by the “multiple nearest neighbours” search algorithms. The nearest points (relatively to the query point) are stored at the beginning of the vector. They are associated to their square distance to the query point.
alreadyVisitedNeighbourhoodSize (int) – Size of the cell neighbourhood that has been already visited by the algorithm. This field is updated by the search algorithm. It should only be reset to 0 when the cell that includes the query point changes. A value of 0 means that no cell has been visited yet, 1 means that only the cell that includes the query point has been visited, 2 means that this cell and its 27 neighbourhing cells have been visited, etc.

Result

Variables: theNearestPointIndex (int) – The nearest point. This field is only used by the “unique nearest neighbour” search algorithm (see findTheNearestNeighborStartingFromCell()).