Point Cloud - what tree structure to use for selection in polygon?

[JamesMaeding]

I am making a tool to find all point cloud points inside a polygon.

I don't mean autocad point cloud points, but my own points in memory.

I have done K-D tree structures before to locate the triangles under a point fast, but this is like the reverse.

Normally this kind of task is handled with sorting the data by X and Y and then subdividing the set of data into left and right halves, then up and down halves, and so on until you get down to just one item per "leaf", if this is a tree.

All I can think of for helping find points in a polygon is to sort by X and Y, and use that to narrow down the points within the bounding box of the polygon. Then I was thinking cut that data set into vertical strips with every vertex in the polygon defining a vertical cut spot, so I have straight lines forming zones within that vert strip. Then analyze those zones to keep or discard points, like:

Now these approaches do not make use of a tree structure, just the data sorted by x and Y.

I can't think of a better way. Can anyone point me in a direction that is more efficient?

I have watched selection in progs like recap and its about instant.

Selection in Trimble business center and carlson P3D is a bit slower.

Maybe an adesk'er could comment on what kind of structure to study?

Something to flex their neurons before the weekend hits?

thx

[_gile]

Hi,

I do not think that using a tree structure is of any use in the case of a selection. the question is, for each point independently of each other, whether it is inside the polygon.
I'm not sure that organizing the points in a specific data structure (tree or otherwise) is only useful when we use a relationship between these points.

[JamesMaeding]

@_gile 

Yah, I can't imagine how a tree will help, but man the recap selection is fast.

thx for the reply!

[brianchapmandesign]

This is interesting. Reminds me of something I messed with years ago. I was trying to auto-generate building exterior walls and the roof from selected point cloud data.  With a lot of assistance we generated code that successfully constructed the 3-dimensional shape of the building including the walls and roof.  The trick was to code like a radio wave, finding the center position/point and projecting out. I had to beg for help on the most complicated portion of it from people with better skill than me, and it was fairly complex, but in the end we were able to select all the points in a point cloud that consisted of the exterior of a building and have it auto-generate the walls and roof.  A few years later drones came out with tech that accomplished that so it defeated the purpose.

[JamesMaeding]

@brianchapmandesign 

Cool. One of the uses for my polygonal selection will be to get a strip of points along some linear feature like a road curb, and figure out the profile of the top of curb or gutter. I'm surprised none of the point cloud software makers have done this yet. They all try to help you with section views and so on, but they fail to see the correct way to get clean features is draw the horizontal first, then get the profile from a best fit of a strip of points. This thing of drawing 3d lines from 3d point to 3d point is nuts. You get wandering results yet everyone knows a curb will be rather regular in reality. Walls and pipes can fit regular shapes, but things like curbs vary enough that you cannot best fit a fixed section along the length, you must find that top of curb edge which is tricky as its radiused a bit, and can have just enough odd things that its better if a human draws its horizontal first. I guess finding the top of a retaining wall would be similar. That is the trick thing with survey, you are not trying to just get a pretty model in the end, you want it to match reality which may be ugly.