Hi,

Guest

NS

Nathan Sokalski

Sun, Jan 28, 2024 3:36 AM

When generating the points for a polygon (or more often modifying them), I sometimes end up creating a perimeter that intersects itself, which displays what looks sort of like multiple polygons. Detecting these intersections & modifying the list of points can sometimes be very tedious, since determining which one is the one I want is an impossible task. Does anybody have any suggestions on the most efficient way to do this?

Nathan Sokalski

njsokalski@hotmail.commailto:njsokalski@hotmail.com

When generating the points for a polygon (or more often modifying them), I sometimes end up creating a perimeter that intersects itself, which displays what looks sort of like multiple polygons. Detecting these intersections & modifying the list of points can sometimes be very tedious, since determining which one is the one I want is an impossible task. Does anybody have any suggestions on the most efficient way to do this?
Nathan Sokalski
njsokalski@hotmail.com<mailto:njsokalski@hotmail.com>

DP

David Phillip Oster

Sun, Jan 28, 2024 3:50 AM

I use this:

module label(pts){

for (i = [0:len(pts)-1]) {

```
translate(pts[i])rotate([90, 0,
```

0])color("blue")linear_extrude(0.1)text(str(i));

}

}

for lists of 2D or 3D points. This plots the integer index in the array of

each point next to the point, so I can see which point is the offending one.

On Sat, Jan 27, 2024 at 7:36 PM Nathan Sokalski via Discuss <

discuss@lists.openscad.org> wrote:

When generating the points for a polygon (or more often modifying them), I

sometimes end up creating a perimeter that intersects itself, which

displays what looks sort of like multiple polygons. Detecting these

intersections & modifying the list of points can sometimes be very tedious,

since determining which one is the one I want is an impossible task. Does

anybody have any suggestions on the most efficient way to do this?

Nathan Sokalski

njsokalski@hotmail.com

OpenSCAD mailing list

To unsubscribe send an email to discuss-leave@lists.openscad.org

I use this:
module label(pts){
for (i = [0:len(pts)-1]) {
translate(pts[i])rotate([90, 0,
0])color("blue")linear_extrude(0.1)text(str(i));
}
}
for lists of 2D or 3D points. This plots the integer index in the array of
each point next to the point, so I can see which point is the offending one.
On Sat, Jan 27, 2024 at 7:36 PM Nathan Sokalski via Discuss <
discuss@lists.openscad.org> wrote:
> When generating the points for a polygon (or more often modifying them), I
> sometimes end up creating a perimeter that intersects itself, which
> displays what looks sort of like multiple polygons. Detecting these
> intersections & modifying the list of points can sometimes be very tedious,
> since determining which one is the one I want is an impossible task. Does
> anybody have any suggestions on the most efficient way to do this?
>
> Nathan Sokalski
> njsokalski@hotmail.com
> _______________________________________________
> OpenSCAD mailing list
> To unsubscribe send an email to discuss-leave@lists.openscad.org
>

N

neri-engineering

Sun, Jan 28, 2024 4:01 AM

I keep my segment counts ($fn) the same for both objects whenever they join, for example mating a cylinder inside of a cylindrical hole. Furthermore I keep the orientations such that a "seam" happens on the +x axis. If I cannot guarantee that then I make the $fn a multiple of four, such that any 90 degree rotation or mirror along an axis would still guarantee that alignment. I use these strategies when things are overlapping, and when they just barely touch but don't overlap.

Just an interesting note, cylinder() and rotate_extrude() place their "initial vertex" at a different location, if I recall correctly rotate_extrude() places its initial vertex on the negative x axis while cylinder() places its initial vertex on the positive x axis. For this reason I rewrote rotate_extrude() to have it align in a consistent way.

Sometimes you want to deliberately fudge the radius of a coarse polygon/circle, and align it such in its rotation so that it intersects perfectly with some radial distance and angle. For that you need some algebraic derivations, which I also do all the time. I could give examples but would probably be wasting both of our times.

Sent with Proton Mail secure email.

On Saturday, January 27th, 2024 at 9:36 PM, Nathan Sokalski via Discuss discuss@lists.openscad.org wrote:

When generating the points for a polygon (or more often modifying them), I sometimes end up creating a perimeter that intersects itself, which displays what looks sort of like multiple polygons. Detecting these intersections & modifying the list of points can sometimes be very tedious, since determining which one is the one I want is an impossible task. Does anybody have any suggestions on the most efficient way to do this?

Nathan Sokalski

njsokalski@hotmail.com

I keep my segment counts ($fn) the same for both objects whenever they join, for example mating a cylinder inside of a cylindrical hole. Furthermore I keep the orientations such that a "seam" happens on the +x axis. If I cannot guarantee that then I make the $fn a multiple of four, such that any 90 degree rotation or mirror along an axis would still guarantee that alignment. I use these strategies when things are overlapping, and when they just barely touch but don't overlap.
Just an interesting note, cylinder() and rotate_extrude() place their "initial vertex" at a different location, if I recall correctly rotate_extrude() places its initial vertex on the negative x axis while cylinder() places its initial vertex on the positive x axis. For this reason I rewrote rotate_extrude() to have it align in a consistent way.
Sometimes you want to deliberately fudge the radius of a coarse polygon/circle, and align it such in its rotation so that it intersects perfectly with some radial distance and angle. For that you need some algebraic derivations, which I also do all the time. I could give examples but would probably be wasting both of our times.
Sent with [Proton Mail](https://proton.me/) secure email.
On Saturday, January 27th, 2024 at 9:36 PM, Nathan Sokalski via Discuss <discuss@lists.openscad.org> wrote:
> When generating the points for a polygon (or more often modifying them), I sometimes end up creating a perimeter that intersects itself, which displays what looks sort of like multiple polygons. Detecting these intersections & modifying the list of points can sometimes be very tedious, since determining which one is the one I want is an impossible task. Does anybody have any suggestions on the most efficient way to do this?
>
> Nathan Sokalski
> njsokalski@hotmail.com

RW

Raymond West

Sun, Jan 28, 2024 12:00 PM

Hi Nathan,

if you draw a straight line in any direction from a point inside a

polygon it will cross the boundary an odd number of times. I'm not sure,

but if you are testing a point that is on a boundary, you can go in two

opposite directions, and if the lines cross the boundary an even number

of times then that point is on an inclusion. Maybe that helps?

Best wishes,

Ray

On 28/01/2024 03:36, Nathan Sokalski via Discuss wrote:

them), I sometimes end up creating a perimeter that intersects itself,

which displays what looks sort of like multiple polygons. Detecting

these intersections & modifying the list of points can sometimes be

very tedious, since determining which one is the one I want is an

impossible task. Does anybody have any suggestions on the most

efficient way to do this?

Nathan Sokalski

njsokalski@hotmail.com

OpenSCAD mailing list

To unsubscribe send an email todiscuss-leave@lists.openscad.org

Hi Nathan,
if you draw a straight line in any direction from a point inside a
polygon it will cross the boundary an odd number of times. I'm not sure,
but if you are testing a point that is on a boundary, you can go in two
opposite directions, and if the lines cross the boundary an even number
of times then that point is on an inclusion. Maybe that helps?
Best wishes,
Ray
On 28/01/2024 03:36, Nathan Sokalski via Discuss wrote:
> When generating the points for a polygon (or more often modifying
> them), I sometimes end up creating a perimeter that intersects itself,
> which displays what looks sort of like multiple polygons. Detecting
> these intersections & modifying the list of points can sometimes be
> very tedious, since determining which one is the one I want is an
> impossible task. Does anybody have any suggestions on the most
> efficient way to do this?
>
> Nathan Sokalski
> njsokalski@hotmail.com
>
> _______________________________________________
> OpenSCAD mailing list
> To unsubscribe send an email todiscuss-leave@lists.openscad.org

RW

Rogier Wolff

Sun, Jan 28, 2024 12:51 PM

On Sun, Jan 28, 2024 at 12:00:39PM +0000, Raymond West via Discuss wrote:

Hi Nathan,

if you draw a straight line in any direction from a point inside a polygon

it will cross the boundary an odd number of times. I'm not sure, but if you

are testing a point that is on a boundary, you can go in two opposite

directions, and if the lines cross the boundary an even number of times then

that point is on an inclusion. Maybe that helps?

He asked for an efficient way... Drawing an infinite number of lines

is considered "not efficient" by many programmers....

Write every segment of your polygon as A + a(B-A) where B and A are the

endpoints The small a is a parameter from 0 to 1.

Now, to check if AB intersects CD, you do this for both lines, (use b

as the parameter beteween CD). Now find the intersection of the two

lines: Calculate a and b when A + a(B-A) = C + b(D-C) . Now if a and b

are both between 0 and one you have an intersection. if either is not

inside that range, the segements do not cross. (If a is inside the

0 - 1 range and b is not, the extension of CD will intersect AB,

but for our purpose that is not crossing. Same holds other way around).

If you get a division by zero while calculating a and b, the segments

are parallel. There are a few side-cases that might be important here.

Say AB = ((0,0) - (1,0)) and CD is ((2,0)-3,0)) These do not intersect.

But swap B and C and they do!

```
Roger.
```

Best wishes,

Ray

On 28/01/2024 03:36, Nathan Sokalski via Discuss wrote:

I sometimes end up creating a perimeter that intersects itself, which

displays what looks sort of like multiple polygons. Detecting these

intersections & modifying the list of points can sometimes be very

tedious, since determining which one is the one I want is an impossible

task. Does anybody have any suggestions on the most efficient way to do

this?

Nathan Sokalski

njsokalski@hotmail.com

OpenSCAD mailing list

To unsubscribe send an email todiscuss-leave@lists.openscad.org

--

** R.E.Wolff@BitWizard.nl ** https://www.BitWizard.nl/ ** +31-15-2049110 **

** Delftechpark 11 2628 XJ Delft, The Netherlands. KVK: 27239233 **

f equals m times a. When your f is steady, and your m is going down

your a is going up. -- Chris Hadfield about flying up the space shuttle.

On Sun, Jan 28, 2024 at 12:00:39PM +0000, Raymond West via Discuss wrote:
> Hi Nathan,
>
>
> if you draw a straight line in any direction from a point inside a polygon
> it will cross the boundary an odd number of times. I'm not sure, but if you
> are testing a point that is on a boundary, you can go in two opposite
> directions, and if the lines cross the boundary an even number of times then
> that point is on an inclusion. Maybe that helps?
He asked for an efficient way... Drawing an infinite number of lines
is considered "not efficient" by many programmers....
Write every segment of your polygon as A + a(B-A) where B and A are the
endpoints The small a is a parameter from 0 to 1.
Now, to check if AB intersects CD, you do this for both lines, (use b
as the parameter beteween CD). Now find the intersection of the two
lines: Calculate a and b when A + a(B-A) = C + b(D-C) . Now if a and b
are both between 0 and one you have an intersection. if either is not
inside that range, the segements do not cross. (If a is inside the
0 - 1 range and b is not, the extension of CD will intersect AB,
but for our purpose that is not crossing. Same holds other way around).
If you get a division by zero while calculating a and b, the segments
are parallel. There are a few side-cases that might be important here.
Say AB = ((0,0) - (1,0)) and CD is ((2,0)-3,0)) These do not intersect.
But swap B and C and they do!
Roger.
>
>
> Best wishes,
>
>
> Ray
>
>
>
> On 28/01/2024 03:36, Nathan Sokalski via Discuss wrote:
> > When generating the points for a polygon (or more often modifying them),
> > I sometimes end up creating a perimeter that intersects itself, which
> > displays what looks sort of like multiple polygons. Detecting these
> > intersections & modifying the list of points can sometimes be very
> > tedious, since determining which one is the one I want is an impossible
> > task. Does anybody have any suggestions on the most efficient way to do
> > this?
> >
> > Nathan Sokalski
> > njsokalski@hotmail.com
> >
> > _______________________________________________
> > OpenSCAD mailing list
> > To unsubscribe send an email todiscuss-leave@lists.openscad.org
> _______________________________________________
> OpenSCAD mailing list
> To unsubscribe send an email to discuss-leave@lists.openscad.org
--
** R.E.Wolff@BitWizard.nl ** https://www.BitWizard.nl/ ** +31-15-2049110 **
** Delftechpark 11 2628 XJ Delft, The Netherlands. KVK: 27239233 **
f equals m times a. When your f is steady, and your m is going down
your a is going up. -- Chris Hadfield about flying up the space shuttle.

RW

Rogier Wolff

Sun, Jan 28, 2024 1:52 PM

On Sun, Jan 28, 2024 at 01:51:33PM +0100, Rogier Wolff via Discuss wrote:

On Sun, Jan 28, 2024 at 12:00:39PM +0000, Raymond West via Discuss wrote:

Hi Nathan,

if you draw a straight line in any direction from a point inside a polygon

it will cross the boundary an odd number of times. I'm not sure, but if you

are testing a point that is on a boundary, you can go in two opposite

directions, and if the lines cross the boundary an even number of times then

that point is on an inclusion. Maybe that helps?

He asked for an efficient way... Drawing an infinite number of lines

is considered "not efficient" by many programmers....

Write every segment of your polygon as A + a(B-A) where B and A are the

endpoints The small a is a parameter from 0 to 1.

Now, to check if AB intersects CD, you do this for both lines, (use b

as the parameter beteween CD). Now find the intersection of the two

lines: Calculate a and b when A + a(B-A) = C + b(D-C) . Now if a and b

are both between 0 and one you have an intersection. if either is not

inside that range, the segements do not cross. (If a is inside the

0 - 1 range and b is not, the extension of CD will intersect AB,

but for our purpose that is not crossing. Same holds other way around).

If you get a division by zero while calculating a and b, the segments

are parallel. There are a few side-cases that might be important here.

Say AB = ((0,0) - (1,0)) and CD is ((2,0)-3,0)) These do not intersect.

But swap B and C and they do!

P.S.

This would be O(N^2)... which might lead to unacceptable runtimes for large

datasets.

If you want to improve on that, declare say N= 10 a small enough numer

that N^2 runtime is acceptable.

Divide the plane into two: x>0 and x<0. Divide the line segments into

three groups: Both enpoints in in one half, both endpoints into the

other half and "spans both halves". regretably we can't do much about

that last group. Repeat dividing into two/three classes by first

repeating this for Y and then e.g. using x=1 as a divider, Then for

the class "bigger than every divider before this" you continue

multiplying by two, and once you have two boundaries for a group you

simply divide that group into two halves.Continue until the groups are

small enough. That's where the "N=10" comes into play.

You might be able to craft datasets that behave horribly under this

algorithm, but "natural" datashets will quickly be divided up into

small groupw. Small enough that testing inside a group

For the "not both points in one portion of the plane", you'd have to

check them against the LOG (N) regions that the algorithm has chosen.

```
Roger.
```

--

** R.E.Wolff@BitWizard.nl ** https://www.BitWizard.nl/ ** +31-15-2049110 **

** Delftechpark 11 2628 XJ Delft, The Netherlands. KVK: 27239233 **

f equals m times a. When your f is steady, and your m is going down

your a is going up. -- Chris Hadfield about flying up the space shuttle.

On Sun, Jan 28, 2024 at 01:51:33PM +0100, Rogier Wolff via Discuss wrote:
> On Sun, Jan 28, 2024 at 12:00:39PM +0000, Raymond West via Discuss wrote:
> > Hi Nathan,
> >
> >
> > if you draw a straight line in any direction from a point inside a polygon
> > it will cross the boundary an odd number of times. I'm not sure, but if you
> > are testing a point that is on a boundary, you can go in two opposite
> > directions, and if the lines cross the boundary an even number of times then
> > that point is on an inclusion. Maybe that helps?
>
> He asked for an efficient way... Drawing an infinite number of lines
> is considered "not efficient" by many programmers....
>
> Write every segment of your polygon as A + a(B-A) where B and A are the
> endpoints The small a is a parameter from 0 to 1.
>
> Now, to check if AB intersects CD, you do this for both lines, (use b
> as the parameter beteween CD). Now find the intersection of the two
> lines: Calculate a and b when A + a(B-A) = C + b(D-C) . Now if a and b
> are both between 0 and one you have an intersection. if either is not
> inside that range, the segements do not cross. (If a is inside the
> 0 - 1 range and b is not, the extension of CD will intersect AB,
> but for our purpose that is not crossing. Same holds other way around).
>
> If you get a division by zero while calculating a and b, the segments
> are parallel. There are a few side-cases that might be important here.
> Say AB = ((0,0) - (1,0)) and CD is ((2,0)-3,0)) These do not intersect.
> But swap B and C and they do!
P.S.
This would be O(N^2)... which might lead to unacceptable runtimes for large
datasets.
If you want to improve on that, declare say N= 10 a small enough numer
that N^2 runtime is acceptable.
Divide the plane into two: x>0 and x<0. Divide the line segments into
three groups: Both enpoints in in one half, both endpoints into the
other half and "spans both halves". regretably we can't do much about
that last group. Repeat dividing into two/three classes by first
repeating this for Y and then e.g. using x=1 as a divider, Then for
the class "bigger than every divider before this" you continue
multiplying by two, and once you have two boundaries for a group you
simply divide that group into two halves.Continue until the groups are
small enough. That's where the "N=10" comes into play.
You might be able to craft datasets that behave horribly under this
algorithm, but "natural" datashets will quickly be divided up into
small groupw. Small enough that testing inside a group
For the "not both points in one portion of the plane", you'd have to
check them against the LOG (N) regions that the algorithm has chosen.
Roger.
--
** R.E.Wolff@BitWizard.nl ** https://www.BitWizard.nl/ ** +31-15-2049110 **
** Delftechpark 11 2628 XJ Delft, The Netherlands. KVK: 27239233 **
f equals m times a. When your f is steady, and your m is going down
your a is going up. -- Chris Hadfield about flying up the space shuttle.

AM

Adrian Mariano

Sun, Jan 28, 2024 1:53 PM

The original poster wasn't clear on what sort of solution was sought

regarding polygons that intersect themselves.

THe BOSL2 library has a debug_polygon() module that displays point number

(like David shows above), which would aid in manual redesign of the

polygon. If more automated solutions are of interest BOSL2 has:

https://github.com/BelfrySCAD/BOSL2/wiki/paths.scad#function-is_path_simple

which will tell you if a polygon self-intersects (like what Rogier

describes), and then these functions that will cut the polygon at self

intersections, returning a list of parts:

https://github.com/BelfrySCAD/BOSL2/wiki/paths.scad#function-split_path_at_self_crossings

https://github.com/BelfrySCAD/BOSL2/wiki/paths.scad#function-polygon_parts

On Sun, Jan 28, 2024 at 7:52 AM Rogier Wolff via Discuss <

discuss@lists.openscad.org> wrote:

On Sun, Jan 28, 2024 at 12:00:39PM +0000, Raymond West via Discuss wrote:

Hi Nathan,

if you draw a straight line in any direction from a point inside a

polygon

it will cross the boundary an odd number of times. I'm not sure, but if

you

are testing a point that is on a boundary, you can go in two opposite

directions, and if the lines cross the boundary an even number of times

then

that point is on an inclusion. Maybe that helps?

He asked for an efficient way... Drawing an infinite number of lines

is considered "not efficient" by many programmers....

Write every segment of your polygon as A + a(B-A) where B and A are the

endpoints The small a is a parameter from 0 to 1.

Now, to check if AB intersects CD, you do this for both lines, (use b

as the parameter beteween CD). Now find the intersection of the two

lines: Calculate a and b when A + a(B-A) = C + b(D-C) . Now if a and b

are both between 0 and one you have an intersection. if either is not

inside that range, the segements do not cross. (If a is inside the

0 - 1 range and b is not, the extension of CD will intersect AB,

but for our purpose that is not crossing. Same holds other way around).

If you get a division by zero while calculating a and b, the segments

are parallel. There are a few side-cases that might be important here.

Say AB = ((0,0) - (1,0)) and CD is ((2,0)-3,0)) These do not intersect.

But swap B and C and they do!

```
Roger.
```

Best wishes,

Ray

On 28/01/2024 03:36, Nathan Sokalski via Discuss wrote:

When generating the points for a polygon (or more often modifying

them),

I sometimes end up creating a perimeter that intersects itself, which

displays what looks sort of like multiple polygons. Detecting these

intersections & modifying the list of points can sometimes be very

tedious, since determining which one is the one I want is an impossible

task. Does anybody have any suggestions on the most efficient way to do

this?

Nathan Sokalski

njsokalski@hotmail.com

OpenSCAD mailing list

To unsubscribe send an email todiscuss-leave@lists.openscad.org

--

** R.E.Wolff@BitWizard.nl ** https://www.BitWizard.nl/ ** +31-15-2049110

**

** Delftechpark 11 2628 XJ Delft, The Netherlands. KVK: 27239233 **

f equals m times a. When your f is steady, and your m is going down

your a is going up. -- Chris Hadfield about flying up the space shuttle.

OpenSCAD mailing list

To unsubscribe send an email to discuss-leave@lists.openscad.org

The original poster wasn't clear on what sort of solution was sought
regarding polygons that intersect themselves.
THe BOSL2 library has a debug_polygon() module that displays point number
(like David shows above), which would aid in manual redesign of the
polygon. If more automated solutions are of interest BOSL2 has:
https://github.com/BelfrySCAD/BOSL2/wiki/paths.scad#function-is_path_simple
which will tell you if a polygon self-intersects (like what Rogier
describes), and then these functions that will cut the polygon at self
intersections, returning a list of parts:
https://github.com/BelfrySCAD/BOSL2/wiki/paths.scad#function-split_path_at_self_crossings
https://github.com/BelfrySCAD/BOSL2/wiki/paths.scad#function-polygon_parts
On Sun, Jan 28, 2024 at 7:52 AM Rogier Wolff via Discuss <
discuss@lists.openscad.org> wrote:
> On Sun, Jan 28, 2024 at 12:00:39PM +0000, Raymond West via Discuss wrote:
> > Hi Nathan,
> >
> >
> > if you draw a straight line in any direction from a point inside a
> polygon
> > it will cross the boundary an odd number of times. I'm not sure, but if
> you
> > are testing a point that is on a boundary, you can go in two opposite
> > directions, and if the lines cross the boundary an even number of times
> then
> > that point is on an inclusion. Maybe that helps?
>
> He asked for an efficient way... Drawing an infinite number of lines
> is considered "not efficient" by many programmers....
>
> Write every segment of your polygon as A + a(B-A) where B and A are the
> endpoints The small a is a parameter from 0 to 1.
>
> Now, to check if AB intersects CD, you do this for both lines, (use b
> as the parameter beteween CD). Now find the intersection of the two
> lines: Calculate a and b when A + a(B-A) = C + b(D-C) . Now if a and b
> are both between 0 and one you have an intersection. if either is not
> inside that range, the segements do not cross. (If a is inside the
> 0 - 1 range and b is not, the extension of CD will intersect AB,
> but for our purpose that is not crossing. Same holds other way around).
>
> If you get a division by zero while calculating a and b, the segments
> are parallel. There are a few side-cases that might be important here.
> Say AB = ((0,0) - (1,0)) and CD is ((2,0)-3,0)) These do not intersect.
> But swap B and C and they do!
>
> Roger.
>
>
> >
> >
> > Best wishes,
> >
> >
> > Ray
> >
> >
> >
> > On 28/01/2024 03:36, Nathan Sokalski via Discuss wrote:
> > > When generating the points for a polygon (or more often modifying
> them),
> > > I sometimes end up creating a perimeter that intersects itself, which
> > > displays what looks sort of like multiple polygons. Detecting these
> > > intersections & modifying the list of points can sometimes be very
> > > tedious, since determining which one is the one I want is an impossible
> > > task. Does anybody have any suggestions on the most efficient way to do
> > > this?
> > >
> > > Nathan Sokalski
> > > njsokalski@hotmail.com
> > >
> > > _______________________________________________
> > > OpenSCAD mailing list
> > > To unsubscribe send an email todiscuss-leave@lists.openscad.org
>
> > _______________________________________________
> > OpenSCAD mailing list
> > To unsubscribe send an email to discuss-leave@lists.openscad.org
>
>
> --
> ** R.E.Wolff@BitWizard.nl ** https://www.BitWizard.nl/ ** +31-15-2049110
> **
> ** Delftechpark 11 2628 XJ Delft, The Netherlands. KVK: 27239233 **
> f equals m times a. When your f is steady, and your m is going down
> your a is going up. -- Chris Hadfield about flying up the space shuttle.
> _______________________________________________
> OpenSCAD mailing list
> To unsubscribe send an email to discuss-leave@lists.openscad.org
>

AM

Adrian Mariano

Sun, Jan 28, 2024 2:17 PM

The challenge of implementing fast algorithms in OpenSCAD is that they tend

to require data structures that cannot be implemented efficiently. The

standard algorithm for the problem of locating all self-intersections is

https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm but it

requires a priority queue and binary search tree.

I am wondering if your proposed algorithm can be implemented efficiently.

I would say that rather than dividing on fixed coordinates you should

divide based on the span of the data, so divide the X range in half, then

divide Y range in half, and recursively continue until the number of points

in a set is small enough. The question then arises of whether the run

time will be noticeably improved for data sets of plausible size. The

brute force algorithm for me (with a very fast computer) takes 0.4s on a

point list of 1000 points. This is not fast, but if you are doing it just

one time, it is fast enough. Someone hand-designing a polygon probably

has fewer than 1000 points.

On Sun, Jan 28, 2024 at 8:52 AM Rogier Wolff via Discuss <

discuss@lists.openscad.org> wrote:

On Sun, Jan 28, 2024 at 01:51:33PM +0100, Rogier Wolff via Discuss wrote:

On Sun, Jan 28, 2024 at 12:00:39PM +0000, Raymond West via Discuss wrote:

Hi Nathan,

if you draw a straight line in any direction from a point inside a

polygon

it will cross the boundary an odd number of times. I'm not sure, but

if you

are testing a point that is on a boundary, you can go in two opposite

directions, and if the lines cross the boundary an even number of

times then

that point is on an inclusion. Maybe that helps?

is considered "not efficient" by many programmers....

endpoints The small a is a parameter from 0 to 1.

as the parameter beteween CD). Now find the intersection of the two

lines: Calculate a and b when A + a(B-A) = C + b(D-C) . Now if a and b

are both between 0 and one you have an intersection. if either is not

inside that range, the segements do not cross. (If a is inside the

0 - 1 range and b is not, the extension of CD will intersect AB,

but for our purpose that is not crossing. Same holds other way around).

are parallel. There are a few side-cases that might be important here.

Say AB = ((0,0) - (1,0)) and CD is ((2,0)-3,0)) These do not intersect.

But swap B and C and they do!

P.S.

This would be O(N^2)... which might lead to unacceptable runtimes for large

datasets.

If you want to improve on that, declare say N= 10 a small enough numer

that N^2 runtime is acceptable.

Divide the plane into two: x>0 and x<0. Divide the line segments into

three groups: Both enpoints in in one half, both endpoints into the

other half and "spans both halves". regretably we can't do much about

that last group. Repeat dividing into two/three classes by first

repeating this for Y and then e.g. using x=1 as a divider, Then for

the class "bigger than every divider before this" you continue

multiplying by two, and once you have two boundaries for a group you

simply divide that group into two halves.Continue until the groups are

small enough. That's where the "N=10" comes into play.

You might be able to craft datasets that behave horribly under this

algorithm, but "natural" datashets will quickly be divided up into

small groupw. Small enough that testing inside a group

For the "not both points in one portion of the plane", you'd have to

check them against the LOG (N) regions that the algorithm has chosen.

```
Roger.
```

** R.E.Wolff@BitWizard.nl ** https://www.BitWizard.nl/ ** +31-15-2049110

**

** Delftechpark 11 2628 XJ Delft, The Netherlands. KVK: 27239233 **

f equals m times a. When your f is steady, and your m is going down

your a is going up. -- Chris Hadfield about flying up the space shuttle.

OpenSCAD mailing list

To unsubscribe send an email to discuss-leave@lists.openscad.org

The challenge of implementing fast algorithms in OpenSCAD is that they tend
to require data structures that cannot be implemented efficiently. The
standard algorithm for the problem of locating all self-intersections is
https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm but it
requires a priority queue and binary search tree.
I am wondering if your proposed algorithm can be implemented efficiently.
I would say that rather than dividing on fixed coordinates you should
divide based on the span of the data, so divide the X range in half, then
divide Y range in half, and recursively continue until the number of points
in a set is small enough. The question then arises of whether the run
time will be noticeably improved for data sets of plausible size. The
brute force algorithm for me (with a very fast computer) takes 0.4s on a
point list of 1000 points. This is not fast, but if you are doing it just
one time, it is fast enough. Someone hand-designing a polygon probably
has fewer than 1000 points.
On Sun, Jan 28, 2024 at 8:52 AM Rogier Wolff via Discuss <
discuss@lists.openscad.org> wrote:
> On Sun, Jan 28, 2024 at 01:51:33PM +0100, Rogier Wolff via Discuss wrote:
> > On Sun, Jan 28, 2024 at 12:00:39PM +0000, Raymond West via Discuss wrote:
> > > Hi Nathan,
> > >
> > >
> > > if you draw a straight line in any direction from a point inside a
> polygon
> > > it will cross the boundary an odd number of times. I'm not sure, but
> if you
> > > are testing a point that is on a boundary, you can go in two opposite
> > > directions, and if the lines cross the boundary an even number of
> times then
> > > that point is on an inclusion. Maybe that helps?
> >
> > He asked for an efficient way... Drawing an infinite number of lines
> > is considered "not efficient" by many programmers....
> >
> > Write every segment of your polygon as A + a(B-A) where B and A are the
> > endpoints The small a is a parameter from 0 to 1.
> >
> > Now, to check if AB intersects CD, you do this for both lines, (use b
> > as the parameter beteween CD). Now find the intersection of the two
> > lines: Calculate a and b when A + a(B-A) = C + b(D-C) . Now if a and b
> > are both between 0 and one you have an intersection. if either is not
> > inside that range, the segements do not cross. (If a is inside the
> > 0 - 1 range and b is not, the extension of CD will intersect AB,
> > but for our purpose that is not crossing. Same holds other way around).
> >
> > If you get a division by zero while calculating a and b, the segments
> > are parallel. There are a few side-cases that might be important here.
> > Say AB = ((0,0) - (1,0)) and CD is ((2,0)-3,0)) These do not intersect.
> > But swap B and C and they do!
>
> P.S.
>
> This would be O(N^2)... which might lead to unacceptable runtimes for large
> datasets.
>
> If you want to improve on that, declare say N= 10 a small enough numer
> that N^2 runtime is acceptable.
>
> Divide the plane into two: x>0 and x<0. Divide the line segments into
> three groups: Both enpoints in in one half, both endpoints into the
> other half and "spans both halves". regretably we can't do much about
> that last group. Repeat dividing into two/three classes by first
> repeating this for Y and then e.g. using x=1 as a divider, Then for
> the class "bigger than every divider before this" you continue
> multiplying by two, and once you have two boundaries for a group you
> simply divide that group into two halves.Continue until the groups are
> small enough. That's where the "N=10" comes into play.
>
> You might be able to craft datasets that behave horribly under this
> algorithm, but "natural" datashets will quickly be divided up into
> small groupw. Small enough that testing inside a group
>
> For the "not both points in one portion of the plane", you'd have to
> check them against the LOG (N) regions that the algorithm has chosen.
>
> Roger.
>
> --
> ** R.E.Wolff@BitWizard.nl ** https://www.BitWizard.nl/ ** +31-15-2049110
> **
> ** Delftechpark 11 2628 XJ Delft, The Netherlands. KVK: 27239233 **
> f equals m times a. When your f is steady, and your m is going down
> your a is going up. -- Chris Hadfield about flying up the space shuttle.
> _______________________________________________
> OpenSCAD mailing list
> To unsubscribe send an email to discuss-leave@lists.openscad.org
>

RW

Raymond West

Sun, Jan 28, 2024 7:37 PM

It's not an infinite number of lines. It is one line for each point

under consideration. If the points of the polygon are in order, and you

select a horizontal line, say, the calculation is trivial in most cases,

although you need to check for a few exceptions, e.g a point of

inflection being on the line. That is for checking if a point lies

within a boundary.

FWIW, I first used that technique about 55 years ago, programming in IBM

fortan 4, on an IBM 1130, while working with the ordnance survey in the

early days of digitising maps, and last year, when deciding

(programmatically) if a shape generated by openscad needed pocketing or

profiling. As I mentioned, I am not sure if a similar technique would

work for an incorrect boundary, e.g. some of its boundary points are

inside the boundary. If it did, then I think the most required would be

one line though each point on the boundary, and see how often that line

line crossed the boundary at each side.

iirc, the few exceptions totalled eight.

On 28/01/2024 12:51, Rogier Wolff via Discuss wrote:

On Sun, Jan 28, 2024 at 12:00:39PM +0000, Raymond West via Discuss wrote:

Hi Nathan,

if you draw a straight line in any direction from a point inside a polygon

it will cross the boundary an odd number of times. I'm not sure, but if you

are testing a point that is on a boundary, you can go in two opposite

directions, and if the lines cross the boundary an even number of times then

that point is on an inclusion. Maybe that helps?

He asked for an efficient way... Drawing an infinite number of lines

is considered "not efficient" by many programmers....

endpoints The small a is a parameter from 0 to 1.

as the parameter beteween CD). Now find the intersection of the two

lines: Calculate a and b when A + a(B-A) = C + b(D-C) . Now if a and b

are both between 0 and one you have an intersection. if either is not

inside that range, the segements do not cross. (If a is inside the

0 - 1 range and b is not, the extension of CD will intersect AB,

but for our purpose that is not crossing. Same holds other way around).

are parallel. There are a few side-cases that might be important here.

Say AB = ((0,0) - (1,0)) and CD is ((2,0)-3,0)) These do not intersect.

But swap B and C and they do!

```
Roger.
```

Best wishes,

Ray

On 28/01/2024 03:36, Nathan Sokalski via Discuss wrote:

I sometimes end up creating a perimeter that intersects itself, which

displays what looks sort of like multiple polygons. Detecting these

intersections & modifying the list of points can sometimes be very

tedious, since determining which one is the one I want is an impossible

task. Does anybody have any suggestions on the most efficient way to do

this?Nathan Sokalski

njsokalski@hotmail.com

OpenSCAD mailing list

To unsubscribe send an email todiscuss-leave@lists.openscad.org

OpenSCAD mailing list

To unsubscribe send an email to discuss-leave@lists.openscad.org

It's not an infinite number of lines. It is one line for each point
under consideration. If the points of the polygon are in order, and you
select a horizontal line, say, the calculation is trivial in most cases,
although you need to check for a few exceptions, e.g a point of
inflection being on the line. That is for checking if a point lies
within a boundary.
FWIW, I first used that technique about 55 years ago, programming in IBM
fortan 4, on an IBM 1130, while working with the ordnance survey in the
early days of digitising maps, and last year, when deciding
(programmatically) if a shape generated by openscad needed pocketing or
profiling. As I mentioned, I am not sure if a similar technique would
work for an incorrect boundary, e.g. some of its boundary points are
inside the boundary. If it did, then I think the most required would be
one line though each point on the boundary, and see how often that line
line crossed the boundary at each side.
iirc, the few exceptions totalled eight.
On 28/01/2024 12:51, Rogier Wolff via Discuss wrote:
> On Sun, Jan 28, 2024 at 12:00:39PM +0000, Raymond West via Discuss wrote:
>> Hi Nathan,
>>
>>
>> if you draw a straight line in any direction from a point inside a polygon
>> it will cross the boundary an odd number of times. I'm not sure, but if you
>> are testing a point that is on a boundary, you can go in two opposite
>> directions, and if the lines cross the boundary an even number of times then
>> that point is on an inclusion. Maybe that helps?
> He asked for an efficient way... Drawing an infinite number of lines
> is considered "not efficient" by many programmers....
>
> Write every segment of your polygon as A + a(B-A) where B and A are the
> endpoints The small a is a parameter from 0 to 1.
>
> Now, to check if AB intersects CD, you do this for both lines, (use b
> as the parameter beteween CD). Now find the intersection of the two
> lines: Calculate a and b when A + a(B-A) = C + b(D-C) . Now if a and b
> are both between 0 and one you have an intersection. if either is not
> inside that range, the segements do not cross. (If a is inside the
> 0 - 1 range and b is not, the extension of CD will intersect AB,
> but for our purpose that is not crossing. Same holds other way around).
>
> If you get a division by zero while calculating a and b, the segments
> are parallel. There are a few side-cases that might be important here.
> Say AB = ((0,0) - (1,0)) and CD is ((2,0)-3,0)) These do not intersect.
> But swap B and C and they do!
>
> Roger.
>
>
>>
>> Best wishes,
>>
>>
>> Ray
>>
>>
>>
>> On 28/01/2024 03:36, Nathan Sokalski via Discuss wrote:
>>> When generating the points for a polygon (or more often modifying them),
>>> I sometimes end up creating a perimeter that intersects itself, which
>>> displays what looks sort of like multiple polygons. Detecting these
>>> intersections & modifying the list of points can sometimes be very
>>> tedious, since determining which one is the one I want is an impossible
>>> task. Does anybody have any suggestions on the most efficient way to do
>>> this?
>>>
>>> Nathan Sokalski
>>> njsokalski@hotmail.com
>>>
>>> _______________________________________________
>>> OpenSCAD mailing list
>>> To unsubscribe send an email todiscuss-leave@lists.openscad.org
>> _______________________________________________
>> OpenSCAD mailing list
>> To unsubscribe send an email to discuss-leave@lists.openscad.org
>

RW

Rogier Wolff

Sun, Jan 28, 2024 8:02 PM

Oops. Sorry. I didn't think that through. ANY line will suffice, you

can chose a convenient one, like horizontal as you suggested.

On Sun, Jan 28, 2024 at 07:37:51PM +0000, Raymond West via Discuss wrote:

It's not an infinite number of lines.

** R.E.Wolff@BitWizard.nl ** https://www.BitWizard.nl/ ** +31-15-2049110 **

** Delftechpark 11 2628 XJ Delft, The Netherlands. KVK: 27239233 **

f equals m times a. When your f is steady, and your m is going down

your a is going up. -- Chris Hadfield about flying up the space shuttle.

Oops. Sorry. I didn't think that through. ANY line will suffice, you
can chose a convenient one, like horizontal as you suggested.
On Sun, Jan 28, 2024 at 07:37:51PM +0000, Raymond West via Discuss wrote:
> It's not an infinite number of lines.
--
** R.E.Wolff@BitWizard.nl ** https://www.BitWizard.nl/ ** +31-15-2049110 **
** Delftechpark 11 2628 XJ Delft, The Netherlands. KVK: 27239233 **
f equals m times a. When your f is steady, and your m is going down
your a is going up. -- Chris Hadfield about flying up the space shuttle.

Replying to:

Empathy v1.0
2024 ©Harmonylists.com