How to figure out points that are close to each other in an arbitrary set of points

Become a member of the CGSociety

Connect, Share, and Learn with our Large Growing CG Art Community. It's Free!

Thread Tools Display Modes
  04 April 2005
How to figure out points that are close to each other in an arbitrary set of points

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?
  04 April 2005
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.

You can have your characters photoreal, fast or cheap. Pick two.
  04 April 2005
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.

  04 April 2005
Thread automatically closed

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.
CGTalk Policy/Legalities
Note that as CGTalk Members, you agree to the terms and conditions of using this website.
Thread Closed share thread

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Society of Digital Artists

Powered by vBulletin
Copyright 2000 - 2006,
Jelsoft Enterprises Ltd.
Minimize Ads
Forum Jump

All times are GMT. The time now is 05:02 PM.

Powered by vBulletin
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.