← Back to team overview

kicad-developers team mailing list archive

Re: Re: problems after draggin a footprint

 

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








References