<p>Upper bound:</p>

<p>Make three sorted lists of point pointers, one for each dimension O(nlogn)</p>

<p>Pick a point in your reference template to be the "origin" and make 4 vectors to the other points O(1)</p>

<p>For each vector</p>

<p>Scan the list of all points to see if a sister point exists at this vector, if not throw it out as not an origin candidate.  O(n)</p>

<p>If you allow rotations you are probably going to have to throw it in a quadtree and do some range queries; but after the first few are matched to the template it will be oriented allowing you to go back to vector lookups.</p>

CC BY-SA 3.0
2013-06-22T11:45:10.137Z
_If you allow rotations you are probably going to have to throw it in a quadtree and do some range queries_ — Huh?
Jeffε
CC BY-SA 3.0
2013-06-25T17:14:45.920Z
i.e. no scaling, just matching rotatations and translations of the 5 point template. Range queries let you disregard non-candiate points that are too close or too far. You have a better idea for a naive implementation Jeff? :)
Chad Brewbaker
CC BY-SA 3.0
2013-06-21T21:17:46.650Z
2013-06-21T21:17:46.650Z
Chad Brewbaker
<p>What is the most efficient way to find a set of 5 geometrically constrained, non-collinear points within a 3D point cloud of, for example, 100 points?</p>

<p>All points are expressed with respect to a single world coordinate system.</p>

CC BY-SA 3.0
2013-06-20T03:37:04.703Z
What does "geometrically constrained" mean?  Why five?
Jeffε
CC BY-SA 3.0
2013-06-21T00:42:43.670Z
Are you given some kind of 5-point template and need to find a match for it ?
Suresh Venkat
CC BY-SA 3.0
2013-06-21T14:19:11.597Z
yes, that's right
jellybean
CC BY-SA 3.0
2013-06-22T11:44:26.043Z
What does "match" mean?  A translation of the template set?  Or do you also allow rotation?  What about scaling?  Arbitrary linear transformations?  Arbitrary _projective_ transformations?  **Please edit the question to make it self-contained and unambiguous.**
Jeffε
<cg.comp-geom>
Locating a set of 5 geometrically constrained points within a cloud of points
jellybean
# Locating a set of 5 geometrically constrained points within a cloud of points

(Asked by: username_0 on 2013-06-19)

What is the most efficient way to find a set of 5 geometrically constrained, non-collinear points within a 3D point cloud of, for example, 100 points?

All points are expressed with respect to a single world coordinate system.

**Tags:** cg.comp-geom
> **Comments:**
> **username_1**: What does "geometrically constrained" mean?  Why five?  
> **username_2**: Are you given some kind of 5-point template and need to find a match for it ?  
> **username_0**: yes, that's right  
> **username_1**: What does "match" mean?  A translation of the template set?  Or do you also allow rotation?  What about scaling?  Arbitrary linear transformations?  Arbitrary _projective_ transformations?  **Please edit the question to make it self-contained and unambiguous.**  

---

## 1 answers

### Answer by username_3 on 2013-06-21. Score: -1

Upper bound:

Make three sorted lists of point pointers, one for each dimension O(nlogn)

Pick a point in your reference template to be the "origin" and make 4 vectors to the other points O(1)

For each vector

Scan the list of all points to see if a sister point exists at this vector, if not throw it out as not an origin candidate. O(n)

If you allow rotations you are probably going to have to throw it in a quadtree and do some range queries; but after the first few are matched to the template it will be oriented allowing you to go back to vector lookups.

> **Comments:**
> **username_1**: _If you allow rotations you are probably going to have to throw it in a quadtree and do some range queries_ — Huh?  
> **username_3**: i.e. no scaling, just matching rotatations and translations of the 5 point template. Range queries let you disregard non-candiate points that are too close or too far. You have a better idea for a naive implementation Jeff? :)  

---

