One way to identify the exterior shell of your set of points (so we're assuming there are not any 'holes' that should be considered exterior to the volume).

a) Identify a point on the exterior of the line set.

b) Walk around the exterior of the line set till you get back to start.

This identifies all the lines required to define the exterior; and then ones that you can remove are all those not belonging to the exterior.

For a) you can choose the lexicographically minimal point (a, b) < (c, d) iff a < c || (a == c &amp;&amp; b < d)

For b) you need to be able to; from any given point of the exterior identify the next point of the exterior. This comes in two cases; the initial case where you have 2 exterior lines to choose and you have to pick one of them (for this, abuse that your start point is lexicographically minimal), and in the other case you can make use of the point of the exterior you have just came from to order the outgoing edges.

Presume that we choose, as a result of the first case of b) the point that is clockwise around the exterior (We'll come back to this after).

If you label the previous point 'p' and the current point 'c'; then you can order the outgoing edges based on their relative rotation from the vector (c - p) http://www.zimagez.com/zimage/screenshot-021212-223758.php here, we want to pick vertex v0.

We can do this by computing the perp-dot products of (v[i] - c) with (c - p) normalised by the length of (v[i] - c); and choosing the minimal (or maximal depending on coordinate system); since the perp-dot of two vectors u,v is |u||v|sin(theta). We can also avoid any division if sorting of the outgoing edges uses a comparison function instead of a key.

Back to the first case of b); choosing the second vertex of exterior we can use the same technique, and use the vector (1, 0) instead of (c - p) above. This is valid given that our first vertex was lexicographically minimal since the clockwise direction of the next vertex can in the worst case be in the direction (1, 0) and there cannot exist any vertex of the set that would give us a 'negative' perp-dot since that point would need to have a lower y-coordinate and would have been chosen as the lexicographically minimal one.

^^ this is very similar to gift wrapping algorithm for computing a convex hull and is exactly equivalent if we join every vertex to every other one using this algorithm.

### Show differencesHistory of post edits

### #4luca-deltodesco

Posted 02 December 2012 - 04:48 PM

One way to identify the exterior shell of your set of points (so we're assuming there are not any 'holes' that should be considered exterior to the volume).

a) Identify a point on the exterior of the line set.

b) Walk around the exterior of the line set till you get back to start.

This identifies all the lines required to define the exterior; and then ones that you can remove are all those not belonging to the exterior.

For a) you can choose the lexicographically minimal point (a, b) < (c, d) iff a < c || (a == c &amp;&amp; b < d)

For b) you need to be able to; from any given point of the exterior identify the next point of the exterior. This comes in two cases; the initial case where you have 2 exterior lines to choose and you have to pick one of them (for this, abuse that your start point is lexicographically minimal), and in the other case you can make use of the point of the exterior you have just came from to order the outgoing edges.

Presume that we choose, as a result of the first case of b) the point that is clockwise around the exterior (We'll come back to this after).

If you label the previous point 'p' and the current point 'c'; then you can order the outgoing edges based on their relative rotation from the vector (c - p) http://www.zimagez.com/zimage/screenshot-021212-223758.php here, we want to pick vertex v0.

We can do this by computing the perp-dot products of (v[i] - c) with (c - p) normalised by the length of (v[i] - c); and choosing the minimal (or maximal depending on coordinate system); since the perp-dot of two vectors u,v is |u||v|sin(theta). We can also avoid any division if sorting of the outgoing edges uses a comparison function instead of a key.

Back to the first case of b); choosing the second vertex of exterior we can use the same technique, and use the vector (1, 0) instead of (c - p) above. This is valid given that our first vertex was lexicographically minimal since the clockwise direction of the next vertex can in the worst case be in the direction (1, 0) and there cannot exist any vertex of the set that would give us a 'negative' perp-dot since that point would need to have a lower y-coordinate and would have been chosen as the lexicographically minimal one.

^^ this is very similar to gift wrapping algorithm for computing a convex hull and is exactly equivalent if we join every vertex to every other one using this algorithm.

a) Identify a point on the exterior of the line set.

b) Walk around the exterior of the line set till you get back to start.

This identifies all the lines required to define the exterior; and then ones that you can remove are all those not belonging to the exterior.

For a) you can choose the lexicographically minimal point (a, b) < (c, d) iff a < c || (a == c &amp;&amp; b < d)

For b) you need to be able to; from any given point of the exterior identify the next point of the exterior. This comes in two cases; the initial case where you have 2 exterior lines to choose and you have to pick one of them (for this, abuse that your start point is lexicographically minimal), and in the other case you can make use of the point of the exterior you have just came from to order the outgoing edges.

Presume that we choose, as a result of the first case of b) the point that is clockwise around the exterior (We'll come back to this after).

If you label the previous point 'p' and the current point 'c'; then you can order the outgoing edges based on their relative rotation from the vector (c - p) http://www.zimagez.com/zimage/screenshot-021212-223758.php here, we want to pick vertex v0.

We can do this by computing the perp-dot products of (v[i] - c) with (c - p) normalised by the length of (v[i] - c); and choosing the minimal (or maximal depending on coordinate system); since the perp-dot of two vectors u,v is |u||v|sin(theta). We can also avoid any division if sorting of the outgoing edges uses a comparison function instead of a key.

Back to the first case of b); choosing the second vertex of exterior we can use the same technique, and use the vector (1, 0) instead of (c - p) above. This is valid given that our first vertex was lexicographically minimal since the clockwise direction of the next vertex can in the worst case be in the direction (1, 0) and there cannot exist any vertex of the set that would give us a 'negative' perp-dot since that point would need to have a lower y-coordinate and would have been chosen as the lexicographically minimal one.

^^ this is very similar to gift wrapping algorithm for computing a convex hull and is exactly equivalent if we join every vertex to every other one using this algorithm.

### #3luca-deltodesco

Posted 02 December 2012 - 04:46 PM

One way to identify the exterior shell of your set of points (so we're assuming there are not any 'holes' that should be considered exterior to the volume).

a) Identify a point on the exterior of the line set.

b) Walk around the exterior of the line set till you get back to start.

This identifies all the lines required to define the exterior; and then ones that you can remove are all those not belonging to the exterior.

For a) you can choose the lexicographically minimal point (a, b) < (c, d) iff a < c || (a == c && b < d)

For b) you need to be able to; from any given point of the exterior identify the next point of the exterior. This comes in two cases; the initial case where you have 2 exterior lines to choose and you have to pick one of them (for this, abuse that your start point is lexicographically minimal), and in the other case you can make use of the point of the exterior you have just came from to order the outgoing edges.

Presume that we choose, as a result of the first case of b) the point that is clockwise around the exterior (We'll come back to this after).

If you label the previous point 'p' and the current point 'c'; then you can order the outgoing edges based on their relative rotation from the vector (c - p) http://www.zimagez.com/zimage/screenshot-021212-223758.php here, we want to pick vertex v0.

We can do this by computing the perp-dot products of (v[i] - c) with (c - p) normalised by the length of (v[i] - c); and choosing the minimal (or maximal depending on coordinate system); since the perp-dot of two vectors u,v is |u||v|sin(theta). We can also avoid any division if sorting of the outgoing edges uses a comparison function instead of a key.

Back to the first case of b); choosing the second vertex of exterior we can use the same technique, and use the vector (1, 0) instead of (c - p) above. This is valid given that our first vertex was lexicographically minimal since the clockwise direction of the next vertex can in the worst case be in the direction (1, 0) and there cannot exist any vertex of the set that would give us a 'negative' perp-dot since that point would need to have a lower y-coordinate and would have been chosen as the lexicographically minimal one.

a) Identify a point on the exterior of the line set.

b) Walk around the exterior of the line set till you get back to start.

This identifies all the lines required to define the exterior; and then ones that you can remove are all those not belonging to the exterior.

For a) you can choose the lexicographically minimal point (a, b) < (c, d) iff a < c || (a == c && b < d)

For b) you need to be able to; from any given point of the exterior identify the next point of the exterior. This comes in two cases; the initial case where you have 2 exterior lines to choose and you have to pick one of them (for this, abuse that your start point is lexicographically minimal), and in the other case you can make use of the point of the exterior you have just came from to order the outgoing edges.

Presume that we choose, as a result of the first case of b) the point that is clockwise around the exterior (We'll come back to this after).

If you label the previous point 'p' and the current point 'c'; then you can order the outgoing edges based on their relative rotation from the vector (c - p) http://www.zimagez.com/zimage/screenshot-021212-223758.php here, we want to pick vertex v0.

We can do this by computing the perp-dot products of (v[i] - c) with (c - p) normalised by the length of (v[i] - c); and choosing the minimal (or maximal depending on coordinate system); since the perp-dot of two vectors u,v is |u||v|sin(theta). We can also avoid any division if sorting of the outgoing edges uses a comparison function instead of a key.

Back to the first case of b); choosing the second vertex of exterior we can use the same technique, and use the vector (1, 0) instead of (c - p) above. This is valid given that our first vertex was lexicographically minimal since the clockwise direction of the next vertex can in the worst case be in the direction (1, 0) and there cannot exist any vertex of the set that would give us a 'negative' perp-dot since that point would need to have a lower y-coordinate and would have been chosen as the lexicographically minimal one.

### #2luca-deltodesco

Posted 02 December 2012 - 04:45 PM

One way to identify the exterior shell of your set of points (so we're assuming there are not any 'holes' that should be considered exterior to the volume).

a) Identify a point on the exterior of the line set.

b) Walk around the exterior of the line set till you get back to start.

This identifies all the lines required to define the exterior; and then ones that you can remove are all those not belonging to the exterior.

For a) you can choose the lexicographically minimal point (a, b) < (c, d) iff a < c || (a == c && b < d)

For b) you need to be able to; from any given point of the exterior identify the next point of the exterior. This comes in two cases; the initial case where you have 2 exterior lines to choose and you have to pick one of them (for this, abuse that your start point is lexicographically minimal), and in the other case you can make use of the point of the exterior you have just came from to order the outgoing edges.

Presume that we choose, as a result of the first case of b) the point that is clockwise around the exterior (We'll come back to this after).

If you label the previous point 'p' and the current point 'c'; then you can order the outgoing edges based on their relative rotation from the vector (c - p) http://www.zimagez.com/zimage/screenshot-021212-223758.php here, we want to pick vertex v0.

We can do this by computing the perp-dot products of (v[i] - c) with (c - p) normalised by the length of (v[i] - c); and choosing the minimal (or maximal depending on coordinate system); since the perp-dot of two vectors u,v is |u||v|sin(theta). We can also avoid any division if sorting of the outgoing edges uses a comparison function instead of a key.

Back to the first case of b); choosing the second vertex of exterior we can use the same technique, and use the vector (1, 0) instead of (c - p) above. This is valid given that our first vertex was lexicographically minimal since the clockwise direction of the next vertex can in the worst case be in the direction (1, 0) and there cannot exist any vertex of the set that would give us a 'negative' perp-dot since that point would need to have a lower y-coordinate and would have been chosen as the lexicographically minimal one.

a) Identify a point on the exterior of the line set.

b) Walk around the exterior of the line set till you get back to start.

This identifies all the lines required to define the exterior; and then ones that you can remove are all those not belonging to the exterior.

For a) you can choose the lexicographically minimal point (a, b) < (c, d) iff a < c || (a == c && b < d)

For b) you need to be able to; from any given point of the exterior identify the next point of the exterior. This comes in two cases; the initial case where you have 2 exterior lines to choose and you have to pick one of them (for this, abuse that your start point is lexicographically minimal), and in the other case you can make use of the point of the exterior you have just came from to order the outgoing edges.

Presume that we choose, as a result of the first case of b) the point that is clockwise around the exterior (We'll come back to this after).

If you label the previous point 'p' and the current point 'c'; then you can order the outgoing edges based on their relative rotation from the vector (c - p) http://www.zimagez.com/zimage/screenshot-021212-223758.php here, we want to pick vertex v0.

We can do this by computing the perp-dot products of (v[i] - c) with (c - p) normalised by the length of (v[i] - c); and choosing the minimal (or maximal depending on coordinate system); since the perp-dot of two vectors u,v is |u||v|sin(theta). We can also avoid any division if sorting of the outgoing edges uses a comparison function instead of a key.

Back to the first case of b); choosing the second vertex of exterior we can use the same technique, and use the vector (1, 0) instead of (c - p) above. This is valid given that our first vertex was lexicographically minimal since the clockwise direction of the next vertex can in the worst case be in the direction (1, 0) and there cannot exist any vertex of the set that would give us a 'negative' perp-dot since that point would need to have a lower y-coordinate and would have been chosen as the lexicographically minimal one.

### #1luca-deltodesco

Posted 02 December 2012 - 04:44 PM

Well one way could be to:

a) Identify a point on the exterior of the line set.

b) Walk around the exterior of the line set till you get back to start.

This identifies all the lines required to define the exterior; and then ones that you can remove are all those not belonging to the exterior.

For a) you can choose the lexicographically minimal point (a, b) < (c, d) iff a < c || (a == c && b < d)

For b) you need to be able to; from any given point of the exterior identify the next point of the exterior. This comes in two cases; the initial case where you have 2 exterior lines to choose and you have to pick one of them (for this, abuse that your start point is lexicographically minimal), and in the other case you can make use of the point of the exterior you have just came from to order the outgoing edges.

Presume that we choose, as a result of the first case of b) the point that is clockwise around the exterior (We'll come back to this after).

If you label the previous point 'p' and the current point 'c'; then you can order the outgoing edges based on their relative rotation from the vector (c - p) http://www.zimagez.com/zimage/screenshot-021212-223758.php here, we want to pick vertex v0.

We can do this by computing the perp-dot products of (v[i] - c) with (c - p) normalised by the length of (v[i] - c); and choosing the minimal (or maximal depending on coordinate system); since the perp-dot of two vectors u,v is |u||v|sin(theta). We can also avoid any division if sorting of the outgoing edges uses a comparison function instead of a key.

Back to the first case of b); choosing the second vertex of exterior we can use the same technique, and use the vector (1, 0) instead of (c - p) above. This is valid given that our first vertex was lexicographically minimal since the clockwise direction of the next vertex can in the worst case be in the direction (1, 0) and there cannot exist any vertex of the set that would give us a 'negative' perp-dot since that point would need to have a lower y-coordinate and would have been chosen as the lexicographically minimal one.

a) Identify a point on the exterior of the line set.

b) Walk around the exterior of the line set till you get back to start.

This identifies all the lines required to define the exterior; and then ones that you can remove are all those not belonging to the exterior.

For a) you can choose the lexicographically minimal point (a, b) < (c, d) iff a < c || (a == c && b < d)

For b) you need to be able to; from any given point of the exterior identify the next point of the exterior. This comes in two cases; the initial case where you have 2 exterior lines to choose and you have to pick one of them (for this, abuse that your start point is lexicographically minimal), and in the other case you can make use of the point of the exterior you have just came from to order the outgoing edges.

Presume that we choose, as a result of the first case of b) the point that is clockwise around the exterior (We'll come back to this after).

If you label the previous point 'p' and the current point 'c'; then you can order the outgoing edges based on their relative rotation from the vector (c - p) http://www.zimagez.com/zimage/screenshot-021212-223758.php here, we want to pick vertex v0.

We can do this by computing the perp-dot products of (v[i] - c) with (c - p) normalised by the length of (v[i] - c); and choosing the minimal (or maximal depending on coordinate system); since the perp-dot of two vectors u,v is |u||v|sin(theta). We can also avoid any division if sorting of the outgoing edges uses a comparison function instead of a key.

Back to the first case of b); choosing the second vertex of exterior we can use the same technique, and use the vector (1, 0) instead of (c - p) above. This is valid given that our first vertex was lexicographically minimal since the clockwise direction of the next vertex can in the worst case be in the direction (1, 0) and there cannot exist any vertex of the set that would give us a 'negative' perp-dot since that point would need to have a lower y-coordinate and would have been chosen as the lexicographically minimal one.