All of these posts seem to be forgetting that if a point is on a plane, I can't find this out - depending on how the rounding happens to come out, there's a 50% chance of it being flagged as on one side of the plane and a 50% chance of it being flagged as on the other side, but a 0% chance of it being flagged as on the plane. I had thought about a system using the midpoints of edges, but the midpoints of all edges are on planes, and therefore have a good chance of being flagged as inside the volume.
I'll try and address things one point at a time:
Why do you need to delete the line?
Another function that needs to be run on the volume afterwards will fail if it is ill-formed.
Why do you need to add the second shape to the first?
The first shape represents a portion of the view frustum. The second represents the space between it and the sun. Together, they represent the volume which shadow casters can occupy.
Can you calculate if a point is inside the whole shape?
I can do this with a 50% false positive rate for things on the border, but all of the edges I want to keep are on the border, so half of those would be removed.
Can you form triangles from sets of points and calculate their norm? Can you calculate if a point on that norm (that is infinitely close to the triangle but not in the plane of the triangle itself) is inside the shape?
That's not terminology I recognise, but when I see the word close, my default response is going to be that the results will be wrong 50% of the time.
This is challenging to describe but here goes. Imagine you were holding this wireframe shape in your hands. Now you can look at it from all different directions. Now pick an edge, E, and look directly along it so that it becomes a point. In other words, project the wireframe onto a plane where the edge E is orthogonal to that plane.
If you're still with me and can picture this, then I think you might see a point in the middle, which is E, and number of connecting edges going off in different directions. What I think is relevant are the angles between these connecting edges. If you cannot find an angle greater than or equal to 180, then I would imagine that this edge must travel through the interior of the convex hull.
So I project everything into 2D, looking along an edge, work out the bearing of each of its neighbours, and check at least one of the gaps is above 180°? This actually seems like it might be viable. It's like a few other ideas I had, but I'm not seeing any of the pitfalls, and it passes my 'stab some cocktail sticks into an eraser and see if it works' test. I shall conduct further testing.
A line segment is not an edge of a polyhedron/volume, if its midpoint (or any other point besides the end points) is inside the polyhedron, or conversely, it is an edge of the polyhedron, if its midpoint is on the boundary of the polyhedron.
From this, it looks to me, that an unoptimized algorithm for you problem seems to be:
1. Ignore the edge data you are given and just take all vertices of all edges and create from this a data structure from which you can easily deside (strict) containment in the convex hull.
2. Test for each edge, if the midpoint is inside the convex hull and not on the boundary.
Due to rounding errors, I can't test if something is on
the boundary - it's either on one side or the other, and things close to the boundary have a 50% chance of registering as on either side. That breaks this. It's something I've already tried.
Another idea is to find at each vertex the set of line segments which form edges in the polyhedron. This is probably slower than the previous approach, but might be more in line of what you were thinking about.
For each vertex v:
1. Generate the list of all edges, which are incident to v
2. Find a plane through v which does not contain any of the edges and move it inside the polytope. (You can take the average of the directions of all edges to find a normal vector for such a plane)
3. Intersect all rays starting in v and formed by the edge directions with the plane. Now find the intersections, which form the convex hull. All other come from edges, which are inside the polyhedron.
This is another thing I'd already thought of, but sliding the plane is where it fails - the scale of input the data can change by many orders of magnitude, even for one volume (parts of the added volume use -DBL_MAX and the original volume can sometimes range between 0.9998 and 0.9999). If the plane is slid far enough to soak up the rounding error for the big numbers, it also soaks up the whole range of the small numbers.
Picking a plane normal is also harder than just taking the average - if there are enough edges in one direction, the plane will face that direction, which is only acceptable if lines are constrained to 90°. A good normal is the average of just the minimum and maximum edges in an orthogonal plane, and then everything starts to get circular, with things requiring their own results to exist before they can be computed.
I'm going to try a prototype of PatDaRat's solution as it's the only thing to pass both the 'stab some cocktail sticks into an eraser and see if it works' test and the 'doesn't require testing against planes' test.