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

__init__(*args, **kwargs)

computeCellCenter(*args, **kwargs)

Overloaded function.

1. 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

2. 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.

1. 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

2. 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.

1. 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

2. 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

__init__(self: _cloudComPy.PointDescriptor) → None

Default constructor

property point

property pointIndex

property squareDistd

class cloudComPy.CellDescriptor

Structure used during nearest neighbour search.

Variables:

• center (tuple) – Cell center coordinates

• index (int) – First point index in associated NeighboursSet

__init__(self: _cloudComPy.CellDescriptor) → None

Default constructor

property center

property index

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

__init__(self: _cloudComPy.IndexAndCode) → None

Default constructor

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

property theCode

property theIndex

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

__init__(self: _cloudComPy.CylindricalNeighbourhood) → None

Default constructor

property center

property dir

property level

property maxHalfLength

property onlyPositiveDir

property radius

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)

__init__(self: _cloudComPy.ProgressiveCylindricalNeighbourhood) → None

Default constructor

property currentHalfLength

property potentialCandidates

property prevMaxCornerPos

property prevMinCornerPos

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

__init__(self: _cloudComPy.BoxNeighbourhood) → None

Default constructor

property axes

property center

property dimensions

property level

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()).

__init__(self: _cloudComPy.NearestNeighboursSearchStruct) → None

Default constructor

property alreadyVisitedNeighbourhoodSize

property cellCenter

property cellPos

property level

property maxSearchSquareDistd

property minNumberOfNeighbors

property minimalCellsSetToVisit

property pointsInNeighbourhood

property queryPoint

property theNearestPointIndex