0

I have a problem to prove if a number of 4 points can form a convex hull and if a 5th points is inside the hull or not. I managed to solve the problem of the convex hull using triangles, however I don't know how to prove if the 5th point is inside the hull created by the other 4 points.

Any ideas?

Thank you!

Stefan
  • 83
  • 1
  • 6
  • 20
  • Could you explain what you mean by "I managed to solve the problem of the convex hull using triangles"? – M_M Oct 16 '14 at 18:30
  • @M_M http://stackoverflow.com/a/2122620/3502949 – Stefan Oct 16 '14 at 18:34
  • Try to add the point to the convex hull, if it cannot be done then the point is inside the hull, else it is outside the hull. You can decide whether "on the hull" is considered inside or outside the hull. Not clear if by 4-point you mean 4 dimensional convex hull or a convex hull of only 4 points but should work either way. – Nuclearman Oct 18 '14 at 21:50

3 Answers3

1

Assuming that you're asking about points on a plane - there is a standard approach for any polygon (convex or not) with any number of vertices.

HEKTO
  • 3,876
  • 2
  • 24
  • 45
  • This problem isn't about points on a plane -- the term '4-points' refers to a 4-dimensional space where each point has a set of coordinates like (a,b,c,d) or (0.1,2,54,0.4). – M_M Oct 16 '14 at 18:29
  • @M_M The term "triangles" suggests otherwise ("simplices" is standard for higher dimensions). – David Eisenstat Oct 16 '14 at 18:31
  • I think your right, my mistake in reading the question. It could be in any number of dimensions, the way it's phrased. – M_M Oct 16 '14 at 18:36
0

Call your points a,b,c,d. They form a tetrahedron. If the tetrahedron is not degenerated, the points are the vertex points (extreme points) of their convex hull.

To check this, check if a,b,c form a non-degenerated triangle. To do this compute the normal vector (call it n) of the triangle (b-a) cross (c-a). If it is zero then the triangle is degenerated, otherwise it is not.. The check if d is not in the plane of this triangle. It is if (d-a) dot product with n is zero. If so, the tetrahedron is degenerated.

Compute the normal vector for each of the 4 triangles of the tetrahedron. Each normal vector together with (any) point of the triangle describes a half-space; that is, all the points on one side of a plane. Let n be the normal vector and p a point of the triangle.

A point q is said to be inside of the half-space, if n dot (q - p) is negative.

Check for all 4 triangles, if the forth point is inside. If not, adjust the sign of the normal vector.

A point is inside the tetrahedron if it is inside for all 4 half-spaces.

Gyro Gearloose
  • 1,056
  • 1
  • 9
  • 26
0

If you were able to find the convex hull of the four points, then you are able to split the quadrilateral in two triangles by a diagonal (unless one of the points was interior, then you have a single triangle left).

So it all amounts to a point-in-triangle test.

Again, being able to construct a convex hull, you must already have the area test handy (sign of the area of a triangle). You fifth point is inside a given triangle when the area test reports the same sign for the three triangles formed by the point and the three edges of the given triangle.

  • If you want a solution that strictly minimizes the number of comparisons and arithmetic operations, let me know. Also read my own answer here: http://stackoverflow.com/questions/2049582/how-to-determine-a-point-in-a-triangle –  Oct 17 '14 at 17:10