Checking for a point inside a region on a spherical surface

[sebbbi]

This is very similar to the solution Mintmaster suggested:

On cartesian coordinates, sphere center at origin (0,0,0), points and triangle vertices at surface of unit sphere.

a, b, c = triangle vertices (in clockwise order)
x = point on sphere

p1 = dot(x, cross(a, a-c))
p2 = dot(x, cross(b, b-a))
p3 = dot(x, cross(c, c-b))

If all p1, p2 and p3 are positive, the point is inside the triangle. Otherwise it's outside.

 

[Simon F]

On a sphere, three points can define two triangles.

If the points are all you are using, then surely it could be 4 triangles.

 

[Xmas]

If the points are all you are using, then surely it could be 4 triangles.

I don't think so, at least not if you use the shortest distance between points. I guess it's not clearly defined what you get when you use antipodes.

 

[Simon F]

I don't think so, at least not if you use the shortest distance between points. I guess it's not clearly defined what you get when you use antipodes.

The only definition given by zeeshanzia84 was

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

You therefore need another point to really identify which of four "triangular" areas.

 

[Xmas]

You therefore need another point to really identify which of four "triangular" areas.

I still don't see how you count four areas. If you use the shortest connection between two points as edges, you get two areas. If you allow the shortest or the longest then you get more than four, and you get intersections using two or three of the longer paths. If you allow any "straight" connections then you can have an infinite number of "triangular" areas.

 

[Simon F]

I still don't see how you count four areas.

Let's pick 3 points on the earth: Amsterdam, Berlin and Munich (spelled with a C ) (I wanted to use Cologne but Google maps doesn't draw a nice diagram )

We have the "obvious" triangle that contains a big chunk of Germany, but we can also form 3 other ABC triangles: One each containing Bremen, Paris and Prague respectively.

 

[Mintmaster]

Simon, you're using lines that aren't the shortest distance between points as Xmas is saying you should.

Xmas, it looks like Simon is excluding triangles with edges that intersect at places other than the endpoints.

 

[Simon F]

Simon, you're using lines that aren't the shortest distance between points as Xmas is saying you should.

I'm being pedantic, but that wasn't part of the specification. All that was defined was that there were 3 points defining the region and I'm just stating that, given the topology of a sphere, there is more than one such solution. (shrug).

 

[Xmas]

I'm being pedantic, but that wasn't part of the specification. All that was defined was that there were 3 points defining the region and I'm just stating that, given the topology of a sphere, there is more than one such solution. (shrug).

Even restricted to "straight" edges that lie on a plane intersecting the sphere, there are still an infinite number of connections between two points, so you'd get an infinite number of triangles. That is obviously not what the thread starter wants. Only two of these edges are special: the shortest one and the longest one (and antipodal points have neither), which both lie on the plane specified by both points and the sphere centre.

If you use the shortest edges you end up with two areas that you could call triangles, a smaller and a larger one. OTOH, if you assume you can pick either edge then you end up with eight different sets of three edges, i.e. 16 areas. And if you use two or three of the long edges, they will intersect at the antipodal of the third point. I still don't see how you count 4 triangles.

 

[Simon F]

Even restricted to "straight" edges that lie on a plane intersecting the sphere, there are still an infinite number of connections between two points, so you'd get an infinite number of triangles.

No, I was assuming "great circle" routes, i.e. the paths that are formed by the intersection of the sphere's surface and the plane formed by the centre of the sphere and the two vertices in question.

If you use the shortest edges you end up with two areas that you could call triangles, a smaller and a larger one. OTOH, if you assume you can pick either edge then you end up with eight different sets of three edges, i.e. 16 areas. And if you use two or three of the long edges, they will intersect at the antipodal of the third point. I still don't see how you count 4 triangles.

Arghh!! Serves me right for trying to do it all in my head and not drawing a diagram. Slice an object in half 3 times and you end up with 8 segments which means there are 8 "triangular" areas. (**Ignoring cases where the 3 original points and the centre of the sphere are coplanar). I really am getting stupid in my old age.

 

[Mintmaster]

No, I was assuming "great circle" routes, i.e. the paths that are formed by the intersection of the sphere's surface and the plane formed by the centre of the sphere and the two vertices in question.

Which is why he deduced that you were talking about the shortest and longest, as those are "great circle" routes.

Arghh!! Serves me right for trying to do it all in my head and not drawing a diagram. Slice an object in half 3 times and you end up with 8 segments which means there are 8 "triangular" areas. (**Ignoring cases where the 3 original points and the centre of the sphere are coplanar). I really am getting stupid in my old age.

I don't know if that's the right way to think about it. Those 8 pieces won't always go through the three original points. For example, two pieces will be identical but from opposite sides of the sphere.

I think you were right in saying 4, assuming "long" edges are allowed. They would be:
(short, short, short)
(long, short, short)
(short, long, short)
(short, short, long)

Two long edges will always intersect each other twice - once at the original triangle point common to the edges, and once at its antipode. That creates a disjoint "enclosed" region.

 

[Simon F]

Mintmaster,
To confirm it, take a ball and a marker pen . As long as the three points and the centre of the sphere aren't coplanar, it does generate 8 "triangular" regions**.




**Not that I've proved it.. There might be another special case I've missed.

 

[Mintmaster]

Mintmaster,
To confirm it, take a ball and a marker pen . As long as the three points and the centre of the sphere aren't coplanar, it does generate 8 "triangular" regions.

I was just going the description in your last post. I know there are 8 pieces from the slicing, but only one touches your original three points. In addition to this "obvious" triangle, I see three more that you can make by gluing a half-sphere onto any of its three edges.

However, in my last post I forgot that you can invert any of these to get 8 total areas. Still, I don't see how those are related to the pieces after slicing other than coincidentally matching the number.

 

[Simon F]

I was just going the description in your last post. I know there are 8 pieces from the slicing, but only one touches your original three points.

Hmm that's a good point. I'd discussed this in our office and our definitions had changed to only use the slices defined by the points and not the points themselves.... a bit like how one evaluates the whether a pixel is inside a triangle in a hardware renderer.

 

[Christer Ericson]

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.

You describe the standard test for containment in a triangle in the plane, but that's not necessarily sufficient for a triangle on a sphere.

The connecting arcs between three points on a sphere form TWO spherical triangles: one smaller (inner) and one larger (outer) triangle. (Unless all points lie on a great circle in which case the two are equally large, but we can ignore that special case for this discussion.)

Your test only works for the smaller of the two spherical triangles. For the larger triangle you effectively need to "negate" the test and say that you're contained if you're NOT inside the smaller triangle.

IF you can assume that the vertices of the triangle always describe the smaller spherical triangle in a consistent (clockwise, say) orientation, THEN what you suggest works fine.

However, it's easy to picture a situation where you have triangle vertices moving around on a sphere, representing a filled smaller spherical triangle, where suddenly the vertices cross over a great circle and now the small triangle became a large spherical triangle, with a filled interior that now encompasses more than a hemisphere. At that point your test fails, as you now need to use the "negated" test I mentioned.

Nitpicky perhaps, but important to consider.

 

[Mate Kovacs]

You're right.

This case can be detected by checking whether some vertex (any of the three will do) is on the "wrong" side of the plane corresponding to the opposing side-line (e.g. if C*(AxB) < 0, supposing a CCW winding).

 

[Mintmaster]

Your test only works for the smaller of the two spherical triangles. For the larger triangle you effectively need to "negate" the test and say that you're contained if you're NOT inside the smaller triangle.

Yup, we've been discussing that later in the thread:
http://forum.beyond3d.com/showpost.php?p=1180608&postcount=18

By "half" I meant which of the two areas.