I don't think the OGC PolyhedralSurface model will work together
with a multipolygon concept for a polyhedron (surface mesh), since
the connectivity between polygons will be severely complicated to
compute and change during topological operations if the points are
repeated for each polygon.
To ensure logical point uniqueness (not involving tolerances to
drop duplicates), the topology of the surface mesh must be
described either as a graph, or using indirect addressing like
Adam described in his previous email/ However, I am 100% certain
that ensuring point uniqueness with indirect addressing will cause
the algorithm complexity to literally explode.
I've tried using indrect addressing and subsequently ensuring
point uniqueness, and that is the reason why I want to switch to a
multipolygon representation and loose the connection between
polygons of the surface mesh, for intersecting smaller non-planar
polyhedra. In the end my goal is to efficiently intersect and
compute volume of the result between a halfspace and a small
polyhedron, two tetrahedral decompositions and two polyhedrons.
Maybe this is too specific for the geometry library.. I don't
know.. this is just my experience..
On 06/12/2013 12:32 PM, Barend Gehrels wrote:
On 12-6-2013 10:49, Tomislav Maric wrote:
On 06/12/2013 01:51 AM, Adam Wulkiewicz wrote:
Tomislav Maric wrote:
On 06/11/2013 10:12 PM, Adam Wulkiewicz wrote:
Correct me if I'm wrong but shouldn't ring, polygon, multipolygon,
etc. be always flat? It may be 3D, may have even some orientation and
position in 3D space, not only height, but should be flat. This way we
can perform some 2D operations on it by e.g. first projecting it into
the 2D plane. E.g. we can calculate convex hull (also flat) or
triangulate. I'm not so sure if using MultiPolygon concept to describe
3D mesh is a good idea. I'd rather provide additional concept.
IMHO this would be quite expensive. Coordinate transform is a Matrix
Vector multiplication, and it costs for nothing, if its only done to
enable 2D calculation on a 3d object. Another point, consider
incremental convex hull in 3D: computing the visible face is not
possible to do this way (mixed product makex only sense for non
co-planar vectors) simply because the hull construction will lie in 3D
and transforming it to 2D projection will not work. I'm sure the
quickhull algorithm is similar.
Sure, this was only an example. My point was that maybe there should
be introduced a new, as you've written, MultiPolygon-like concept. And
then algorithms should be built for it. Maybe even you'd like to
extend MultiPolygon somehow or change it to describe meshes in better
way? E.g. should 3D mesh contain faces which are polygons with holes?
Or could those containing only triangles be represented in some
Well, I am working on numerical methods for simulating fluid flow, and
they need flow domain to be decomposed into polyhedra like MultiPolygon,
so physics prevents the polygons of those polyhedra to have holes...
What I am aiming at is working on the algorithms in 3D in
boost.geometry, that I need in order to optimize my geometrical code for
speed + efficiency, and then extend what I get later for a more general
Triangles: that's a great question actually. Basically, the answer is
yes and no. Initially the polyhedron is consisted of polygons, but then
it is decomposed into tetrahedra to compute its volume and do subsequent
intersections. This is done because some of its polygons will be *non
planar* (search for voFoam on arXiv.org, page 12 I think).
So, there are three concepts, I believe: polyhedron (multipolygon
extended), tetrahedron and tetrahedral decomposition of a polyhedron
(just triangle faces: e.g. optimized normal vector calculation).
The OGC model is our reference model for the concepts point,
linestring, polygon, multi_point, multi_linestring, multi_polygon.
Up to now we have followed this model.
See also this webpage, where it can be downloaded:
The OGC talks consequently about a "PolyhedralSurface".
I copy a part from the PDF here for convenience:
A PolyhedralSurface is a contiguous collection of
polygons, which share common boundary segments. For each
pair of polygons that “touch”, the common boundary shall be
expressible as a finite collection of LineStrings. Each
such LineString shall be part of the boundary of at most 2
Polygon patches. A TIN (triangulated irregular network)
is a PolyhedralSurface consisting only of Triangle patches.
For any two polygons that share a common boundary, the “top” of
the polygon shall be consistent. This means
that when two LinearRings from these two Polygons traverse
the common boundary segment, they do so in
opposite directions. Since the Polyhedral surface is
contiguous, all polygons will be thus consistently oriented.
This means that a non-oriented surface (such as Möbius
band) shall not have single surface representations.
They may be represented by a MultiSurface. Figure 14 shows
an example of such a consistently oriented surface
(from the top). The arrows indicate the ordering of the
linear rings that from the boundary of the polygon in which
they are located.
Figure 14: Polyhedral Surface with consistent orientation
If each such LineString is the boundary of exactly 2 Polygon
patches, then the PolyhedralSurface is a simple,
closed polyhedron and is topologically isomorphic to the
surface of a sphere. By the Jordan Surface Theorem
(Jordan’s Theorem for 2-spheres), such polyhedrons enclose
a solid topologically isomorphic to the interior of a
sphere; the ball. In this case, the “top” of the surface
will either point inward or outward of the enclosed finite
If outward, the surface is the exterior boundary of the
enclosed surface. If inward, the surface is the interior of the
infinite complement of the enclosed solid. A Ball with some
number of voids (holes) inside can thus be presented
as one exterior boundary shell, and some number in interior
Geometry mailing list