It is possible to manipulate the initial runsun model in such way the
polyhedron is acceptable by CGAL and faces with hole do not need to be
triangulated. If enough well placed bridges are added (the number of holes
plus one) a polygon with holes is split in two polygons meeting at the
bridges. The following example, based on the runsun model, illustrates the
principle.

pts = [[0, 0, 0], [0, 4, 0], [3, 5, 0], [2, 0, 0],
[0, 0, 2], [0, 4, 2], [3, 5, 2], [2, 0, 2],
[1, 0.5, 0], [0.4, 1.2, 0], [0.5, 2.1, 0], [2, 1.5, 0],
[1, 0.5, 2], [0.4, 1.2, 2], [0.5, 2.1, 2], [2, 1.5, 2],
[1.5, 2.5, 0], [0.5, 3.5, 0], [2, 3.5, 0],
[1.5, 2.5, 2], [0.5, 3.5, 2], [2, 3.5, 2]];

faces = [[7, 4, 5, 6, 21, 20, 19, 14, 13, 12],  // top blue
[7, 12, 15, 14, 19, 21, 6],            // top red
[3, 2, 18, 16, 10, 11],                // bottom red
[2, 1, 0, 3, 11, 8, 9, 10, 16, 17, 18], // bottom blue
[0, 1, 5, 4], [1, 2, 6, 5], [2, 3, 7, 6],
[3, 0, 4, 7], [9, 8, 12, 13], [10, 9, 13, 14],
[11, 10, 14, 15], [8, 11, 15, 12], [17, 16, 19, 20],
[18, 17, 20, 21], [16, 18, 21, 19]];

The following image of the polyhedron(pts, faces) enhances the top and
bottom partition:

[image: polyWithHoles.PNG]

Intentionally the top and bottom partitions are differents. Note that each
of the faces with holes has 3 bridges that are common to the two polygons
of the partition.

I guess the method I coded to find the bridges is O(m) where m is the
number of holes which is lot better than the triangulation methods. The
original method finds m bridges for m holes in the polygon. It may be
changed to find an additional bridge that split the face in two. I am
working on this now.

The image bellow shows the render of difference between the polyhedron and
a cube.

[image: polyRendered.PNG]

Correction: my guess of the order of the bridging method was wrong; I meant
O(n.m) for m holes and n total number of vertices.

Ronaldo

first, thanks for the earcut. It works well.

I am also thrilled by your solution to decompose a face with holes into two
(or more?) faces without holes. This is definitely a good approach for
implementing a multihole sweep. Does your algorithm find such a
decomposition for an unlimited number of holes?

As I understand it, the proposed function sweepMH() will now be something
like:

function sweepMH(manifolds) =
let(firstfaces = decompose(polyHole(manifolds)))
let(lastfaces = decompose(polyHole(manifolds, last=true))
...

--
Sent from: http://forum.openscad.org/

Parkinbot,

The polyHoles() code implements the David Eberly method of bridging a
polygon with (any number of) holes in order to apply his earcut
triangulation method  to the resulting (almost) simple polygon. The polygon
polyHoles() returns has no holes but is not really a simple polygon: some
edges of it are traveled twice as you traverse its full cycle. I call those
edges as (two-way) bridges. As CGAL doesn't like polyhedron faces with the
kind of polygons polyHoles produces, my proposal is to write an algorithm
based on the Eberly's one to partition a simple polygon with holes in
(really) simple polygons without holes.

In my last few messages, I have made a set of very naive conjectures about
this problem and its solving algorithm: 1) it is possible to partition the
original polygon with holes in exactly two parts, 2) this partition is done
by m+1 bridges and 3) the order of the solving method would be O(m.n) where
m is the number of holes and n is the total number of vertices. Those
conjectures  are in fact true for convex polygons with convex holes.

For convex holes but non-convex polygons, the number of necessary bridges
may be 2.m and the partition may have m+1 parts. For non-convex holes,
things become very wild! I don't have a guess for the number of parts in
the partition but the number of bridges may increase to something like 2^m
and the complexity grows to O( (2^m).n). Still, my expectancy is that this
approach would be better than triangulation.

I am still working on the method I have in mind to partition a polygon with
many holes in simple polygons without holes. To have a flavor of what would
result in a non-convex case consider the following image:

[image: Poly2holes.PNG]

The red bridges have been obtained by a direct application of
polyHoles(outer,mH). The yellow bridges result from the application of
polyHoles(-outer, -mH). Four bridges partition the original polygon in 3
parts. However, it is possible to partition it in 2 parts with just 3
bridges.

Parkinbot,

The ear-cut triangulation method I have attached before is good only for
the kind of polygons polyHoles generates. It may lead to wrong results
(like degenerated triangles) when an additional vertex is added to some
bridge. So I think it is risky to use it in any other cases. To have a
proper ear-cut triangulation method that works for proper simple polygons
the function isCCW should have the following definition:

function isCCW(a, b, c) = CCW(a,b,c) >= 0 ;

Ronaldo,
I intuitively unterstand the separation algorithm as follows:

Be P the point set of the outer polygon and I = {P1, P2 ...} the points sets
of the holes.

1. find first bridge between P and I: calculate all point distances between
   P and I and select the hole P_ containing the point closest to O to build
   the brigde. Remove P_ from I and get I_
2. find bridge from hole P_ to closest hole in I_: exclude the ingoing
   bridge point from P_, set P_ as P and I_ as I.
3. if I is not empty go to step 1.

selecting always the shortest distance to build a brige, guarantees that no
other polygon can be cut. Thus we have all bridges exept the last.

The problem: I don't see, why we should be able to find a bridge to the
outer polygon again and I doubt that such a bridge will always exist.

See this example:

P = [[0,0],  [10,0], [10,10], [0,10]];
Q1 = [[2,7.8], [1,7.8], [1,1],  [9,1], [9,9], [1,9], [1,8], [8,8], [8,2],
[2,2], ];
Q2 = [[4,3],  [3,4], [3,3]];

linear_extrude(.1, convexity = 9)
difference()
{
polygon(P);
polygon(Q1);
polygon(Q2);
}

--
Sent from: http://forum.openscad.org/

Parkinbot,

polyHoles doesn't try to find a bridge between each hole and the polygon
boundary. Some bridges may connect two holes.
It operates as following:

a) find the hole having the rightmost vertex among all hole vertices;
b) project this vertex to the right to a point in the polygon border;
c) find a vertex of the polygon "near" the projection point whose
connection to the hole vertex of a) is a bridge;
d) redefine the polygon using that bridge and the hole of a) ;
e) remove the hole of a) from the list of holes;
f) recur with the redefined polygon and the updated list of holes.

So, in your example, there would be a bridge from the squared hole to the
polygon border and another one between the two holes.

In the algorithm schema above, item c) is a bit more complex than described.

David Eberly's explanation of the algorithm is very clear and easy to
follow.

Ronaldo,

this is exactly what I meant and what I tried to express:
Go from the outer polygon to nearest hole, then from this hole to the
nearest unbridged hole and so on until you reach the last unbridged hole.
To get a full separation into two facets, you have to add a final bridge
from last hole to the outer polygon. And this is not always possible.

--
Sent from: http://forum.openscad.org/

We agree. A bipartition with m+1 bridges is assured when the main polygon
and the holes are convex. But, for very intricate geometry of m holes, the
number of parts and number of bridges seem to grow exponentially with m.

In the picture bellow, the main polygon border is white. There are 3 holes,
filled by the colors green, red and blue. One possible set of bridges to
subdivide the polygon in simple polygons are represented in yellow.

[image: spiraledHoles.PNG]

The polygon partition has 6 parts. It is possible to add a fourth spiraled
hole squeezed between all previous holes that will require to double the
number of bridges and will produce the double of parts in the partition.
And so on...