Empathy List Archives

RP

Ronaldo Persiano

Sun, Jan 20, 2019 2:37 PM

Parkinbot rudolf@digitaldocument.de wrote:

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.

You are right. Nice counterexample. My present code was successful in
finding a partition:

[image: RudolfExample.PNG]

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! :(

Parkinbot <rudolf@digitaldocument.de> wrote: > 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. > > You are right. Nice counterexample. My present code was successful in finding a partition: [image: RudolfExample.PNG] 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! :(

P

Parkinbot

Mon, Jan 21, 2019 10:54 AM

Ronaldo wrote

There are 10 polygons in the partition and it seems that a minimal
partition would have 6 parts.

The example has a bipartion.

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

Ronaldo wrote > There are 10 polygons in the partition and it seems that a minimal > partition would have 6 parts. The example has a bipartion. -- Sent from: http://forum.openscad.org/

RP

Ronaldo Persiano

Mon, Jan 21, 2019 4:45 PM

Yes, you are right: the solution of an Eulerian cycle through all possible
bridges. It will require m+1 bridges for m holes.

Yes, you are right: the solution of an Eulerian cycle through all possible bridges. It will require m+1 bridges for m holes.

N

NateTG

Mon, Jan 21, 2019 7:38 PM

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/

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/

RP

Ronaldo Persiano

Mon, Jan 21, 2019 8:12 PM

Ronaldo Persiano rcmpersiano@gmail.com 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.

[image: biPartition.PNG]

Interestingly, the symmetry of the polygon with holes is somewhat reflected
in two congruent parts.

Ronaldo Persiano <rcmpersiano@gmail.com> 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. [image: biPartition.PNG] Interestingly, the symmetry of the polygon with holes is somewhat reflected in two congruent parts.

RP

Ronaldo Persiano

Mon, Jan 21, 2019 8:28 PM

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.

NateTG nate-openscadforum@pedantic.org wrote:

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.

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. NateTG <nate-openscadforum@pedantic.org> wrote: > 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. >

A

arnholm@arnholm.org

Mon, Jan 21, 2019 8:49 PM

On 2019-01-21 21:12, Ronaldo Persiano wrote:

Ronaldo Persiano rcmpersiano@gmail.com 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

On 2019-01-21 21:12, Ronaldo Persiano wrote: > Ronaldo Persiano <rcmpersiano@gmail.com> 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

RP

Ronaldo Persiano

Mon, Jan 21, 2019 8:59 PM

arnholm@arnholm.org wrote:

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.

<arnholm@arnholm.org> wrote: > 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.

P

Parkinbot

Mon, Jan 21, 2019 9:50 PM

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/

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/

P

Parkinbot

Mon, Jan 21, 2019 9:56 PM

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/

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/

discuss@lists.openscad.org

Polyhedron tube with irregular sides -- is it possible ?