Re: How to find closest point(s) around a specific point in point cloud?

On Mar 31, 11:03 am, Willem <wil...@xxxxxxxx> wrote:
Ed wrote:

) Wait. Why suggest a linear search of the entire array?
)
) what's wrong with this pseudocode algorithm?
) Given point (P,Q,R)
)
) number of points found = 0
) current distance = 0
) while number of points found < 10
) {
) searcharray=find all points in shell between current distance and
) current distance + 1

Find all points in shell ?
You make it sound as if it's easy, but I don't think it is.
In fact, I think this alone requires a linear search of the array.

Why hard? We are working in integer dimensions.
Given point 5,4,3 the unit shell (points exactly 1 unit away)
includes the points
5,4,4
5,4,2
6,4,3
4,4,3
5,5,3
5,3,3

points in the volume between one and two units away include (NOT in
order of distance!)
4,3,2
5,3,2
6,3,2
4,3,3
6,3,3
4,3,4
5,3,4
6,3,4
4,4,2
6,4,2
4,4,4
6,4,4
4,5,2
5,5,2
and so on.
I did not code it out. maybe I will try that tonight.
maybe it would be easier to consider loops on integer coordinates.
then the first iteration would include these points.

The key of what I am suggesting is not to start the search at 0,0,0.
Maybe I assumed wrong that your suggestion of linear search starts
there and not at the point of interest.

4,3,4



) <snip>
)
) That should find things faster. Defining the "find all points in
) shell" function can be tricky since the array in rectilinear but the
) shell is circular.

Even if the shell were rectilinear it would be more than just 'tricky'.
How are you going to find all points that fall inside a given box without
looking at most (if not all) of the points ?

the coordinates are integers. it is an array space, not a real
coordinate space. That simplifies the search.
So maybe you can call it a linear search from the point of interest.

Ed
.

Relevant Pages

  • Re: How to find closest point(s) around a specific point in point cloud?
    ... current distance = 0 ... Find all points in shell? ... I think this alone requires a linear search of the array. ...
    (comp.programming)
  • Re: Minimal keywords needed for constructing a full CL system
    ... The one puzzle that baffled me relentlessly at the time, ... It seemed weird and unsatisfying to say that LAMBDA and AREF were ... (as opposed to N, the number of items of the array that is being indexed, e.g. ... simply by doing a linear search and pessimizing the lookup of all items to be ...
    (comp.lang.lisp)
  • Re: Search algorithm to use
    ... >order, and the array is less than 50 elements, and I want to find the ... >benefit on this data set. ... is horribly expensive or you loop repeatedly on the search, a linear search ... CLC FAQ CLC readme: ...
    (comp.lang.c)
  • Re: a rand array
    ... check for equals in array is O ... and randand goto label until no equal ... inserting ... >Linear search isn't all that great, but it doesn't matter much in this case. ...
    (comp.lang.c)