[postgis-devel] Polyhedral, 3d and distance

Nicklas Avén nicklas.aven at jordogskog.no
Tue Aug 10 01:31:40 PDT 2010


Hallo Olivier

> Hi Nicklas,
> 
> > This polyhedral thing is really interesting. I have been thinking  
> > about the distance-functions against 3D.
> > The word polyhedral is new to me and I don't know more about it than  
> > what Olivier has written in his post.
> 
> Well it's just a collection of connected polygons.
> They could be either 2D, or 3D.
> 
> And if they are 3D, they could also lead to enclose a solid.
> (a cube for instance).
> 
> 
> > I have a few questions:
> >
> > Olivier, in your post in January
> > http://postgis.refractions.net/pipermail/postgis-devel/2010-January/008384.html
> > you say that :
> >
> > resulting PolyhedralSurface must be convex (and without hole)
> >
> > is that a logical limitation or a limitation in the standard.
> > I mean if the resulting geometry has to be convex it will be hard to  
> > describe things like the land shape, a mountain a valley etc.
> 
> I was wrong on this point, the convex aspect is not (at all) required  
> by the spec.
> 

Ok, but maybe as you comment yourself maybe TIN is a better choice for
land shape and aim on polyhedral use for buildings. 

I think assumptions like that should affect our strategy quite a lot.
Because if so the polyhedral cases will be quite simple mostly with
horizontal and and vertical walls. 

Then there might also be no gain in searching for shortcuts in
distance-calculations because most polyhedral geometries will only have
4 walls and each wall containing 4 corners. In that case I think the
overhead cost to do precalculations might be bigger than the gain. But
if we aim on usage with big and complex polygons and a lot of faces,
then there might be interesting approaches. 

I think we then should load the geometries into special structures
before doing the calculations. In the structure there should be the
plane defined in a solid way. Like three representive points or by an
equation. So we don't have to deal with that problem many times in te
same calculation. The structure should also contain the 3d bounding box
and maybe the center of it. Then I think we have a good start for
finding shortcuts in the calculations. 


> > as described in the post above:
> > every polygon mean a face (with all points on the same plan...
> >
> > As I understand it (I like to add that so it hurts a little less  
> > when I'm wrong), a plane can be defined
> > by 3 points. But what when we have 4 or more points. There are  
> > several situations where that is no problem, but
> > if all 4 corners have unique coordinates both x, y and z then I  
> > suspect we can get floating point problems.
> > I guess we will have to find a way to deal with inaccurancy.
> 
> You're right, there's a floating point imprecision issue here.
> And except in naive integer examples we never could say yes or no
> on coplanar 4 points tests, so we have to deal on implementation
> with such imprecision
> 
> And that's one of the reason why a lot of 3D apps don't deal with
> PolyhedralSurface, but use TIN instead...
> 
> I realize quite recently that it would be a really good idea to  
> implement
> also TIN and Triangle. To be consistent with spec first (SQL/MM),
> and to have more additional external lib availables to help with
> meshes handling.
> 
> > From my understanding it can be compared to saying all points have  
> > to be exactly on the line. It is ok if it is two points, then it is  
> > no problem and it is ok
> > if the points have two constant coordinates like 'LINESTRING( 1 1 1,  
> > 1 1 3, 1 1 10, 1 1 12)' but if the line represents a slope there  
> > might be problems.
> 
> In a way yes !
> except you deal with one more axis ;)
> 
> > This has to be something fundamental when calculating distances  
> > against polyhedrals. I don't know the algoritms,
> > but from some reading I think the way to do it, for example the  
> > distance between a point and a polyhedral is to
> > "project the point to the plane"
> > check if the point is in the polygon on the plane
> > if so, the distance is between the projected point and the original  
> > point.
> > If not we have to do a distance calculation against the edges of the  
> > polygon. Like today, but in 3D.
> 
> I didn't yet really/fully analyze the Distance issue.
> But yes that's the general idea for 3D Surfaces.
> 
> One thing i don't know now is if there's a better algo
> to avoid to check each faces, one by one.
> 
> We could also had a Point In Polyhedron prior
> check on closed surfaces, for distance = 0 cases.
> 
That sounds like necessary. Maybe we can collect some information from
that calculation.

> > The point is that the central part of this is the plane. How to  
> > handle that if the points
> > are not exactly on the same plane.
> 
> It have to be coplanar 'enough'.
> As they will (quite) never be strictly coplanar.
> 

We need a solid way to determine the plane as good as possible. 
There is applications only caring about the integer part of the
coordinates. I guess the functions will have to deal with that too. Then
the error is not just on the last decimals but can be half a meter. 


> > Does this have an obvious solution that I'm missing or is it  
> > problems we will have to deal with?
> 
> Yes we have to deal with.
> 
> >
> > The same problem will occur with a "normal" polygon that is tilted.
> 
> Not sure to follow you on this point
> What do you mean tilted ?

I didn't know what word to use. What I meant is just a 3D polygon that
is not laying flat on the horizontal plane. By normal I just meant "not
polyhedral"


> 
> > I see this as a little similar problem as the inability to get an  
> > intersection between a point and a linestring.
> >
> > How to handle the inaccuracy?
> 
> Hopefully in real world we are more concerned
> by Point in Polygon use case :)
> 
> 
> > I might be totally lost in this.
> 
I think I used the wrong word here. I don't mean lost in finding a
solution but just lost in understanding.


> That's a really important part of the analysis/topological  
> implementation functions.
> A lot of 3D libs don't (have to) really care about numerical  
> robustness  as they're primarily
> design mostly for rendering.


> >
> > Another difference between calculating distance in 2D and 3D I have  
> > realized is that two linestring can have their closest parts on the  
> > edges of both. Not like 2D where at least one of the geometries must  
> > be closest with a vertex.
> > That is just an observation.
> 
> --
> Olivier
> 

What about the internal topology inside a polyhedral or a TIN. Is there
any ways of just storing each vertex once like the vertexes connecting
the faces and then referencing the vertexes in some way? The gain should
be primary topological robustness and maybe it could give performance
gain too. 

/Nicklas


> ____________________________
> postgis-devel mailing list
> postgis-devel at postgis.refractions.net
> http://postgis.refractions.net/mailman/listinfo/postgis-devel
> 





More information about the postgis-devel mailing list