Local convexity
category: general [glöplog]
Hi all,
I'm having a rather simple geometric problem for which I'm trying to find an efficient solution. The problem at hand is a local convexity test for an edge:
Given two space curves p & q and three consecutive points on each curve, say p_i-1, p_i, p_i+1 and q_j-1, q_j, q_j+1, I need to decide whether an edge connecting p_i and q_j is locally convex, where local convexity is defined as "lies on the convex hull of all six points".
My intuition tells me that this should be doable without explicit computation of the convex hull but everything I have come up with so far fails for certain configurations. Any ideas on the subject are greatly appreciated!
I'm having a rather simple geometric problem for which I'm trying to find an efficient solution. The problem at hand is a local convexity test for an edge:
Given two space curves p & q and three consecutive points on each curve, say p_i-1, p_i, p_i+1 and q_j-1, q_j, q_j+1, I need to decide whether an edge connecting p_i and q_j is locally convex, where local convexity is defined as "lies on the convex hull of all six points".
My intuition tells me that this should be doable without explicit computation of the convex hull but everything I have come up with so far fails for certain configurations. Any ideas on the subject are greatly appreciated!
7
8
7
what do you mean by "lies on the convex hull" ? If you mean "in the convex hull" I guess this is close to a tautology. Do you mean "on the boundary of the convex hull" ?
Also, what role plays the two curves? Given any triple of points in your (vector?)space, you can always construct a curve passing through them.
Also, what role plays the two curves? Given any triple of points in your (vector?)space, you can always construct a curve passing through them.
Hi Hyde,
thanks for taking the time to reply.
Of course I meant the latter, i.e. on the boundary of the convex hull.
The two curves are given space curves of arbitrary length that should be triangulated using a BBT (triangle strip) that satisfies certain constraints, one of them being the local convexity of each "diagonal" edge (or to me more accurate one goal is to minimize the number of diagonal edges that do not meet the local convexity criterion).
thanks for taking the time to reply.
Of course I meant the latter, i.e. on the boundary of the convex hull.
The two curves are given space curves of arbitrary length that should be triangulated using a BBT (triangle strip) that satisfies certain constraints, one of them being the local convexity of each "diagonal" edge (or to me more accurate one goal is to minimize the number of diagonal edges that do not meet the local convexity criterion).
given two of your six points p,q. Then the line [p,q] lies on the boundary if it is contained in a face of the convex hull polyhedron. This means that there exists another point u in your collection of six points such that the convex hull spanned by (p,q,u) defines a plane such that all the other points in the convex hull lies entirely on one side of this plane or the other.
So, given (p,q), I think you could just loop through every possible choice for u (there are just 4 such choices) and check for each choice if the remaining 3 points lie entirely on one side of the plane spanned by the pair of vectors (p-u, q-u) or the other. If you get to a point u where this happens then you're done and if you loop though all u's without success, the segment [p,q] intersects the interior of the hull.
I am sure there are degenerate cases of colinearity where this fails, but it should solve the generic cases unless I screwed up ;)
So, given (p,q), I think you could just loop through every possible choice for u (there are just 4 such choices) and check for each choice if the remaining 3 points lie entirely on one side of the plane spanned by the pair of vectors (p-u, q-u) or the other. If you get to a point u where this happens then you're done and if you loop though all u's without success, the segment [p,q] intersects the interior of the hull.
I am sure there are degenerate cases of colinearity where this fails, but it should solve the generic cases unless I screwed up ;)
and the curves of yours are not relevant for the combinatorics here, if I understand correctly.
reading your post again, I see you wanted an "efficient" method, so perhaps you should go on looking :)
Hi. Geometry is not my strong point, so I migh have flows on the following. Also, it's only 2D :(
You have the P line (in blue) and Q line (in red). Your edge (the black line) belongs to the convex hull if all A, B, C and D fall in the same side of the black line (same half-space), ie, the area of the four triangles APQ, BPA, CPQ, DPQ have the same sign ? You can compute these areas by 2D cross products (Aapq=(q-a)x(p-a)/2, etc).
I cannot demonstrate this (so take with care...), and I'm not sure how to extend it to 3D...
You have the P line (in blue) and Q line (in red). Your edge (the black line) belongs to the convex hull if all A, B, C and D fall in the same side of the black line (same half-space), ie, the area of the four triangles APQ, BPA, CPQ, DPQ have the same sign ? You can compute these areas by 2D cross products (Aapq=(q-a)x(p-a)/2, etc).
I cannot demonstrate this (so take with care...), and I'm not sure how to extend it to 3D...
BPA -> BPQ, of course...
Thanks for the suggestion, if I (or someone else for that matter) can't come up with a simpler solution I'll implement that.
Concerning the curves not being relevant:
I think so too, but I wanted to mention it in case it helps finding a simpler solution.
One thing given by the fact that all p_i belong the the same curve as well as all q_j belonging to another curve is the fact that any triangulation will always contain the edges (p_i-1, p_i), (p_i, p_i+1), (q_j-1, q_j) and (q_j, q_j+1).
One of the shortcuts I tried is using the signs of the dihedral angles in all possible triangulations to determine convexity of the edge in question, but that didn't yield anything useful.
Concerning the curves not being relevant:
I think so too, but I wanted to mention it in case it helps finding a simpler solution.
One thing given by the fact that all p_i belong the the same curve as well as all q_j belonging to another curve is the fact that any triangulation will always contain the edges (p_i-1, p_i), (p_i, p_i+1), (q_j-1, q_j) and (q_j, q_j+1).
One of the shortcuts I tried is using the signs of the dihedral angles in all possible triangulations to determine convexity of the edge in question, but that didn't yield anything useful.
rocket: but like I said above, you could just start with any six points and construct two curves that passes through any two chosen pair of triples. So the curves cannot matter for your original question.
@iq: Thanks for the suggestion.
I also tried something similar, but in 3D the problem is that the sign of the area only depends on the orientation.
So when rotating the points A & B around the axis spanned by P & Q by 180 degrees (in the left figure) would not change the signs of the areas involved but would make the edge non-convex.
Or am I missing something obvious here?
I also tried something similar, but in 3D the problem is that the sign of the area only depends on the orientation.
So when rotating the points A & B around the axis spanned by P & Q by 180 degrees (in the left figure) would not change the signs of the areas involved but would make the edge non-convex.
Or am I missing something obvious here?
Hyde: Yes, you're right about that.
Your brains are FREAKING ME OUT!
DUNGEON HORROR!
lol Gloom, I thought EXACTLY the same. Coding will always remain a mystery to me.
It's been some years since I took my "computational geometry" class at university, so I might be wrong. But I'd google up "convex hulls + half-space intersection" to transform it into a dual plane that allows for easier determination of whether the line segment (p_i, q_j) is on the boundary of the convex hull.
by the way, is this by any chance a school assignment? :-)
iq:
it's true (in 2D at least), and fairly easy to prove. interpret the line pq as a space partition - points to the "left" of the line are in, points to the "right" are out (this is just the orientation test you mentioned). if points end up on both sides of pq, then pq cannot be on the boundary of the convex hull (or any hull at all for that matter) - since it isn't a hull if it doesn't enclose all of the points.
for the reverse direction, it's easiest to work with the definition of the convex hull as intersection of all convex sets containing your pointset S (i'll write ch(S) for the convex hull of S). assume that all points are on one side of pq (say to the left of p->q), so they're in the "left" halfspace of pq. hence the set H of all points in the "nonright" halfspace of pq (meaning either left of pq or on pq) contains all points in S. it's also convex. so ch(S) must be a subset of H; on the other hand, it also contains the points p, q and the line between them, so pq is in ch(S). since pq is on the boundary of H, it must also be on the boundary of ch(S), since ch(S) is a subset of H.
what hyde posted is pretty much the direct generalization of that idea to 3D: the boundary of the convex hull consists of planar faces (instead of lines). you can't tell from the line where the third point is going to come from, but there's only 4 other points left that could be it, so just testing them all in turn seems like a sensible idea.
if you implement that idea directly, that's 4*3 orientation tests, all of which are of the form orient3d(p,q,x,y) with x,y distinct and chosen from the remaining 4 points. you can cut that in half by using that orient3d(p,q,x,y)=-orient3d(p,q,y,x). you end up with 6 orientation tests, which is a pretty small amount of work (i'm fairly certain that constructing the complete convex hull is way more work).
finally, the 3d orientation test for (a,b,c,d) is just the sign of the determinant
since a, b are both constant for all your tests (p and q respectively), there should be a bunch of common terms you can factor out of your computation. if you want to be even more hardcore, use the (mathematically equivalent) sgn(det(q-p,u-p,x_i-p)) which is less work to start with and should also simiplify a bit (since q-p is constant); but that's less numerically stable than evaluating the determinant above directly, which might be a problem.
Quote:
I cannot demonstrate this (so take with care...), and I'm not sure how to extend it to 3D...
it's true (in 2D at least), and fairly easy to prove. interpret the line pq as a space partition - points to the "left" of the line are in, points to the "right" are out (this is just the orientation test you mentioned). if points end up on both sides of pq, then pq cannot be on the boundary of the convex hull (or any hull at all for that matter) - since it isn't a hull if it doesn't enclose all of the points.
for the reverse direction, it's easiest to work with the definition of the convex hull as intersection of all convex sets containing your pointset S (i'll write ch(S) for the convex hull of S). assume that all points are on one side of pq (say to the left of p->q), so they're in the "left" halfspace of pq. hence the set H of all points in the "nonright" halfspace of pq (meaning either left of pq or on pq) contains all points in S. it's also convex. so ch(S) must be a subset of H; on the other hand, it also contains the points p, q and the line between them, so pq is in ch(S). since pq is on the boundary of H, it must also be on the boundary of ch(S), since ch(S) is a subset of H.
what hyde posted is pretty much the direct generalization of that idea to 3D: the boundary of the convex hull consists of planar faces (instead of lines). you can't tell from the line where the third point is going to come from, but there's only 4 other points left that could be it, so just testing them all in turn seems like a sensible idea.
if you implement that idea directly, that's 4*3 orientation tests, all of which are of the form orient3d(p,q,x,y) with x,y distinct and chosen from the remaining 4 points. you can cut that in half by using that orient3d(p,q,x,y)=-orient3d(p,q,y,x). you end up with 6 orientation tests, which is a pretty small amount of work (i'm fairly certain that constructing the complete convex hull is way more work).
finally, the 3d orientation test for (a,b,c,d) is just the sign of the determinant
Code:
|a_x a_y a_z 1|
|b_x b_y b_z 1|
|c_x c_y c_z 1|
|d_x d_y d_z 1|
since a, b are both constant for all your tests (p and q respectively), there should be a bunch of common terms you can factor out of your computation. if you want to be even more hardcore, use the (mathematically equivalent) sgn(det(q-p,u-p,x_i-p)) which is less work to start with and should also simiplify a bit (since q-p is constant); but that's less numerically stable than evaluating the determinant above directly, which might be a problem.
