15
$\begingroup$

I have a tetrahedron $t$ and a polyhedron $p$. $t$ is constrained such that it always shares all its vertices with $p$. I want to determine whether $t$ lies inside $p$.

I would like to add one detail to the problem in case it may contribute to the solution: $t$ is a Delaunay tetrahedron and faces of $p$ are triangular and are strongly Delaunay both with respect to vertices of $p$. A tetrahedron is Delaunay if circumsphere of its vertices contains no other vertex inside it. A face is strongly Delaunay if there exists a circumsphere containing vertices of that face on its surface but no other vertex on or inside it.

Following figures show the same problem in $2D$ space:

The original polygon $p$:

enter image description here

Delaunay triangulation of vertices of $p$:

enter image description here

Result of inside/outside test over triangles $t$(Shaded triangles are inside $p$ and rest are outside):

enter image description here

Desired result(pruning outside triangles):

enter image description here


My original problem is in 3D space so triangles $t$ in above figures translate to tetrahedrons and polygon $p$ translates to an arbitrary polyhedron $p$. I have figured out some formulations of this problem:

Formulation 1
The only parts of $t$ which can be outside $p$ are its edges and triangular faces but in general there may exist a $p$ which has edges of all outside $t$'s on its surface, so alternatively, this problem may also be formulated as to test whether for a tetrahedron $t$ there exists a face which lies outside $p$?

Formulation 2
I have another possible perspective towards this problem but lacking any formal idea:
Geometrically, if $t$ is outside then it will always be sticking on the outer surface of $p$. So if we can compute the contours(informally, the outer boundary) $C_{V}$ and $C_{V_{p}}$ such that $V=V_{t}\cup V_{p}$ and $V_t,V_p$ are sets of vertices in $t,p$ respectively, then $C_{V}=C_{V_p}$ iff $t$ lies inside $p$.

I would like to know:

  • How can I solve either of Formulation 1 or Formulation 2?
  • Or, is there any completely different approach to solve this?

Update:
I now realize that this problem can be reduced to Point in polyhedron problem. Since an outside tetrahedron $t$ will have at least one face which lies outside $p$, so any arbitrary point on that face(except its vertices,in general) will always lie outside $p$. Therefore, for each face of $t$, I need to take an arbitrary point and test if that point lies outside $p$.

From point in polygon article I came to know about Ray casting algorithm and Winding number algorithm. Ray casting is not numerically stable for cases where point lies on the surface of $p$. But numerical robustness of Winding number algorithm has not been addressed there.

Based on above, my core problem now seems to be(please suggest if it should be asked as a separate question):
Is there any numerically robust algorithm for point in polygon problem?

$\endgroup$
  • $\begingroup$ Just to clarify: 1) Can the polyhedron $p$ be non-convex, and 2) if $t$ and $p$ share a face or an edge (or part of one), does that disqualify $t$ from being "inside" of $p$? (Obviously, based on your requirements, $t$ and $p$ must be allowed to share vertices.) $\endgroup$ – Ilmari Karonen May 31 '14 at 17:01
  • $\begingroup$ @IlmariKaronen 1) Yes 2). No, as far as I can imagine, the only difference between inside and outside tetrahedron will be that its non-shared face/edge will lie outside if $t$ is outside $p$ and inside if $t$ is inside $p$(as I have also mentioned under Formulation 1). BTW, what do you mean by "...or part of one..."? $\endgroup$ – Pranav Jun 1 '14 at 1:34
  • 1
    $\begingroup$ Two coplanar faces or collinear edges might overlap only partially. This could happen even if $p$ itself has no coincident faces or edges, as long as it has more than two collinear or more than three coplanar vertices. $\endgroup$ – Ilmari Karonen Jun 1 '14 at 1:39
  • 1
    $\begingroup$ non-convexity has the oddity that all vertices can be inside the polyhedron and yet the tetrahedron can be outside (since an edge need not lie inside as a whole). Possible algorithm, see if edges (between polyhedron and tetrahedron) can have intersections => prob that tetrahedron lies outside is great $\endgroup$ – Nikos M. Jun 4 '14 at 20:36
  • 1
    $\begingroup$ Have you seen the Gilbert–Johnson–Keerthi distance algorithm? You would need to decompose the polygon/polyhedron into convex shapes first (as you noted, a simplicial complex would do the job). GJK is known to be very stable and very fast. $\endgroup$ – Pseudonym Jan 6 '17 at 1:55
2
$\begingroup$

I recently found one solution to this problem in a paper 'Robust inside-outside segmentation using generalized winding numbers' by Alec Jacobson et.al., here. It solves the problem of locating if a point is inside(or outside) an arbitrary(one with self-intersections, non-manifold, open-surfaces etc.) polygonal mesh using the notion of generalized winding number.

Problem can be solved if I compute the generalized winding number of the centroid of $t$ against the surface of $p$.

$\endgroup$
  • $\begingroup$ Point containment will not solve the problem: Picture $p$ a triangular prism with one side of ("Platonic") $t$ (slightly smaller, inside,) parallel and near to one of the triangular faces of $p$. Now subtract from $p$ a "needle tetrahedron" from the middle of that face to near one of the vertices "in the opposite face": None of $t$'s vertices is outside $p$, none of $p$'s vertices is inside $t$, yet $t$ is not inside $p$. $\endgroup$ – greybeard Feb 4 '17 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.