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