1
$\begingroup$

Let $P$ be a indexable set(array) of points in $\mathbb{R}^3$ s.t. $P = \{p_0,p_1,p_2,...,p_n\}, p_i \in\mathbb{R}^3$.

I want to sort $P$ so that every 4 consecutive points forms a non-coplanar tetrahedra/3D-simplex/triangular pyramid (whatever you personally call it), I know there will be left over points, so I want to do this maximally, meaning I want to create the maximum number of tetrahedra from the set of points and have them back-to-back in the array as every 4 points. And any left-over points will be at the end of the array (after the tetrahedra) where I will have the starting index stored for those leftover points.

Does anyone know how to accomplish this? (and yes the tetrahedra can be arbitrary with no constraints, meaning they are allowed to intersect, but a point can only be used for a single tetrahedra)

(I know I can find a single simplex by first finding 2 points that are at a distance of $\epsilon$ away from each other (meaning I have 2 distinct points) then find a third point that is not colinear by using the orientation test (cross product not the zero vector of 2 vectors formed from the 3 points) then finding a fourth point by using the plane normal test (now that we have 3 points that form a plane we can create a vector from the plane to a new fourth point and compare the dot product of that point with the plane normal and if it is not zero then we have a valid simplex)). (Some thoughts on where to search is to see if this maximization problem has maybe a dual known minimization problem which I don't know what would be or to figure out if the naive algorithm of just grouping 4 points at a time until you can't anymore achieve the maximum or not).

Improve this question
$\endgroup$
5
  • $\begingroup$ It is not fully clear to me if the quadruples overlap or not (i.e. $1-2-3-4, 2-3-4-5, \cdots$ or $1-2-3-4, 5-6-7-8\cdots$. $\endgroup$
    – Yves Daoust
    Sep 26, 2022 at 8:30
  • $\begingroup$ It looks like you actually want to tesselate a point set in $\mathbb{R}^3$ into tetrahedrons. It's well studied problem, and many algorithms exist - please see: scicomp.stackexchange.com/questions/2026/… $\endgroup$
    – HEKTO
    Sep 27, 2022 at 0:59
  • $\begingroup$ And also this: doc.cgal.org/latest/Triangulation_3/index.html $\endgroup$
    – HEKTO
    Sep 27, 2022 at 1:00
  • $\begingroup$ @YvesDaoust the second way, where each index is only used once $\endgroup$
    – yosmo78
    Sep 27, 2022 at 4:05
  • $\begingroup$ @HEKTO I want to do this because this will be a good preprocessing step for creating 3D convex hull's on the gpu when doing the divide and conquer merge strategy. (at least that is what I am attempting to do) $\endgroup$
    – yosmo78
    Sep 27, 2022 at 4:06

1 Answer 1

Reset to default
0
$\begingroup$

Hint:

The naive method will not work. Assume four points forming a non-degenerate tetrahedron plus four coplanar points and no other alignment. Grouping the first four results in a single tetrahedron, while two are otherwise possible.

A heuristic is to first form all possible groups of coplanar points (four or more), and empty the largest groups first (by mating three points to a point of another large group), but I doubt that this is optimal.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for the insight $\endgroup$
    – yosmo78
    Sep 27, 2022 at 4:07

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.