# UNDF: UNDF-2026-000000403
## Classification

| Field       | Value |
|-------------|-------|
| CWE         | CWE-407 Inefficient Algorithmic Complexity |
| Severity    | HIGH |
| Component   | `segmentation/include/pcl/segmentation/impl/region_growing.hpp:594` |
| Also        | `segmentation/include/pcl/segmentation/impl/region_growing_rgb.hpp:726` |
| Function    | `RegionGrowing::getSegmentFromPoint()` / `RegionGrowingRGB::getSegmentFromPoint()` |
| Hot path    | Public API — called once per query point; any loop over N query points = O(N²) |
| Status      | PATCHED (unit test PASS) |

## Defect

`getSegmentFromPoint()` locates the cluster containing a given point index by
scanning all clusters with `std::find`:

```cpp
// region_growing.hpp:594-605
for (const auto& i_segment : clusters_)
{
  const auto it = std::find (i_segment.indices.cbegin (), i_segment.indices.cend (), index);
  if (it != i_segment.indices.cend())
  {
    cluster.indices = i_segment.indices;  // copy
    break;
  }
}
```

This is O(C × S) per call, where:
- C = number of clusters (e.g. 1,000 for a 100K-point LiDAR scan)
- S = average points per cluster (e.g. 100)

The lookup cost is O(C × S) = O(N) when C × S ≈ N.

**The fix is already in the data structure.** `point_labels_` is a dense array
populated by `applySmoothRegionGrowingAlgorithm()` and used verbatim in
`assembleRegions()`:

```cpp
// assembleRegions():538
const auto segment_index = point_labels_[i_point];
clusters_[segment_index].indices[point_index] = i_point;
```

So `clusters_[point_labels_[index]]` is an O(1) direct array lookup that
gives exactly the same result as the O(C × S) scan.

### RGB variant

`RegionGrowingRGB::getSegmentFromPoint()` inherits the same pattern.  After
`applyRegionMergingAlgorithm()`, the two-level mapping is:
`point_labels_[point]` → initial segment index, then
`segment_labels_[seg]` → merged homogeneous region index.
The RGB `assembleRegions()` uses this at lines 566–567:

```cpp
int index = point_labels_[point_index];
index = segment_labels_[index];
clusters_[index].indices[counter[index]] = point_index;
```

After the compaction sweep that removes empty entries, `region_idx` remains a
valid index for non-empty clusters (empty slots are swapped out, but any point
belonging to a surviving cluster still maps correctly via the two-level index).

## Complexity

| Scenario | Before | After |
|----------|--------|-------|
| Single lookup, C=1K clusters × S=100pts | O(50,000) avg | O(1) |
| Query all N=100K points in a loop | O(N × C × S) = O(5 × 10⁹) | O(N) = O(100K) |
| Speedup ratio (N=100K query loop) | baseline | ~50,000× |

At N=1,000 query points with C=100 clusters × S=100:

| Metric | Before | After |
|--------|--------|-------|
| Op count | ~5,000,000 | ~1,000 |
| Ratio | 5000× | 1× |

## Patch

See `pcl-0001-region-growing-get-segment-linear-scan.patch`.

**Base class fix:** replace the `for...std::find` loop with a direct index
`clusters_[point_labels_[index]]`.

**RGB class fix:** replace the `for...std::find` loop with the two-level index
`clusters_[segment_labels_[point_labels_[index]]]`, guarded by bounds checks.

## Date

2026-03-29
