Checking for a point inside a region on a spherical surface

zeeshanzia84

Newcomer
Hi everybody,

I am working on a 3D Morphing algorithm.

I have a point X on lying on a unit sphere in the spherical coordinate system. I have three other points A,B, and C which are also on the unit sphere. The sphere is centered at the origin.

I need to find out whether X lies on the spherical 'triangular' area enclosed by A,B, and C or not.

Can any one tell me how to do this?

Thanks a lot in advance.
 
Thanks for your time and the art work :)

Yes. But it won't be an actual triangle.

I have three points A,B,C which all lie on the surface of a unit sphere. I have another point X, which lies on the same sphere. I want to find whether X lies in the area bounded by A,B, and C. So it will be a triangle drawn on a spherical surface.
 
ok heres an idea
cover the area a,b,c with a texture
sample point x
if its the same colour as the texture its inside
if not its not
 
@Nutball

Yes, I have a large number of points.


@Davros

Thanks for the response. But, I am not rendering. So, I can't use technique. I am looking for some mathematical solution.
 
It seems that you'd be able to do this reasonably simply by using polar coordinates. Find, in polar coordinates, the position of all 3 of your points A, B and C. Since they lie on the surface of a sphere, their "length" component will always equal to the radius of the sphere. You need to then calculate the two angles for each point.

If you don't know how polar coordinates work, it's identical to the concept of declination and right ascension used in astronomy. To represent a point in 3D space, you can use 2 angles and a length. If you think of the night sky, it's like a big sphere surrounding the Earth. To locate a point on the night sky, you use one angle to represent the angle from North, and you use one more angle to determine how far up from the horizon that point is. You can apply the same principles and some simple trigonometry to determine polar coordinates from a set of cartesian coordinates.

Once you have all 4 of your points in polar coordinates, you can just compare their angles to ensure that they're all within each other. For example, let's demonstrate with a simpler problem: a regular 2D circle of radius 10. I have 2 points on the edge of my circle, A and B. A is located 25 degrees around the circle, B is located 50 degrees around the circle.

I want to know if point X, at a distance of 5 from the centre of the circle and an angle of 30 degrees, is within the arc bounded by points A and B. Since the distance is 5 (and the radius of the circle is 10), we know the point is inside the circle somewhere. And since the angle of point X (30 degrees) is between the two angles bounded by A and B (25 and 50 degrees, respectively), it's within the arc bounded by points A and B. Thus, point X is within the specified area.

You can generalise this same method to work in 3D, it's just that you'll have 2 angles to compare per point, rather than just 1. It would certainly be possible to do this in cartesian, but it seems like it would be easier using polar.
 
If you have the spherical polar coordinates it's a simple 2D point in triangle test (although you will need to rotate the coordinates appropriately each time because of coordinate wrap around).

If you have the cartesian coordinates you can just do a ray triangle intersection test of OX against ABC.

Either way, google and ctrl-c/ctrl-v will give you the way to do it :)
 
Last edited by a moderator:
For the triangle-case:

Suppose the stuff is in cartesian coordinates. The half-planes * determined by the side-lines of the triangle (on the sphere) correspond to half-spaces determined by planes containing the origin (in the embedding space). If the triangle's vertices are A, B, C in counter-clockwise order, then these planes have normals AxB, BxC, CxA. If X isn't contained by all of these half-spaces (so e.g. X*(AxB) < 0), then it's on the outside, otherwise it's inside.

Edit: * the triangle is the intersection of these
Edit2: this can be generalized to any shape that can be described as the intersection of a finite number of half-planes, so you only have to decompose your arbitrary shape into convex polygons
 
Last edited by a moderator:
Mate is right. Another way of doing the same calculation is as follows:

d1 = det([A B X]), d2 = det([A X C]), d3 = det([X B C])

If all determinants are the same sign, then the point is inside the triangle. I'm assuming that the origin is the center of the sphere, of course, and the points have cartesian coords.

EDIT: There was an error before, so make sure you didn't use the wrong formula! Also, you have to choose the sign - positive or negative - for all the determinants, depending on the orientation of triangle ABC.
 
Last edited by a moderator:
If you have the spherical polar coordinates it's a simple 2D point in triangle test (although you will need to rotate the coordinates appropriately each time because of coordinate wrap around).
Doesnt this give incorrect results due to a "straight" lines on the surface mapping to curved lines in this 2D unwrapping?
 
I'm pretty sure a linear interpolation in spherical polar coordinates produces a SLERP.
I don't think so. Imagine any two points with the same zenith angle (except pi/2, i.e. the equator). Linear interpolation will keep zenith constant, which is obviously not an SLERP.

On a sphere, three points can define two triangles.
Good point! The test remains the same the same, though. Just need to decide which half is inside.
 
Back
Top