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.
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 |
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. _______________________________________________ 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 (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: 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 |
In reply to this post by Parkinbot
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 ; _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
In reply to this post by Parkinbot
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 n-partion (or a triangulation in the limit) can be found. -- Sent from: http://forum.openscad.org/ _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
Ronaldo wrote You are right. Nice counterexample. My present code was successful in finding a partition:
_______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
This post was updated on .
Ronaldo wrote
> There are 10 polygons in the partition and it seems that a minimal > partition would have 6 parts. The example has a bipartition. -- Sent from: http://forum.openscad.org/ _______________________________________________ OpenSCAD mailing list Discuss@lists.openscad.org 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. _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
In reply to this post by Ronaldo
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 |
In reply to this post by Ronaldo
Ronaldo Persiano <[hidden email]> wrote:
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 |
In reply to this post by NateTG
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 _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
In reply to this post by Ronaldo
On 2019-01-21 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. 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 |
Ronaldo wrote
> we might instead sweep the polygon border and subtract the > sweeping of each hole in a slower process. we might instead sweep the polygon border and difference a lazy_union of the sweeps of the holes. -- Sent from: http://forum.openscad.org/ _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
In reply to this post by Parkinbot
Parkinbot wrote
> The example has a bipartition. Sorry I didn't finish this post for some reason. I wanted to write that the example has a bipartition (many indeed), but I doubt that the algorithm will find it, unless it uses a backtracking scheme. -- Sent from: http://forum.openscad.org/ _______________________________________________ OpenSCAD mailing list [hidden email] http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org |
Free forum by Nabble | Edit this page |