Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Wed Jul 23, 2014 10:01 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 2 posts ] 
Author Message
 Post subject: A question about closest points and geometry
PostPosted: Thu Mar 20, 2014 12:59 am 
Offline
User avatar

Joined: Sat Apr 21, 2007 11:21 pm
Location: Marin, CA
Let's say I have some 3 dimensional space with some number of meshes inside. (Could be puzzle parts for example.)
I know that none of them are closer than 1mm to any other part.
I'm only given the centroid locations as X, Y, Z coordinates, and a list for each part of the other parts that are within <= 1mm of a collision.

I connect each centroid to the centroids around it with an edge. I end up with a new non manifold network of edges and centroids.

Rotations are not allowed for what comes next.

Now, no matter how many centroids I have, it is safe to move any one centroid in any direction by 0.5mm without introducing a collision, right?

If I constrict all the edges by some amount like 0.4 and solve iteratively for the constraint that a centroid can't move locally more than 0.5mm relative to another connected centroid, including the direction the edge originally pointed in, am I still guaranteed a non-colliding system?

Or am I missing something?

If one of you knows a pure linear algebra way to do this I'll be impressed.

_________________
Jason Smith posted here as 'io' through 2012.
Visit Jason Smith's PuzzleForge on Shapeways!
Jason Smith's Puzzles - YouTube Channel.


Top
 Profile  
 
 Post subject: Re: A question about closest points and geometry
PostPosted: Thu Mar 20, 2014 2:43 am 
Offline
User avatar

Joined: Thu Jan 06, 2005 8:53 pm
Location: Los Angeles
I certainly can't think of any counterexample.
However, without taking the shapes into account, you certainly won't be able to get maximum compression.

And I'm guessing you're trying to minimize some property? Bounding box, or empty space perhaps?


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 2 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 7 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group