kicad-developers team mailing list archive

[Dick Hollenbeck <dick@...>]

> Hi. What if all polygons will be represented as a set of triangles?
> In order to fill a polygon along the filling proccess we need to
> perform a check operation (check if a point is inside of the polygon
> or not). There is no universal rule to do this check. In case of an
> arbitrary polygon it is necessary to split it into convex polygons or
> in the simplest case into triangles. After that a simple rule can be
> used to check if a point is inside of triangle or not. If given point
> is inside of at least one triangle then the point is inside of the
> polygon to be filled.
> This check operation can be used also for all cutout polygons such as
> cutouts, pads, vias, traces and other polygons not belonged to the net
> name which the polygon to be filled is connected.
> Also to form gerber files the triangles can be used instead of
> multiple concave polygons (as said polygons with holes must not used
> in gerber).
> Thus I think it is reasonable to represent polygons as a set of triangles.
>
> Alexander Lunev
Alexander,

Your idea seems to have some applicability, but at the very lowest 
levels. Jean-Pierre is doing research and found some libraries that can 
decompose a polygon into triangles. He already gave the link to such a 
library, and I am sure there are others. I repeat it here:

http://www.cs.man.ac.uk/~toby/alan/software/gpc.html

Having said this, the most effective design of this will not start at 
the bottom and work its way up. Instead it will be done by describing 
the needed algorithms at the top and working down. If I were doing it, 
I would describe those algorithms in English (psuedo code) not even 
using C++ at first. 

Really, managing triangles throughout the process would be a pain. The 
triangles are maybe needed only at gerber generation time. 

If you were going to design a new spoken language, would you say, hey, 
"let's base the language on these specific letters"? No, you would 
start at concepts, then sentences, then words, then letters. Why define 
the letters until you know what sounds you need to produce in the 
words? Why define the words until you know what roles they will play in 
the sentences? Why define the sentences until you know what concepts 
need to be communicated? Top -> down.

To continue, much of the existing code is probably more of a hindrance 
than a help in this respect, because it tends to pull your thinking too 
close to the low level details, too early. The existing code in 
fraught with details that obscure the core algorithms. Linked list 
management is being done in line, rather than using tried and true black 
boxes, i.e. library code that we know simply works.


Having said this, in summary, I think your idea is a good one!

I write this response for the benefit of the project, not to be critical 
of an idea that is probably before its time. I would just like the 
discussion to start at the top.


Dick Hollenbeck
SoftPLC Corporation
http://softplc.com