Point within convex hull of multiple functions

[steveB]

In the mean time, would you say that the rubber sheet stretched out over three points would create a triangular plane surface,

Three points define a plane, so the rubber sheet would be a flat triangle in that plane.

and it over 4 points would create a square surface or perhaps two triangular surfaces?

If 4 points, we need to know if they are all in the same plane. If in the same plane, then stretch a rubber band around them, and this need not be a square surface. If the 4th point is outside the plane defined by the other 3, the balloon will create a solid volume and it would have 4 triangular sides.

Also, if there was a fourth point (with the three that formed a triangular surface) that was a little lower than the first three points, would the rubber sheet reach down to touch the top of that fourth point or would it stay stretched across the three and remain above the fourth (so the fourth was under the sheet, not part of the surface)?

I'm not sure if i understand you, but additional points withing the convex hull of the original 3 will not change the shape of the boundary of the convex hull. If you add points outside the convex hull of the original 3, then the boundary must change to include the new point.

Also, if the sheet touches one point and then extends toward another point, does the sheet follow some natural curve or does it bend at the required angle (making the surface discontinuous) in order to reach the next point?

The sheet must always be convex or straight and can never be concave. The sheet will bend over and around the concave parts of objects and will go straight otherwise.

Another question, can we derive the equation(s) for the sheet from the points?

Sometimes yes, and sometimes no. Even when the answer is yes, it may not be an easy thing to do in many cases.

And in short, would this be the set of equations of surfaces that make up the entire sheet, or is it one continuous surface (derivatives everywhere)?

It is a continuous surface with derivatives well defined. The derivative curves should be continuous usually (but not always, for example around points and corners of objects), and the second (and higher) derivatives won't necessarily be continuous, in general.

 

[steveB]

Mr. Al,

You know, now that I think about it, I'm not sure my balloon idea is correct. As you know, a balloon will find a shape that minimizes the energy. I'm not sure the minimum energy shape of a balloon will always define the convex hull. I can see that in many cases it will, but it may not in all cases. I think the definition using lines is more reliable. Hopefully the balloon idea gives a general picture of what the convex hull is, but it may not be precisely correct.

So, my answers above should be interpreted as what is correct (hopefully) for a convex hull, and not necessarily for a balloon stretch around such objects.

 

[MrAl]

Hello again,

Do you mean like a soap bubble film?

So do we see smooth curves around corners or sharp bends?

For example in 2d curve fitting we try to get a smooth curve to fit the points, but if we can put up with it we can simply draw straight lines between the points and then we have a curve that is only piece wise continuous.

Fitting the curve smoothly is much more difficult and there are several methods to do this. So would we have to do this in 3d for the rubber sheet too or could we just connect the points with straight lines?

What i am trying to determine is how hard it would be to functionalize the sheet. Without a function it's going to be harder to find a quick solution, and with a function it would be harder if the sheet shape was very complex. It sounds like it could be very complex so it will take some tests. The trick then is to find the minimum number of tests needed. If the sheet is functionalized and the objects are functionalized (which i believe they are) then we can find shortcuts based on those types of functions, and this should be possible even if we have to resort to a numerical approach right?
For example, if the sheet created an ellipsoid, then we could probably use the equation for that along with the equation for all the objects.

I had a similar problem when i was working on a 3d drawing program. But there the 'objects' where limited to flat sheets, or rather made up of flat sheets. The task was to find out what sheets were in front of other sheets for proper shading. Part of the solution was to sort the sheets by their distance from the hypothetical observer.
What made this problem simpler though was that the objects although complicated could always be represented by a set of sheets which were always defined the same way in space...as a simple plane. The collection of planes made up the object, and the collection of objects made up the entire drawing.
Looking at it in reverse, if the objects had been solid and complex, perhaps they could have been discretized and each surface handled separately.

I still would like to know if the surface of the sheet has to be completely continuous or not. I am not sure i understood your previous explanation. If at each and every point we are allowed a sharp corner then that makes it easier. If the sheet must fit smoothly then it's like a 3d curve fitting.

 

[steveB]

Mr. Al,

Please check my previous post for a correction.

So do we see smooth curves around corners or sharp bends?.

I think sharp corners because that will form the smallest convex set, it seems to me. The shape needs to be convex and never concave, but there are no restrictions on sharpness/curviness.

For example in 2d curve fitting we try to get a smooth curve to fit the points, but if we can put up with it we can simply draw straight lines between the points and then we have a curve that is only piece wise continuous.

Straight lines are no problem. Remember the line test is using straight lines.

Fitting the curve smoothly is much more difficult and there are several methods to do this. So would we have to do this in 3d for the rubber sheet too or could we just connect the points with straight lines?.

Yes, just connect with straight lines, if it works and obeys the definitions.

What i am trying to determine is how hard it would be to functionalize the sheet. Without a function it's going to be harder to find a quick solution, and with a function it would be harder if the sheet shape was very complex. It sounds like it could be very complex so it will take some tests. The trick then is to find the minimum number of tests needed. If the sheet is functionalized and the objects are functionalized (which i believe they are) then we can find shortcuts based on those types of functions, and this should be possible even if we have to resort to a numerical approach right?
For example, if the sheet created an ellipsoid, then we could probably use the equation for that along with the equation for all the objects.

Yes, it's a difficult problem. Further, the OP seems to be saying that only "within" functions are available to define the shapes. So, the method needs (it would seem) to use these types of functions.

I had a similar problem when i was working on a 3d drawing program. But there the 'objects' where limited to flat sheets, or rather made up of flat sheets. The task was to find out what sheets were in front of other sheets for proper shading. Part of the solution was to sort the sheets by their distance from the hypothetical observer.
What made this problem simpler though was that the objects although complicated could always be represented by a set of sheets which were always defined the same way in space...as a simple plane. The collection of planes made up the object, and the collection of objects made up the entire drawing.
Looking at it in reverse, if the objects had been solid and complex, perhaps they could have been discretized and each surface handled separately.

Yes, that seems to be a simpler problem. Hidden line/object routines are not all that difficult or computationally intensive. Back in the 1970's I wrote my own 3d plotting algorithms that included hidden line/surface ability. Not that these are trivial problems, but they are solvable and even the computational power of the late 1970s could handle it.

I still would like to know if the surface of the sheet has to be completely continuous or not. I am not sure i understood your previous explanation. If at each and every point we are allowed a sharp corner then that makes it easier. If the sheet must fit smoothly then it's like a 3d curve fitting.

The volume defined by the complex hull is generally a solid object with a continuous boundary that encloses an interior. - At least for the problem the OP seems to be dealing with. I'm sure you could find exceptions to this for objects that are lines or points, but for solid objects, I think that is true. Sharp corners are allowed, but I'm not sure how that makes it easier. Keep in mind there is no requirement to fit curves or determine equations of surfaces. One only needs to know if a point is within the hull, or not.

 

[MrAl]

Hello again Steve,

What i was hoping for was to find the equation of the surface(s) and the equation of the object(s) and find the best line in 3d space to calculate the equation for, in short. The length of the line then determines if the object is inside or outside because if the line length is negative then it is outside (for example) but if positive then it is inside.
That's the main idea, but of course i am not sure if this is possible or not here as i dont even know the limitations of the objects yet and there may be three orthogonal lines required for each object and 6 total directions.

By 'soap bubble' i mean the 3d distribution problem where the soap bubble naturally stretches itself over a complex 3d shape, like a wire frame with half circle wire shape at one end with a rectangular base...the soap bubble fits itself over the wire shape where the frame is the boarder of the film.
It sounds like this is much simpler than that, thankfully
If the 'soap bubble' were to stretch across that wire frame, it would look like a sort of curved wedge in 3d space. In the problem of this thread it sounds like it would be just two 2d surfaces connected by a single fold. That makes it a lot easier.

 

[steveB]

My impression is that there are no real limitations on the objects, other than that they are solids defined by a "within" function. I think finding surfaces is difficult, but let's forget about that and see if a solution is possible if the surfaces are definable by some method that would use the "within" function.

So, what line length would you define for the point in question, relative to the surfaces to determine if that point was within the complex hull? How does a line length become positive or negative? I didn't really understand your explanation above.

 

[steveB]

By the way, the soap bubble is completely the wrong idea. Soap films will often form surfaces well within the complex hull. For example, look at the attached picture. The soap bubble on the wire frame spiral is a surface winding around, but the convex hull is a cylinder-like object that contains volume.

The balloon idea is a little better, but I think strictly that is wrong too. Actually, I'm not sure, but my gut feeling is that you can find cases where the balloon does not always match the convex hull.

 

[dougy83]

The hierarchical approach only has a negative approach on efficiency if the line-checking approach is used. As I mentioned, if the line-check approach is used, there is no need for a hierarchical approach. The idea is to find a very efficient method that works for 2 objects (and another for one for single concave objects) and allow that to be expanded to any level. If such an efficient method is not available, then I agree that there is no point to the hierarchy.

For 16 objects, the idea is check 8 pairs, and then form 4 pairs from those 8, and then form 2 pairs from those 4 and then pair the last 2. This is what I mean by 4 pairings. The final pair uses all objects and so would cover the full convex hull. So, in this example, 16 objects are checked individually, then 8 pairs are checked, then 4, then 2 and then 1. So, it's linear with the number of objects and 2N-1 checks are needed for M objects, where N is the next power of two >=M. So, if a method can be found that is 2N-1 times faster or more efficient than the crude line-check method, one can think about this type of approach.

I do not understand how you check if a point is within the hull of twice-paired objects any more efficiently. I assumed you were recommending using the line method to check for a point within the pairs; I don't know how you're doing it now.

Are you stating that you have a number of 3d objects, and that each and every object has convex hulls.

Hi MrAl. A hull can exist for every object, which will simply be the object in the case of a convex object; for a concave object, the convex hull has a large volume. I want to quickly find if a point is within the convex hull of multiple objects. The hull is the volume that contains all the objects, and has the property shown in the first post, as well as any point in the hull being either in an object or able to have a line intersect two objects and the point.

Second, when you say "convex hull" do you mean a slice of a sphere, where the curved part is spherical and the 'underside' is flat, or could the 'underside' be a spherical surface too? And if it can be spherical, can it be oriented inward only or possibly either inward or outward?
So if it was flat the inner space could be defined as the space between a sphere and a plane, and if curved it could be defined as the space between the intersection of two spheres. If two spheres, one may be oriented outward and one inward, or both inward, or both outward?
When i say "sphere" i mean the shape is defined by the equation for a sphere. When i say "plane" i mean a 2d plane oriented in 3d space, so it can 'cut' the sphere into two sections.

The convex hull of a sphere is the sphere surface, the volume within the hull of two spheres will include that of the two sphere, in addition to the frustum between them. Here are some examples:
--> -->

In the mean time, would you say that the rubber sheet stretched out over three points would create a triangular plane surface, and it over 4 points would create a square surface or perhaps two triangular surfaces?

Three points, provided they are not co-linear, will have a triangular hull, with zero volume.

Also, if there was a fourth point (with the three that formed a triangular surface) that was a little lower than the first three points, would the rubber sheet reach down to touch the top of that fourth point or would it stay stretched across the three and remain above the fourth (so the fourth was under the sheet, not part of the surface)?

Four points, if not co-planar, will form a tetrahedron. If coplanar (but not co-linear), they will a three- or four-sided planar shape, with no volume. If co-linear, they will form a line, again with zero volume. All of the objects I am caring about will have volume, so all hulls will have volume.

Also, if the sheet touches one point and then extends toward another point, does the sheet follow some natural curve or does it bend at the required angle (making the surface discontinuous) in order to reach the next point?

The balloon will have the extremal points forming its vertices. Any points that aren't extremal will not lie on the surface of the hull, but within its enclosed volume. The surface will be continuous.

 

[MrAl]

Hello again,

When i said "soap bubble" and on a wire frame, i meant a wire frame that i get to choose, not some arbitrary frame. That was necessary for the question. In other words, a comparison between a wire frame where the soap bubble would create a shape where there were points outside any straight line between any two maximums of the wire frame. But now that i think about it and see the drawings, i think this may be unavoidable. I used the soap bubble idea because it is a minimal surface and so would stretch across any voids between pieces. And for these problems we wont have wire frames, we will have solid frames according to the pictures. The 'balloon' would just reduce the freedom of the 'soap bubble' that would restrict it more so i agree that it makes sense.

But enough about soap bubbles
From the pictures i can see that it is starting to look like we are working with generated surfaces where the more complex surfaces are generated from simpler surfaces (objects) that are translated or rotated in space, which forms the hull. So now i think another question.

Forming hulls:
If we take a sphere and translated it along the x axis it creates a pipe with rounded and closed ends.
If we take a cube and translated the same way we get a parallelepiped that has closed ends.
If we take a sphere on the x axis and another sphere on the x axis, we have to connect them using tangents (as per drawing) or alternately generate the surface by simultaneously translating and inflating the smaller sphere.
True or not true?

More complex hull:
If we take a sphere on the x axis not at zero, and rotate it about the y axis, we create a toroid. We might never do this, but if we did would the hull be a doughnut or a cookie?
If we took several spheres and arranged them in a circle so they formed a discretized looking doughnut, we would then connect all the spheres together with straight line tangents (an infinite set) or simply translate each toward the other, but most importantly would this hull look more like the doughnut or more like the cookie (with straight sides)?

One more complex hull:
If we take a sphere on the x axis not at zero and rotate it only 120 degrees about y, does it create a boomerang hull or a half cookie hull?

It appears now that the hull is generated by a surface that is 'morphed' from one simple object to the next. So we end up with surfaces of rotation, of translation, etc. Alternately, any voids must be joined also but i need your feedback to determine this.

The soap bubble (or balloon) on a wire frame that has one curved part and one square part, the two parts in two different orthogonal planes.
This represents a special problem where we have to morph from one type of object to another. For example, from a sphere to a cube.
Is this type of hull allowed too or will it always be one or the other ?

As to lengths positive or negative:
If one surface is above the other and not touching, all lines through both surfaces will have positive length because all y1 will be greater than all y2 if we calculate the distance between the two with y1-y2. If the two surfaces coincide anywhere then at least one line will show a distance which is negative.
But i still need more information here.

As to the basics:
Are you generating the hulls from the objects or are they already generated?
Can i ask what you are going to use this for, as to the practical end application?

 

[steveB]

I do not understand how you check if a point is within the hull of twice-paired objects any more efficiently. I assumed you were recommending using the line method to check for a point within the pairs; I don't know how you're doing it now.

As I tried to explain above, a few times, I don't have a method for checking if the point is in the convex hull of paired objects. I mentioned the line check method, which does not benefit from the pairing hierarchy, as we have discovered as we go through this brainstorming process. The idea of the pairing hierarchy provided motivation to try and find a method that works for paired objects; the idea being that it might be easier to find a fast and efficient method for 2 objects more easily than the general case for any number of objects. Assuming you can find such a method and assuming the method does not automatically generalize to more than 2 objects, the pairing hierarchy would enable you to use the more efficient method.

I've been trying to think of a method that works for 2 objects efficiently, but have not been able to find one. Hence, this may be a dead end path in our brainstorming.

 

[dougy83]

Forming hulls:...

The hull of a toroid is the toroid with a flat top and bottom (no hole, or concave parts are allowed in a convex hull). The six-sphere arrangement forms the following hull (hull on left, original objects on right):

The 120 degree rotation of the sphere will cut a boomerang shape; the convex hull of it will also include the end points (the chord of the arc).

I guess the morphing between shapes will cut the hull. The interpolation will have to be between each shape and every other, I assume.
Convex hulls exist for every set of objects, regardless of their shape.
The application is CSG, similar to OpenSCAD.

As I tried to explain above, a few times, I don't have a method for checking if the point is in the convex hull of paired objects. I mentioned the line check method, which does not benefit from the pairing hierarchy, as we have discovered as we go through this brainstorming process. The idea of the pairing hierarchy provided motivation to try and find a method that works for paired objects; the idea being that it might be easier to find a fast and efficient method for 2 objects more easily than the general case for any number of objects. Assuming you can find such a method and assuming the method does not automatically generalize to more than 2 objects, the pairing hierarchy would enable you to use the more efficient method.

Ah, ok. Yes, I can't think of any method for checking the hull of paired objects, as the hull is never explicitly defined, and both objects in the pairing have to be checked.

 

[steveB]

Continuing with the brainstorming ...

Here is a potential idea for checking if a point is in the convex hull of two objects. I know this is not rigorous, but it might provide a method that works often enough and approximately enough, and it might be significantly more efficient than the line check method.

Imagine two objects A and B, each defined by their own "within" function. The first step is always to check if the point P is within either object, as we know, because this is a quick check and if the point is within at least one object, then there is no need to do further checking.

Now, after you check if the object is within A or B with the within(A)+within(B) function, move the two objects towards each other by a small amount and check to see if the point P is now within either object and set a flag to indicate if the point is ever in A, and another flag is set if you are ever in B. Once a flag is set for A, there is no need to move and check object A any more, and likewise for object B. If the flag is never set, let each object pass well past the point to make sure you sweep out the volume completely. The idea is that as the two objects are moved towards each other, they will automatically sweep through the bulk of the convex hull volume, and the checking can be done with the "within" functions you already have. If the point is ever in both A and B at some point in the process (i.e. if both flags become set), the point is very likely to be in the convex hull, or at least nearly so.

Your first question will be, "how do I know exactly which direction to move the objects so that they are going towards each other accurately?" and that indeed is the real problem to solve with this method. Hence, in addition to the "within" function, we need some way of estimating approximate locations and centers of volume for A and B so that the line that connects the centers of A and B can be established.

I think that at first you will not like this method, but what I would like you to consider is that this method might actually work well for objects that are very far apart in space, and these are the situations that are particularly challenging for the line method.

You can also consider using this method in a different way, - basically as a first pass check. If you use this algorithm and neither flag is set, then you can be sure that the object is not in the convex hull, and you have again eliminated the situations that will be most time consuming for the line method. If one flag is set and not the other, the object could still be in the convex hull, particularly if the objects are close together to begin with. However, you will now have a more confined set of lines to check with the line method.

Basically, I'm suggesting that using multiple methods might provide an overall more efficient method.

 

[MrAl]

Hello again,

From post #31, what do you mean the hull is never explicitly defined? Then how do you ever know where a point is on its surface?
If you are saying that the hull is a ghost where we only know the objects inside and their positions, then you'll have to find a way to define the hull from those objects right?

My basic idea was going to be that if you can define the hull as a collection of simple 3d objects (such as sphere, cube, etc.) and there was never any part that was concave, then we can tell if a point is within the hull with a single 3d line test. If we draw a 3d line in any direction through the point in question p(x,y,z) then the line intersects the hull at two points p1 and p2, and using the signed distances between p and p1 and between p and p2, if the signs of the distances are the same then the point is outside of the hull, but if the signs are opposite (one plus and one minus) then the point is inside the hull.
So basically we are using the ideas of space analytic geometry.

The complications arise if the hull can be too complicated, but if it is very complicated then i cant see how you would generate it anyway without knowing where it is in space. At some point i would think you would have to generate it, and this would require functions. Alternately, if that's not happening yet but you can do it, then perhaps simply connected simple 3d objects can be used.
For your example of two spheres of different size, perhaps you can use two partial spheres and one conic to connect the two.
Isnt there any theory on how to join objects out there?

 

[dougy83]

Now, after you check if the object is within A or B with the within(A)+within(B) function, move the two objects towards each other by a small amount and check to see if the point P is now within either object and set a flag to indicate if the point is ever in A, and another flag is set if you are ever in B. Once a flag is set for A, there is no need to move and check object A any more, and likewise for object B. If the flag is never set, let each object pass well past the point to make sure you sweep out the volume completely. The idea is that as the two objects are moved towards each other, they will automatically sweep through the bulk of the convex hull volume, and the checking can be done with the "within" functions you already have. If the point is ever in both A and B at some point in the process (i.e. if both flags become set), the point is very likely to be in the convex hull, or at least nearly so.

Yes, if the point is in the intersection of the two test objects projected along the line between their centres-of-mass, then for regular solids, this will tell you if the point is definitely within the hull; it doesn't cover much of the hull volume for different sized shapes, however. e.g. for two separated spheres, of radius 1 and 3, the method outlined will include roughly the centre 33% of the volume of the actual hull. For non-spherical dissimilar shapes, this can be worse. For identical objects, the method is exact if using infinitesimal step.

To include more of the hull in the inexact check, using a combination of your method and MrAl's, one could adjust the cross-sectional size of objects as they approach each other by a scale transform of the test point (scaling requires 3 multiplications). This would increase the size of a smaller object, while decreasing the size of a larger object, as they approach each other's original position.

A similar, but faster (and potentially less accuarate for non-spherical objects) would be to test the region between the objects using a frustum between the centres of their bounding spheres, with end radii equal to that of the bounding spheres. This is exact for sphere hulls, but overestimates (possibly grossly) for any other shape.

Basically, I'm suggesting that using multiple methods might provide an overall more efficient method.

Yes, it may be better to use a number of special-case methods wherever they are best suited. I think the iteratively-refined plane check method is the most general (and quite quick once the planes have been calculated initially).

From post #31, what do you mean the hull is never explicitly defined? Then how do you ever know where a point is on its surface?

Only the objects within the hull are defined, and the hull is implied from these objects.

If you are saying that the hull is a ghost where we only know the objects inside and their positions, then you'll have to find a way to define the hull from those objects right?

Yes, but you may have a lot of trouble defining the surface of the hull, as it can be extremely complex. Even the hull of a box and a sphere is hard (for me) to explain analytically.

If we draw a 3d line in any direction through the point in question p(x,y,z) then the line intersects the hull at two points p1 and p2, and using the signed distances between p and p1 and between p and p2, if the signs of the distances are the same then the point is outside of the hull, but if the signs are opposite (one plus and one minus) then the point is inside the hull.

Unfortunately the hull is not explicitly defined, and therefore to do this line check, you'd have to check if points on the line are inside or outside the hull (which is the problem we are trying to solve in the first instance).

For your example of two spheres of different size, perhaps you can use two partial spheres and one conic to connect the two.
Isnt there any theory on how to join objects out there?

The 'conic' section is a frustum. The only theory I could find is the equation shown in the first post. Solving this equation is not an issue, except that the accuracy depends on the number of extremal points used to approximate the hull, and the solution takes a while to compute.

 

[MrAl]

[Hull implicit]
Only the objects within the hull are defined, and the hull is implied from these objects.

[Defining the hull]
Yes, but you may have a lot of trouble defining the surface of the hull, as it can be extremely complex. Even the hull of a box and a sphere is hard (for me) to explain analytically.

Hello again,

Ok now we are getting down to the brass tacks

The cube and sphere question i asked was similar to the soap bubble question where the wire frame i chose had a half round section joined to a rectangular section where the two resulting surfaces are 90 degrees apart.
The solution to this surface is defined by a partial differential equation, but unfortunately i feel that may be too complicated for what you are trying to do. Also unfortunate is that without the surface it could take many tests to determine what is where.

Looking at it in with a full blown view of what it would take without defining the surface, if we look at two simple objects to start with the extremes can be joined with an infinite set of lines. If a third object is then introduced, we would have to connect the third object to the now joined pair with another set of infinite lines, going from the extremes of the pair to the extremes of the new object.
This can get pretty hairy and that's just for simple objects
If we had a complex object (boomerang) then we'd have to connect all the extremes to all the other extremes in an organized way in order to get the 3d envelope.

Because of the complexity i think it will be necessary to discretize the objects in some way, or alternately, limit the allowed shape of any given single object or have it constructed from simpler objects such as spheres ie objects that can be joined without requiring complicated equations.

For example, if we had a cube 1x1x1 and sphere radius 0.5, and we discretize by 1x1x1, we would draw four lines from the corners of the cube to the sphere, and this would form a volume enclosing a region of space that had the shape of a rectangular pipe of sorts. We could then use an equation to determine if the point was inside that space, or (first) check the cube and the sphere and then check this new region. If it was in the cube we're done, if it was in the sphere we're done, but if not then we have to look in the new region.
That obviously is not an exact method, because we used 1x1x1 as the dx,dy,dz step, so that will lead to a certain accuracy limit. Using smaller steps will get us more accuracy, but will require a more complicated region. It is also possible that intrinsic coordinates may help here.

If we instead limit the allowed shapes of the objects they will be easier to connect, and the equations can probably be generalized into a smaller set.

In closing, it appears to me that the only true exact solution is to define the surfaces that join the objects and using those equations determine if the point is inside from the solution set. Since this can get quite complicated (partial differential equations required for various unusual shapes) and will probably end up having to be solved numerically anyway, we look for approximate solutions. The approximate solutions can take the form of an entire distretization of the space and/or objects, or in the form of a constraint placed on any single object.