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

 04 April 2005 billrobertson42 Frequenter portfolio Bill Robertson Ohio, USA 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? share quote
 04 April 2005 playmesumch00ns Lord of the posts   render monkey pretty picture maker United Kingdom 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. share quote
 04 April 2005 billrobertson42 Frequenter portfolio Bill Robertson Ohio, USA 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 share quote
 04 April 2005 CGTalk Moderation Expert 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. share quote

 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 CGSociety Society of Digital Artists www.cgsociety.org Powered by vBulletinCopyright ©2000 - 2006, Jelsoft Enterprises Ltd.