On 06/12/2013 11:26 PM, Barend Gehrels wrote:
that it is the Concept which repeat points. The implementation
might be different. I mean: the Concept has methods as NumPatch,
Patch(index), or probably an iterator returning polygons. However,
this can be stored internally as the implementator thinks it is
Besides this, I don't understand - if you want to use
multipolygons to store the polyhedron, I always assumed that you
wanted to repeat coordinates...
I would definitely like to use multipolygons to store polyhedra, at
least as a start, then see how fast the intersection and collision
detection wil work coupled with axis aligned bounding box tests.
It is a bit as a collection of polygons, some files (shapefiles)
store all coordinates per polygon, others (ESRI coverages) use
topology, however, retrieving one polygon always returns just that
polygon, regardless how it is stored.
Retrieving a polygon is O.K., but retrieving a common boundary costs
with repeating points. And for algorithms relying on polygon
boundaries, this incurrs complexity increase. A part in the
description of the OGC Polyhedral Surface Model says:
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
So, lets say I have two polygons that touch, with repeating points
as shown on the attached image for two squares (see attached
Figure). Even if the normals of the polygons are consistent (as
indicated by the order of the point labels), I don't think that
finding the common boundary is trivial. If the points are repeated
per each polygon, the touching edge is not known without
computation that compares equality of points. If I am to construct a
polyhedron that's a multipolygon, I would do:
At this point M1 has no idea that its two polygons have a common
boundary, since for a multipolyon, there are no topological
restrictions, if I understand the concept right...
So the only way to compute the common boundary is to find out
(checking if points are equal?) that the edge 0-1 in polygon p1 is
the opposite of the edge 1-2 in the polygon p2. This is what I mean
by complicating things. I am very new to Concepts, so I might be
missing your point as well, if so, I'll need read more about it,
maybe things get clearer for me.
But if the model is to provide "an accessible common boundary", then
the unique-point implementation does it automatically (graph based
works better for intersection operations, this I can back up with
articles), and the non-unique point (multipolygon concept) requires
calculation of connectivity based on I guess equality of points...
and equality == precision issues.
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
I don't exactly understand why the complexity explodes by just
using indirect addressing. It is IMO just a way to access the
coordinates. If the Concept gives certain methods, the
implementations (using either direct or indirect addresses and
either unique or duplicated points) might vary. The algorithms
should use the Concept to support different types of polyhedrons.
Say that there is a polyhedron described with indirect addressing.
If it is intersected by a half-space, you can know exactly which
edges are cut, and from the edge-faces connectivity, you know
exactly which edges do not have a face accross them anymore (hole
created by the intersection). Intersecting it and updating indirect
addressing topology is more difficult then clipping each polygon in
a polygon soup and storing 2 intersection points per edge.
Say that there is a polyhedron described as a multipolygon. The
intersection with a half-space loops over all polygons, and the
results will be polygon clips, or complete polygons, if they are
completely within the halfspace. But now we have a hole in our
result polyhedron, where the plane lies. How to connect the points
of that hole? One way is to re-compute edge connectivity for a
concept that doesn't support it (multipolygon) which might involve
point equality (quadratic if not worse with respect to the sum of
points of both polyhedra). The other way is to do a convex hull in
2D of an already convex set of points which resorts to a single sort
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
I don't think it is too specific, but we need a generic concept
able to store polyhedrons described either as triangles, or as
I'm new to Concepts, I'm only putting in my 2 cents from my
experiences with 3D algorithms....
Geometry mailing list