## Newbie Qtn: Building 2D boundary list

### Newbie Qtn: Building 2D boundary list

Hi all,

I'm new to this NG and I'm not completely sure whether this is the

I have a list of simple closed 2D polygons (boundaries) made up of
line and arc segments. I want to parse this list and combine all the
polygons to produce a union of all these objects. Which would result
in a list of closed polygons possibly with holes. I can define a
outside bounding rectangle if that would simplify the process.

Any suggestions, I can probably work out some sort of algorithm to do
this, though I doubt it would be anywhere near optimal, if anyone
would like to point me in a particular direction please go ahead.

The reason why I'm doing this is because we have a quick circuit PCB
prototyping milling machine (http://www.t-tech.com/)that comes with
software called isopro, although it works alright, we would like to
have far more control over the milling path (in the old DOS days the
actual isolation algorithm worked better than it does today, however,
it now has a lot of pretty GUI stuff as replacement). The milling
machine works by starting with a PCB completely covered with copper
and milling (drilling if you like) away the unrequired copper.

To do that we need to parse the gerber files which represents the
areas of copper on the PCB & then generate an isolation path based on
a filling algorithm.

Parsing the gerber file is fairly easy, this file defines what's
called draws & flashes. A draw is a closed circle that dragged from
point 1 to point 2 creating a closed polygon with two lines and two
half circles. A flash is just a shape (a rectangle or circle) drawn at
a point.

So the polygons representing draws & flashes are the initial data
structure that I want to union all together generating an object that
represents the copper area on the PCB that will be left after milling.

BTW, I'll be using Python to initially implement this application, and
if speed is an issue, I'll profile it and "hardcode" the more critical
bits.

### Newbie Qtn: Building 2D boundary list

Found part of the solution in another post on polygon subtaction

The algorithm is partially designed by Micahel Leonov,
http://members.nbci.com/msleonov/.

>Hi all,

>I'm new to this NG and I'm not completely sure whether this is the

>I have a list of simple closed 2D polygons (boundaries) made up of
>line and arc segments. I want to parse this list and combine all the
>polygons to produce a union of all these objects. Which would result
>in a list of closed polygons possibly with holes. I can define a
>outside bounding rectangle if that would simplify the process.

>Any suggestions, I can probably work out some sort of algorithm to do
>this, though I doubt it would be anywhere near optimal, if anyone
>would like to point me in a particular direction please go ahead.

>The reason why I'm doing this is because we have a quick circuit PCB
>prototyping milling machine (http://www.t-tech.com/)that comes with
>software called isopro, although it works alright, we would like to
>have far more control over the milling path (in the old DOS days the
>actual isolation algorithm worked better than it does today, however,
>it now has a lot of pretty GUI stuff as replacement). The milling
>machine works by starting with a PCB completely covered with copper
>and milling (drilling if you like) away the unrequired copper.

>To do that we need to parse the gerber files which represents the
>areas of copper on the PCB & then generate an isolation path based on
>a filling algorithm.

>Parsing the gerber file is fairly easy, this file defines what's
>called draws & flashes. A draw is a closed circle that dragged from
>point 1 to point 2 creating a closed polygon with two lines and two
>half circles. A flash is just a shape (a rectangle or circle) drawn at
>a point.

>So the polygons representing draws & flashes are the initial data
>structure that I want to union all together generating an object that
>represents the copper area on the PCB that will be left after milling.

>BTW, I'll be using Python to initially implement this application, and
>if speed is an issue, I'll profile it and "hardcode" the more critical
>bits.

I need to describe 2D objects using what Samet calls the boundary
model (He describes this for modeling 3D solids). It seems to me that I can
use analagous model for 2D using edges, vertices, polygons and no faces. I am
starting to work on this subject and I would appreciate if some one can give
some pointers to algorithms/code/references/data-structures that I could use
to understand how it works.