kicad-developers team mailing list archive

[jean-pierre charras - INPG <jean-pierre.charras@...>]

Dick Hollenbeck a écrit :
> > To use the zone filling in connectivity calculations, only a volunteer
> > is needed to create 2 or 3 functions which test zone segments 
> connectivity.
> > Tim, currently, you cannot be this volunteer because you have work 
> about
> > eeschema.
> > Dick i believe you are not volunteer (am I right ?)
> > And i am busy...
> >
> > But if a volunteer exists, i could help it to start the work.
> >
>
> Jean-Pierre,
>
> It is good that you are communicating well. I had the impression that
> you were working on the whole group of continuity testing primitives.
> So we are making progress in learning that you are willing to let
> someone else move into that role.
This is true.
> As we discussed, currently the "end point" matching on tracks is an
> inadequate test of electrical continuity. What is your starting
> point? Please put a list together and summarize which functions are
> the building blocks if any that you have, so that no duplication of work
> takes place. I would like to look at that before I make any commitments.
>
> Once we have those continuity testing primitives, then we can experiment
> with how to employ them.
>
> The primitives work on following objects:
>
> tracks, pads, via, and zones. Allow me to use "zone" in an abstract
> sense for a moment.
>
> So we have to test continuity between:
>
> track to track (present test is inadequate)
> track to pad (present test is inadequate)
> track to via (present test is inadequate)
> track to zone (no test exists)
>
> pad to pad (no test exists)
> pad to via (no test exists, but log is same as pad to pad)
> pad to zone (no test exists)
>
> via to via (no test exists, but like pad to pad)
> via to zone (no test exists, but like pad to zone)
>
> zone to zone (test exists in polygon library, needs wrapper)
>
> anything missed here?
>
> I had made some remarks earlier about having a series of BOARD_ITEM
> functions, such as
>
> bool TRACK::ConnectsTo( TRACK* )
> bool TRACK::ConnectsTo( PAD* )
>
> bool ZONE::ConnectsTo( TRACK* ) (remember ZONE is abstract here!)
>
> etc.
>
> If we had those, we could re-arrange the current code to use them
> immediately. Client code and test primitive implementation could be
> done by two different people, concurrently. In fact for track to track
> testing, the old endpoint tests could be used for a short term, wrapped
> in the new wrapper: bool TRACK::ConnectsTo( TRACK*) . And in that
> short term, the client code can be architected to sit on top of
> TRACK::ConnectsTo( TRACK*) rather than
>
> if track1.start == track2.start || track1.start == track2.end ||
> track1.end == track2.start || track1.end == track2.end
>
> This becomes:
>
> if( track1.ConnectsTo( track2 ) )
>
> In addition to the ConnectsTo() family of primitives, we might need a
> function which returns the nearest point of a polygon:
>
> wxPoint ZONE::GetNearestPoi nt( wxPoint fromHere )
>
> This one would help in the ratsnest drawing and give the shortest path.
Obviously, current test need to be enhanced.
Be careful.
In these applications, time calculation is a problem.
there are 2 classes of algorithms (assuming we must test n items):
Algos which increase time as nlog(n)
Algos which increase time as n*n (compare each item which each other)

** Only nlog(n) algos are useable. **
Often they use sorted lists.
the track to pad test uses a sorted by increasing x value list of pads 
and a dichotomy search.
this is easy when testing only track end points
Enhanced dichotomy search using the track end points and whole pad shape 
is not so complex.
(one can search before, and after the better pad candidate, restricted 
to its neighbour (from x - bigger pad size to x + bigger pad size) )
Enhanced dichotomy search using the entire track ot pad must be possible,
using 2 sorted pad list (sorted by X and sorted by Y) and using the best 
list for horizontal and vertical tracks.
This is more tricky for other tracks (but 45 degrees (or other) tracks 
are less numerous, and usually short)

Track to track is more difficult.
An exhaustive test (n*n algo) could cost hours of computing time on 
large designs.
Faster PC do not solve the problem because PC and faster and faster, but 
designs are more and more complex!

> Your offer to give direction is being accepted by me, but before you
> have a volunteer.
>
> Thanks,
>
> Dick
Your offer is accepted.

--
Jean-Pierre CHARRAS
Maître de conférences
Directeur d'études 2ieme année.
Génie Electrique et Informatique Industrielle 2
Institut Universitaire de Technologie 1 de Grenoble
BP 67, 38402 St Martin d'Heres Cedex

Recherche :
Grenoble Image Parole Signal Automatique (GIPSA - INPG)
46, Avenue Félix Viallet
38031 Grenoble Cedex