- #1
KLoux
- 174
- 1
Hello. I am creating an algorithm for finding the locations of nodes connected by rigid links. Some nodes in the system are constrained in place, and to one node (a *special* node), a displacement is applied. The algorithm should be able to determine the locations of the other nodes by knowing only the lengths of all of the links and the locations of the constrained nodes.
To do this, I am treating the problem as the intersection of three spheres. The centers of the spheres are known points (either constrained nodes or nodes that were previously solved using the same technique) and the radii of the spheres are the lengths of the appropriate links. The place where the spheres intersect is the location of the node.
Of course, the intersection of three spheres (usually) gives two points, and I have to choose between them to determine the correct location of the node. This is where I am stuck now. Previously, I was comparing the two solutions to the original location of the node (before the displacement was applied to the *special* node), and this works in most cases, but not all. I have an idea for a more robust solution, but I can wrap my head around an implementation:
There is a plane that contains the three sphere center points. Between the two solutions, one will always lie on one side of the plane, and the second will lie on the opposite side of the plane. I think it is safe for me to assume (due to the geometry of my system of links) that the correct solution will be on the same side of that plane as the original location of the node. The problem is that this plane moves as the system of links moves (but the system is constrained so that the plane isn't going to rotate anywhere near 90 degrees, usually it will probably be < 20 degrees), so I have the original node and the original plane, and a set of two solutions with a new plane. So my two questions:
1. How can I determine if point X is on the same side of plane A, and point Y is to plane B?
2. Is there a better way to solve a system like this that avoids this problem entirely?
Hopefully this isn't too confusing... if it is, please ask and I will try to clarify. Thanks in advance!
-Kerry
To do this, I am treating the problem as the intersection of three spheres. The centers of the spheres are known points (either constrained nodes or nodes that were previously solved using the same technique) and the radii of the spheres are the lengths of the appropriate links. The place where the spheres intersect is the location of the node.
Of course, the intersection of three spheres (usually) gives two points, and I have to choose between them to determine the correct location of the node. This is where I am stuck now. Previously, I was comparing the two solutions to the original location of the node (before the displacement was applied to the *special* node), and this works in most cases, but not all. I have an idea for a more robust solution, but I can wrap my head around an implementation:
There is a plane that contains the three sphere center points. Between the two solutions, one will always lie on one side of the plane, and the second will lie on the opposite side of the plane. I think it is safe for me to assume (due to the geometry of my system of links) that the correct solution will be on the same side of that plane as the original location of the node. The problem is that this plane moves as the system of links moves (but the system is constrained so that the plane isn't going to rotate anywhere near 90 degrees, usually it will probably be < 20 degrees), so I have the original node and the original plane, and a set of two solutions with a new plane. So my two questions:
1. How can I determine if point X is on the same side of plane A, and point Y is to plane B?
2. Is there a better way to solve a system like this that avoids this problem entirely?
Hopefully this isn't too confusing... if it is, please ask and I will try to clarify. Thanks in advance!
-Kerry