Edited by BluePhase, 24 October 2012 - 01:48 PM.
Subscribe to GameDev.net Direct to receive the latest updates and exclusive content.
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.
Posted 24 October 2012 - 01:47 PM
Edited by BluePhase, 24 October 2012 - 01:48 PM.
Posted 24 October 2012 - 02:52 PM
Posted 12 November 2012 - 04:39 PM
Posted 12 November 2012 - 04:45 PM
Posted 12 November 2012 - 05:14 PM
Posted 12 November 2012 - 06:42 PM
Posted 12 November 2012 - 06:53 PM
You can probably do better than this by starting with a sphere large enough to hold all the points and shrinking it "appropriately", depending on how many points of contact you currently have. I think this method should take time O(N), but it could be tricky to implement.
Edited by max343, 12 November 2012 - 06:54 PM.
Posted 12 November 2012 - 08:26 PM
You can probably do better than this by starting with a sphere large enough to hold all the points and shrinking it "appropriately", depending on how many points of contact you currently have. I think this method should take time O(N), but it could be tricky to implement.
I don't think that it's possible to do it in O(n) time for dimensions larger than 1 (I think that it's possible to construct a reduction from the diameter problem to the CH problem, but I'm not 100% sure about this). On the other hand an O(n*log(k)) implementation is possible (n is the number of vertices and k is the number of vertices on the convex hull), though it's not that trivial.
Posted 13 November 2012 - 07:58 PM
FindMinSphere(S, origSphereVerts) 1. sphereVerts = origSphereVerts, remainingVerts = empty 2. for each i[k] in random pi(1,2,...,length(S)) 2.1 if S[i[k]] is not contained in the sphere spanned by sphereVerts 2.1.1 sphereVerts = FindMinSphere(remainingVerts, EliminateExtraVertex(origSphereVerts + S[i[k]])) 2.2 remainingVerts += S[i[k]] 3. return sphereVerts EliminateExtraVertex(S) 1. X=S 2. if length(S)==5 2.1 X = from the 5 possible spheres in X choose the one that contains all five points 3. return X
Edited by max343, 13 November 2012 - 07:59 PM.
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.
GameDev.net™, the GameDev.net logo, and GDNet™ are trademarks of GameDev.net, LLC.