Geometry Boost List: Re: [geometry] 3D box -> 3D multi_polygon conversion

Subject: Re: [geometry] 3D box -> 3D multi_polygon conversion
From: Tomislav Maric (tomislav.maric_at_[hidden])
Date: 2013-06-12 18:08:52

Hi Barend

On 06/12/2013 11:26 PM, Barend Gehrels wrote:
> Note 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 good.
>
> 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:

"
/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.
"
/
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:

polygon p1;
p1.push_back...

polygon p2;
p2.push_back...

multipolygon M1;

M1.push_back(p1);
M1.push_back(p2);

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 explode. 
>
> 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 operation.
>
>>
>> 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..
>
> I don't think it is too specific, but we need a generic concept able
> to store polyhedrons described either as triangles, or as polygons.

I'm new to Concepts, I'm only putting in my 2 cents from my experiences
with 3D algorithms....

Best regards,
Tomislav

>
> Regards, Barend
>
>
>
>
> _______________________________________________
> Geometry mailing list
> Geometry_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/geometry