
123456

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:
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.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


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/_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.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 (twoway) 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 nonconvex polygons, the number of necessary bridges may be 2.m and the partition may have m+1 parts. For nonconvex 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 nonconvex case consider the following image:
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.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Parkinbot,
The earcut 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 earcut 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 ;
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


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/_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.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.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


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/_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.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.
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...
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Ronaldo wrote
> A bipartition with m+1 bridges is assured when the main polygon
> and the holes are convex.
I doubt that, see this arrangement
<http://forum.openscad.org/file/t887/bis.png>
Of course, some npartion (or a triangulation in the limit) can be found.
You are right. Nice counterexample. My present code was successful in finding a partition:
A total of 2.m bridges (for m holes) was found by my partition code but 4 bridges might be discarded in that solution. There are 10 polygons in the partition and it seems that a minimal partition would have 6 parts. A partition in triangles would require something as 37 bridges.
Although it is conceptually simple the algorithm is showing to be hard to code and debug. Harder seems to prove that it works! :(
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


I'd be concerned about the impact of floating point rounding on clipping
ears.
Computationally, you can do way better than ear clipping here and instead
use a sweep line to split it into monotone polygons. That's Order n log n
in the number of vertices.
When I tried a "partition into chunks" approach for doing beveled text, I
had less than ideal results way that OpenSCAD also seems to do rounding when
generating geometry.

Sent from: http://forum.openscad.org/_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Yes, you are right: the solution of an Eulerian cycle through all possible bridges. It will require m+1 bridges for m holes.
I cannot assure it is always possible but I could find a bipartition of Parkinbot's convex hole case by judiciously deleting bridges found by my present code.
Interestingly, the symmetry of the polygon with holes is somewhat reflected in two congruent parts.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


I agree that earcut method may generate very bad triangles, almost degenerated. That is one reason I would look for something else. I don't know how the sweep line algorithms work but remind that for our application in mind we can't add new vertices to any polygonal. Computationally, you can do way better than ear clipping here and instead
use a sweep line to split it into monotone polygons. That's Order n log n
in the number of vertices.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


On 20190121 21:12, Ronaldo Persiano wrote:
> Ronaldo Persiano < [hidden email]> wrote:
>
>> Yes, you are right: the solution of an Eulerian cycle through all
>> possible bridges. It will require m+1 bridges for m holes.
>
> I cannot assure it is always possible but I could find a bipartition
> of Parkinbot's convex hole case by judiciously deleting bridges found
> by my present code.
>
> Interestingly, the symmetry of the polygon with holes is somewhat
> reflected in two congruent parts.
Why this long and complex discussion when you can use 2D booleans  i.e.
subtract the holes from the main rectangle and simply extrude that?
What is missing in this thinking?
Carsten Arnholm
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


Why this long and complex discussion when you can use 2D booleans  i.e.
subtract the holes from the main rectangle and simply extrude that?
The main goal now is to sweep a polygon with holes along a polygonal line using fast polyhedron. This avoid slower boolean operations. As Parkinbot pointed before, we might instead sweep the polygon border and subtract the sweeping of each hole in a slower process.
_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org

123456
