### Avoiding Intersecting Lines in a Polygon Perimeter

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 <

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

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:

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

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:

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

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

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    **

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    **

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

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:

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

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

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

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    **

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

AM
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 <

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    **

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....

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

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

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    **