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