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:

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:

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:

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

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.  

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

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.

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:

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:

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:

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:

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