1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ What does "geometrically constrained" mean? Why five? $\endgroup$ – Jeffε Jun 20 '13 at 3:37
  • $\begingroup$ Are you given some kind of 5-point template and need to find a match for it ? $\endgroup$ – Suresh Venkat Jun 21 '13 at 0:42
  • $\begingroup$ yes, that's right $\endgroup$ – jellybean Jun 21 '13 at 14:19
  • 1
    $\begingroup$ 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. $\endgroup$ – Jeffε Jun 22 '13 at 11:44
-1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If you allow rotations you are probably going to have to throw it in a quadtree and do some range queries — Huh? $\endgroup$ – Jeffε Jun 22 '13 at 11:45
  • $\begingroup$ 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? :) $\endgroup$ – Chad Brewbaker Jun 25 '13 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.