Boldt 122 Report post Posted June 22, 2005 My problem is as follows: I have a point p in n-space laying in the cube defined by the two corners v_min and v_max each being a vector in n_space. eg \forall i \in \{ 0 .. n } v_min_i < = p_i <= v_max_i. I then need a clever way to construct a simplex that consist of n+1 vertices that all are corners in the box. I will denote the vertices of the simplex from s_0 to s_n. The simplex must be constructed in such a way that p can be written as a linear combination of s_i eg \sum_i=0^n k_i * s_i where k_i >= 0 and \sum_i=0^n k_i = 1. A brute force solution would be to test all possible simplexes, but as the dimension grow the number of possible simplexes grows at least exponentially and the running time would be unacceptable large. Does anyone know a clever way to either select the vertices that must be in the simplex or filter away the vertices that cannot possibly be part of the simplex until the n+1 corners of the simplex are found I thought about using hyperplanes spanned by some of the corners in n dimensions and filtering away all points that are at the wrong side of the plane It just comes to my mind that the problem also can be considered as follows: Construct the convex hull made out of the n+1 corners of the box that also contains p Best Regards Niels [Edited by - Boldt on June 22, 2005 9:45:50 AM] 0 Share this post Link to post Share on other sites
Dave Eberly 1173 Report post Posted June 22, 2005 I believe the following should work, illustrated for vertices with zeros and ones, but should not be a problem in general. In 2D, let P = (p0,p1) be the point in the rectangle. Let V = (v0,v1) represent the vertices of the rectangle. If p0 >= p1, keep vertices for which v0 >= v1 is true. These are (0,0), (1,0), and (1,1), and they form a simplex (triangle) containing P. If p0 <= p1, keep vertices for which v0 <= v1 is true . These are (0,0), (0,1), and (1,1), and they form a simplex containing P.In 3D, let P = (p0,p1,p2). If p0 <= p1 <= p2, keep vertices for which v0 <= v1 <= v2 is true. These vertices are (0,0,0), (0,0,1), (0,1,1), and (1,1,1), and they form a simplex (tetrahedron) containing P.I do not have a formal proof, but I think this works in any dimension. The algorithm is to sort the components of P, p[i0] <= p[i1] <= ... <= p[in], where (i0,i1,...,in) is a permutation of (0,1,...,n). The simplex is formed by those vertices V for which v[i0] <= v[i1] <= ... <= v[in]. The sorting is O(n*log(n)) and the test of vertices if O(n), so the full algorithm is O(n*log(n)). 0 Share this post Link to post Share on other sites