How Do 3D Coordinates and Radii Affect Vector Paths Between Points?

[ckirmser]

I'm not sure if this is the right forum - please move the thread, if not - but, here goes...

I have a collection of 3d coordinates, each with a radius of varying amounts. Each of the coordinates is to be linked to each of the others, unless a third coordinate - with its radius - blocks the straight line path between the first two.

I'm thinking of an adjacency table where the intersection of the X, Y lines would be the length of an unbroken vector between the two points.

Any ideas?

Thanx in advance for any help!

 

[jbriggs444]

Re-wording so that the problem makes sense to me...

You have a collection of vertices specified as coordinate 3-tuples. Around each vertex you have a sphere of some radius. The radius of the sphere can be different for each vertex. Links (line segments) are to be drawn between each pair of vertices but only if those line segments do not intersect with the spheres around any other vertices.

You are after a computational approach that will allow you to determine which connecting line segments meet this criterion and which do not?

 

[ckirmser]

You have it spot on.

I'd like to take my table of coordinates, run the computational process and have a resulting adjacency table of those coordinates with surviving links. It'd also be nice if the table showed the length of each link.

I was never the best with matrix operations it's been years, anyway.

 

[jbriggs444]

Given two points, can you code up a test to see whether the line connecting those two intersects with the sphere of given radius around a given point?

 

[ckirmser]

My idea would be to see if the third point lies on the line formed by the first two. But, what throws me is including the radius.

I didn't know if maybe this might be a common problem - say, in gaming - that may already have a formula I didn't know about.

 

[jbriggs444]

My idea would be to see if the third point lies on the line formed by the first two. But, what throws me is including the radius.

I didn't know if maybe this might be a common problem - say, in gaming - that may already have a formula I didn't know about.

Possibly there is a better approach, but...

Call the points at the ends of the line segment a and b. Call the third point c. Call its radius r.

Define one plane that is perpendicular to line ab at point a. Call this plane A. Define a second plane that is perpendicular at point b. Call this plane B. There are three immediately obvious conditions for point c. It can lie between the planes, on the "a" side of both planes or on the "b" side of both planes.

To determine which, take the dot product of ab and ac. If the product is positive, c is on the b side of plane A. If negative, it is on the a side. Similarly, take the dot product of ba and bc to determine which side of plane B point c is on.

If point c is on the a side of both planes then it suffices to check whether point a falls within radius r of point c. Similarly, if point c is on the b side of both planes, it suffices to check whether point b falls within radius r of point c. The more difficult case is when point c falls between planes A and B.

Compute the distance from point c to line ab. This is the length of the projection of ca on plane A (or, equivalently, the projection of cb on plane B). One way to compute this would be as the vector cross product of ca and ba and divide by the length of ba.

Compare the computed distance to r. If it is greater than r, then the sphere around c does not intersect line ab. If it is less than r then the sphere does intersect line ab. And because we know that point c is between planes A and B, we can easily see that the intersection includes at least a portion of line segment ab.

 

[ckirmser]

Possibly there is a better approach, but...

Call the points at the ends of the line segment a and b. Call the third point c. Call its radius r.

Define one plane that is perpendicular to line ab at point a. Call this plane A. Define a second plane that is perpendicular at point b. Call this plane B. There are three immediately obvious conditions for point c. It can lie between the planes, on the "a" side of both planes or on the "b" side of both planes.

To determine which, take the dot product of ab and ac. If the product is positive, c is on the b side of plane A. If negative, it is on the a side. Similarly, take the dot product of ba and bc to determine which side of plane B point c is on.

If point c is on the a side of both planes then it suffices to check whether point a falls within radius r of point c. Similarly, if point c is on the b side of both planes, it suffices to check whether point b falls within radius r of point c. The more difficult case is when point c falls between planes A and B.

Compute the distance from point c to line ab. This is the length of the projection of ca on plane A (or, equivalently, the projection of cb on plane B). One way to compute this would be as the vector cross product of ca and ba and divide by the length of ba.

Compare the computed distance to r. If it is greater than r, then the sphere around c does not intersect line ab. If it is less than r then the sphere does intersect line ab. And because we know that point c is between planes A and B, we can easily see that the intersection includes at least a portion of line segment ab.

Hmm.

Matrix operations, it looks like. I'll have to cogitate on your answer for a while to distill it from words into a formula. My poor old brain hasn't done this sort of thing since the 80s.

Thanx for the reply, kind sirrah; from first glance, it looks like what I'm after, but getting what I need out of it will take some work on my part.

 

[ckirmser]

In doing more research, I'm finding that the line equation isn't a simple thing like y = mx + b.

Oh no no no.

This is going to be a tough nut to crack. Mainly because most of what I'm finding on figuring the line equation connecting two 3d points looks to require some prior knowledge. Maybe I had that knowledge back in college, but that was over 20 years ago; it's covered under thick, impenetrable layers of brain dust now.

 

[aikismos]

Here's a thought.

1. For every ordered triple in space, find the plane it lies in by converting three points to two vectors and take the cross-product which is the normal vector
2. Substitute any of the three points and use the normal vector to solve for the equation of the plane in space.
3. Translate the plane and points in space to two dimensional plane and use simple planar geometry techniques
   
4. At this point, all you have to do is find a line perpendicular (radius) to a line segment (the end points that might intersect the sphere).
5. Use the distance formula to see if the contained point and the point of intersection in the line exceeds the radius