PDA

View Full Version : How to figure out points that are close to each other in an arbitrary set of points

billrobertson42
04-28-2005, 01:55 AM
Ok, I'm sure I'm not the first with this idea...

I'm working on a plug-in to align points that are "close enough" to each other points from an arbitrary set of points. For example, you're working on a model that consists of multiple mesh objects and you want to make sure that the edges of the various meshes line up exactly. You select the points on the matching edges, and if they're within a given tolerence the postion of those two points will be averaged.

In order to avoid having to compare the location of every point to every other point in the set I want to group them so I only have to compare the locations of those that are close to each other. My cunning plan is to create a sparse matrix and the location of each point will be specified by the original coordinate divided by the tolerence. And then traverse through the sparse matrix looking for clusters of points that might be close enough and then average them.

Does this make sense?
playmesumch00ns
04-28-2005, 09:01 AM
I'm not sure I entirely understand how you would construct this matrix. Without having a clear picture in my mind it's hard to judge how effective it would be...

The standard (and proven) way of doing this would be to use a Kd-tree (google for it). This is a heirachical spatial data structure that allows you to quickly find points in space near to a specified search point. A good Kd-tree implementation is a very useful thing to have around as you can do all sorts of things with it.
billrobertson42
04-28-2005, 10:58 PM
I guess what I was considering would have been sort of like re-mapping the coordinates of the points to a lower resolution coordinate system.

I figured that there had to be a more standard (i.e. proven) way of doing this though. I'll check out the kd tree.

thanks
CGTalk Moderation
04-28-2005, 10:58 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.