Re: [CAD_CAM_EDM_DRO] Geometric functions / TurboCAD CAM plugin

JJ,

Look at the "Geometric Intersection" chapter in Sedgewick, if you
haven't already. It deals with exactly this problem.

You can also do a web search for "geometric intersection", or
"computational geometry" to find more references and maybe even some
existing code.

The short version is that brute-force checking each line against all
other lines is a losing battle. The time required goes up with N^2,
where N is the number of lines.

You need to sort the lines in some way so you can quickly find only the
potential intersections and check those. Sedgewick describes sorting the
lines into a tree. Another approach is to break the area of interest
into a grid of rectangular cells and record which lines fall
in/through/near which cells.

Andy Anderson

John Johnson wrote:

>...
>
> What I need for the moment, however, is a good line intersection
> algorithm. Not for lines of a given slope will intersect at (x, y), but
> does this line intersect any of these other lines, and possibly where.
> I'm working my way through Algorithms by Sedgewick now, but it's an
> uphill battle.
>