[postgis-devel] Polyhedral, 3d and distance

[Olivier Courtin]

On Aug 9, 2010, at 8:13 PM, Nicklas Avén wrote:

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.


> 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.

> 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.

> 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 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.

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