Can a point view another point around an obstructing point?

[wiyosaya]

I am not sure that this is the correct forum for this question.

I have multiple sets of 3, 3D (x, y, z) points in space. They are fixed points in space, and I cannot move them. Each point is weighted with a pressure value. I need to be able to determine if point 1 can view point 3 given that point 2 might prevent point 1 from viewing point 3.

What I am attempting to do is write a triangulation algorithm, only I have to create the triangles between points that are fixed. I cannot move them. The result should look as close as possible to a contour map.

If I look at the system of points as if it were flattened, point 3 might be either too far left or right of point 2 such that drawing a triangle edge either too far left or too far right of point 2 will overlap an edge from an existing triangle, and that causes an incorrect triangulation.

For example, I am using C#, and the Vector3D class, and I figured that I might be able to use the "AngleBetween" function to calculate the angles between point 1 and point 3, and point 1 and point 2 and then determine if the angles are such that point if the angle between point 3 is greater than the angle between point 2, then point 1 will not be able to triangulate with point 3 properly. However, the angle calculated by the AngleBetween function does not give angles that consistently indicate the viewability of point 3 from point 1 given that point 2 might be obstructing. I assume that the AngleBetween function is not calculating the angle that would allow me to solve this problem.

I have had a course in linear algebra, however, I do not use it regularly, so I am having difficulty in determining what to do to make the program work as I would like it to.

Does anyone have an idea how this might be solved? I am really looking for suggestions as to how to set up this problem mathematically as opposed to how to program it in C#, or any language, for that matter. The mathematics is what I need help with, not the programming language.

Thanks in advance.

 

[AlephZero]

Maybe you want to calculate the angle between the vectors (point2 - point1) and (point3 - point1) and check if it is close to 0, instead of calculating two different angles.

Or instead of trying to invent your own method, see http://en.wikipedia.org/wiki/Delaunay_triangulation

 

[wiyosaya]

Thanks for the suggestion. I'll have to give that a try to see if it works.

I looked at Delaunay Triangulation, however, there are complications that are a result of the default way that openGL renders its triangles. If I were interested only in the distance between points, Delaunay would work great; however, what I am really interested in is producing a contour map of the pressures at each point. If I triangulate simply based on distance, the default openGL rendering generates artifacts. The best openGL rendering follows a path of the least differential pressure between points. In essence, it ends up more of a routing problem, like Dykstra - http://en.wikipedia.org/wiki/Dijkstra's_algorithm

 

[Stephen Tashi]

If you are trying to make a contour map, I suggest you research algorithms used by software for surveyors. Surveyors often need to draw contour maps from irregularly spaced measurements.

I haven't researched surveying software recently. I've had experience drawing contour maps by hand. In writing some contour drawing software for a grid years ago, I do recall that not all contour drawing programs are based on finding the "even" elevations on the sides of a triangle. Some use a method closed to the manual method, which involves picking a given contour and "following" it across the map.

 

[Stephen Tashi]

...and something to keep in mind is that drawing contours is a problem that need not have a unique answer. For example if you have found a point where the elevation (or pressure) is 96 and you want to see how the 96 contour continues, you look for a point in the vicinity that has an elevation of 96 or greater and another point that has an elevation of 96 or less. If you have fairly smooth terrain there will be only one such pair of points. However, in very rough terrain there may be several pairs of points. The contour you are drawing may not go directly from where you are to any point you could interpolate. It might even turn around. For example if you are interpolating to find the 96 contour near the top of a ridge whose top is, say, 96.3 and your measurements are not finely spaced enough then you won't be able to determine when the 96 contour should cross a little valley in the ridge and proceed on the other side.