The design information for a printed circuit board or semiconductor chip will include a number of copper tracks and other conductive features. Under most circumstances it will be known which tracks connect to which others, as this information will be transmitted from higher levels of abstract circuit design through to the more detailed levels of design which determine where copper is printed on a circuit board or semiconductor layer. However, this information will not be available in all circumstances. In particular where there is a need to "reverse engineer" an electronic design information about copper features may be available but not how these connect into networks. These notes explore some of the primitive geometrical algorithms which a more complete solution would require.
Reverse engineeing a printed circuit board which can contain copper polygons makes it neccessary to analyse whether a line crosses the boundary of a polygon, or whether a point is inside the copper area defined by a polygon. As it would be unusual for a line segment which is part of a track to be drawn completely inside a polygon without toucing any of the line segments forming the boundary of the polygon, this suggests that the problem can be solved by considering the polygon to be the equivalent of a track around its boundary, and using a line crossing algorithm or function to identify whether there are any crossings between the segment being checked, and any of the segments comprising the polygon boundary. A more reliable approach is available, in the sense that it is possible to discover whether a point is within the polygon, by drawing an imaginary line through the point, and working out how many crossings exist beween the polygon boundary and points to either side of the point of interest along this line. If this number of crossings is odd, the point of interest is inside the polygon and if even, it is outside.
The first approach considered, which involved an analysis of crossing points based on line algebra, turned out to have a number of special cases some of which led to potential numerical instabilities.
A coordinate is normally stored as a pair of floating point values which store the X and Y values of a single point coordinate. Mathematically, a line is considered to stretch to infinity in both directions and has zero width. A copper connection or track between 2 points can be considered to be formed from a number of line segments, typically connected at the ends, but possibly crossing anywhere along the lengths of both, and changing direction to route around obstacles. A line segment is a part of a straight line, with starting and ending coordinates.
Not all lines can be described by the same form of equation. The equation y = a + bx has a zero value for b for a horizontal line making y constant. For a vertical line y is independant of x, with b taking any value between minus and plus infinity and with x constant.
Segments are likely to be stored as pairs of XY coordinates, one for each end. To use the line equations we need to derive terms a for the point where the line crosses the y axis, and b for the line gradient from knowledge of segment end coordinates.
The gradient b is the rate at which Y changes per unit change in X:
b = (y2 - y1)/(x2 - x1)
The point a where the line crosses the y axis can then be derived from y1, x1 and a:
a = y1 - bx1
Unless 2 lines are parrallel, they will cross. Consider 2 lines describable using the equations:
Solving for y:
a + bx = c + dx (b-d)x = c - a crossing point x = (c-a)/(b-d)
Using this result to solve for x:
y = a+bx y = a + b(c-a)/(b-d)
If b = d, we get a divide by zero. This will occur if the 2 lines are parallel as the gradients are the same.
If the crossing point is within both segments, (i.e. x1 <= cpx <= x2 AND x3 <= cpx <= x4 ) then the 2 segments can be assumed to connect (if they are on the same metalisation layer of the printed circuit or semiconductor product).
Resolving the above pair of simultaneous equations can also be achieved by inverting an appropriate 2 x 2 matrix.
#include <math.h>
#define PI 3.1415923
typedef struct gcoord { /* graphical x-y coordinate */
float x;
float y;
} GCOORD;
typedef struct ccoord { /* circular coordinate */
float angle; /* angle of vector in radians anticlockwise from
X axis */
float leng; /* hypotenuese distance from x=0 y=0 origin */
} CCOORD;
typedef struct segment { /* a line segment consists of 2 coordinates */
GCOORD p1;
GCOORD p2;
} SEGMENT;
GCOORD ctog(CCOORD c); /* converts circular to graphical coordinate */
CCOORD gtoc(GCOORD g); /* converts graphical to circular coordinate */
void rotate(GCOORD *gc, float radians);
/* rotates gc by radians about origin */
void rotate(GCOORD *gc, float radians){
/* rotates gc by radians about origin */
float twopi=2*PI;
CCOORD cc;
cc=gtoc(*gc);
cc.angle+=radians;
/* normalise angle to range 0 - 2PI */
while(cc.angle < 0.0 || cc.angle > twopi){
if(cc.angle<0.0)
cc.angle+=twopi;
else
cc.angle-=twopi;
}
*gc=ctog(cc);
}
CCOORD gtoc(GCOORD g){ /* converts graphical to spherical coordinate */
CCOORD cc;
/* use pythagoras to compute vector length */
cc.leng=sqrt(g.x*g.x + g.y*g.y);
if(cc.leng<=0.0000002&&cc.leng>=-0.0000002){
/* coord on origin, length too small to risk dividing by */
cc.angle=0.0;
return cc;
}
/* all other cases, use sin-1 function to get angle */
if(g.x>=0.0){ /* +ve x, angles from -PI/2 -> PI/2 */
cc.angle=asin(g.y/cc.leng);
} else { /* -ve x, angles from PI/2 -> 3PI/2 */
cc.angle=PI-asin(g.y/cc.leng);
return cc;
}
GCOORD ctog(CCOORD cc){ /* converts spherical to graphical coordinate */
GCOORD gc;
gc.y=cos(cc.angle)*cc.leng;
gc.x=sin(cc.angle)*cc.leng;
return gc;
}
These also need to be handled seperately. These will connect if the segments touch end to end or overlap, and the difference between a and c (i.e. the y-values where the lines cross the y axis) is less than the line width.
Lines which are nearly vertical or nearly parallel also need to be handled with caution, due to the problems using floating point representations for extremely large values, resulting from division by very small values.
Further research uncovered 2 approaches which are less complex than the geometrical manipulations described above, with fewer special cases. The second approach concerns whether 2 segments with given line width electrically connect. The third uses a scanning algorithm to identify all crosses between line segments on a layer.
If the part of a segment nearest to where a cross could occur can be identified, this segment can be shortened and retested. If the part of the other segment nearest to where a cross could occur is identified next, the other segment is shortened. These tests can be carried out recursively by swapping the segments and shortening both in turn. To end the recursion, a solution can be detected either:
In the diagram, 5 distance sums a1+b1, a2+b2, a3+b3, a4+b4 and a5+b5 are compared and the shortest sum identified. Computing the distance between 2 XY coordinate pairs involves use of Pythagoras' theorem which is fast and numerically stable. The shortest sum identifies which point along segment s1 within the set p1 ... p5 is closest to a crossing point cp, should such a crossing point be found to exist. If this point is either p1 or p2, the segment s1 is shortened to a segment between p1 and p3. If this point is p3 the segment s1 is shortened to a segment between p2 and p4. Otherwise this point is either p4 or p5 and the segment s1 is shortened to a segment between p3 and p5.
This turned out to be much easier to program in practice. To save time in carrying out this investigation, the Python programming language was used.
#!/usr/bin/python
# recursive algorithm to work out if 2 line segments
# are connected, by moving towards shortest distance
# Richard Kay, April 2006
import math
# global debugging flag
debug=False
# large float
BIGFLOAT=4.0E100
class coord:
''' Does things with X-Y coordinates '''
def __init__(self,x,y):
self.x=x
self.y=y
def dist(self,another):
''' Returns distance between self and another'''
x2=math.pow(self.x-another.x,2)
y2=math.pow(self.y-another.y,2)
return math.sqrt(x2+y2)
def between(self,another,proportion):
''' returns a coordinate somewhere along
the line segment between self
and another based on a proportion between
0.0 and 1.0, e.g. if proportion is .25
it will return a coordinate one quarter
of the distance between self and another.'''
bx=self.x + (another.x - self.x)*proportion
by=self.y + (another.y - self.y)*proportion
return coord(bx,by)
def __repr__(self):
return "coordinate at X: %f Y: %f\n" % (self.x,self.y)
class segment:
def __init__(self,c1,c2,lw=0.1):
self.c1=c1 # end coordinate 1
self.c2=c2 # end coordinate 2
self.lw=lw # line width
def midpoint(self):
midx=(self.c1.x+self.c2.x)/2.0
midy=(self.c1.y+self.c2.y)/2.0
midc=coord(midx,midy)
return midc
def crosses(s1,s2):
''' returns true if s1 and s2 segment objects
cross or connect with each other '''
''' for each of 11 points spaced along the segment
s1, compute the sum of the 2 distances between
this point and the 2 endpoints of segment s2 '''
distances=[]
distances.append(s1.c1.dist(s2.c1)+s1.c1.dist(s2.c2))
for step in range(1,10): # integers in range from 1 to 9 inclusive
proportion=step/10.0
point=s1.c1.between(s1.c2,proportion)
distances.append(point.dist(s2.c1)+point.dist(s2.c2))
distances.append(s1.c2.dist(s2.c1)+s1.c2.dist(s2.c2))
if debug:
for di in distances:
print "%.2f " % (di),
print
# find minimum out of 11 distances
min=BIGFLOAT
minidx=0
for i in range(11): # indexes 0 - 10
if distances[i]<min:
min=distances[i]
minidx=i
if debug:
print "minimum: ",min
print "minindex: ",minidx
if min < s1.lw+s2.lw: # this proves s1 and s2 are connected
# so further recursion is not needed
return True
elif s1.c1.dist(s1.c2) + s2.c1.dist(s2.c2) < min:
# min dist between 2 segs greater than combined
# length so it is impossible for s1 and s2 to cross
return False
''' Otherwise, reduce segment s1 to 3 points from or
on either side of the point at the minimum distance. '''
if minidx <= 1:
ns1c1=s1.c1
ns1c2=s1.c1.between(s1.c2,0.2)
elif minidx >= 9:
ns1c1=s1.c1.between(s1.c2,0.8)
ns1c2=s1.c2
else:
ns1c1=s1.c1.between(s1.c2,(minidx-1)/10.0)
ns1c2=s1.c1.between(s1.c2,(minidx+1)/10.0)
# create new shortened segment 1
ns1=segment(ns1c1,ns1c2)
# now call crosses recursively, swapping s1 and s2 over
return crosses(s2,ns1)
def test():
global debug
debug=True
tests=[ # add a record to this array for each test
# test 0, vertical crossed by diag
{'tno':0,'expected':'connected',
'c1':coord(0,0),'c2':coord(0,10),
'c3':coord(-2,5),'c4':coord(5,5)},
# test 1, vertical uncrossed by diag
{'tno':1,'expected':'unconnected',
'c1':coord(0,0),'c2':coord(0,10),
'c3':coord(-4,5),'c4':coord(-0.2,9)},
# test 2, right angles joined at corner
{'tno':2,'expected':'connected',
'c1':coord(0,0),'c2':coord(0,10),
'c3':coord(0,10),'c4':coord(10,10)},
# test 3, horizontals joined at ends
{'tno':3,'expected':'connected',
'c1':coord(0,0),'c2':coord(0,10),
'c3':coord(0,10),'c4':coord(0,20)}
]
for t in tests:
print 'test number: %d' % t['tno']
s1=segment(t['c1'],t['c2'])
s2=segment(t['c3'],t['c4'])
if crosses(s1,s2):
print "cross or connection detected"
else:
print "cross or connection not detected"
print 'Expected result: %s' % t['expected']
raw_input("press enter to continue")
if __name__ == '__main__': # true when run, false when imported
test()
python recurx.py test number: 0 12.46 10.88 9.44 8.21 7.34 7.00 7.34 8.21 9.44 10.88 12.46 minimum: 7.0 minindex: 5 4.47 3.28 2.33 2.01 2.56 3.61 4.83 6.14 7.47 8.83 10.20 minimum: 2.00997512422 minindex: 3 2.45 2.13 1.85 1.62 1.46 1.40 1.46 1.62 1.85 2.13 2.45 minimum: 1.4 minindex: 5 1.26 1.00 0.75 0.54 0.41 0.45 0.62 0.86 1.11 1.38 1.65 minimum: 0.407921561087 minindex: 4 0.49 0.43 0.37 0.33 0.29 0.28 0.29 0.33 0.37 0.43 0.49 minimum: 0.28 minindex: 5 0.37 0.31 0.26 0.21 0.16 0.11 0.08 0.09 0.12 0.16 0.22 minimum: 0.0835224520713 minindex: 6 cross or connection detected Expected result: connected press enter to continue test number: 1 15.41 13.66 12.00 10.48 9.13 8.00 7.13 6.48 6.02 5.86 7.42 minimum: 5.85685424949 minindex: 9 11.40 10.31 9.22 8.14 7.06 5.99 4.94 3.93 3.02 2.35 2.04 minimum: 2.03960780544 minindex: 10 2.00 1.78 1.61 1.49 1.41 1.45 1.67 1.98 2.33 2.69 3.06 minimum: 1.41492044832 minindex: 4 2.29 2.08 1.87 1.67 1.47 1.28 1.11 0.95 0.81 0.71 0.65 minimum: 0.6472135955 minindex: 10 0.87 0.82 0.76 0.72 0.67 0.64 0.61 0.59 0.58 0.58 0.59 minimum: 0.575853238117 minindex: 9 0.75 0.71 0.67 0.63 0.60 0.56 0.53 0.50 0.47 0.44 0.42 minimum: 0.415406592285 minindex: 10 cross or connection not detected Expected result: unconnected press enter to continue test number: 2 24.14 22.45 20.81 19.21 17.66 16.18 14.77 13.44 12.20 11.05 10.00 minimum: 10.0 minindex: 10 2.00 3.24 4.83 6.61 8.47 10.39 12.32 14.28 16.25 18.22 20.20 minimum: 2.0 minindex: 0 4.83 4.49 4.16 3.84 3.53 3.24 2.95 2.69 2.44 2.21 2.00 minimum: 2.0 minindex: 10 0.40 0.65 0.97 1.32 1.69 2.08 2.46 2.86 3.25 3.64 4.04 minimum: 0.4 minindex: 0 0.97 0.90 0.83 0.77 0.71 0.65 0.59 0.54 0.49 0.44 0.40 minimum: 0.4 minindex: 10 0.08 0.13 0.19 0.26 0.34 0.42 0.49 0.57 0.65 0.73 0.81 minimum: 0.08 minindex: 0 cross or connection detected Expected result: connected press enter to continue test number: 3 30.00 28.00 26.00 24.00 22.00 20.00 18.00 16.00 14.00 12.00 10.00 minimum: 10.0 minindex: 10 2.00 4.00 6.00 8.00 10.00 12.00 14.00 16.00 18.00 20.00 22.00 minimum: 2.0 minindex: 0 6.00 5.60 5.20 4.80 4.40 4.00 3.60 3.20 2.80 2.40 2.00 minimum: 2.0 minindex: 10 0.40 0.80 1.20 1.60 2.00 2.40 2.80 3.20 3.60 4.00 4.40 minimum: 0.4 minindex: 0 1.20 1.12 1.04 0.96 0.88 0.80 0.72 0.64 0.56 0.48 0.40 minimum: 0.4 minindex: 10 0.08 0.16 0.24 0.32 0.40 0.48 0.56 0.64 0.72 0.80 0.88 minimum: 0.08 minindex: 0 cross or connection detected Expected result: connected press enter to continue
Approach 2 is capable of being applied to find crossing points for N segments if each is compared against all the remaining. The above algorithm would normally be applied N-1 x N-2 x N-3 .... x 3 x 2 or ON2 times.
Wikipedia's current (May 2006) article on line scanning algorithms includes the following:
In computational geometry, the line segment intersection problem supplies a list of line segments in the plane and asks us to determine whether any two of them intersect, or cross.
Naive algorithms examine each pair of segments, but this is highly inefficient, since most pairs of segments aren't anywhere close to one another in a typical input sequence. The most common, more efficient way to solve this problem is to use a sweep line algorithm, where we imagine a line sliding across the line segments and we track which line segments it intersects at each point in time using a dynamic data structure based on self-balancing binary search trees.
References
* Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000). Computational Geometry, 2nd edition, Springer. ISBN 3540656200. Chapter 2: Line Segment Intersection, pp.19–44. * Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 1990. ISBN 0262032937. Section 33.2: Determining whether any pair of segments intersects, pp.934–947. * J. L. Bentley and T. Ottmann., Algorithms for reporting and counting geometric intersections, IEEE Trans. Comput. C28 (1979), 643–647.
This article also references a Java animationTW = TrackWidth Maxx = maximum value of X for all lines Xscan = Minx // start position of vertical scan line Sidx=0 // index of array of StartedX1 lines Eidx=0 // index of array of EndedX2 lines While Xscan < Max_x: Increment Xscan // small increment (suggest trackwidth) While StartedX1[Sidx].x1 < Xscan AND Sidx<NoLines: Sidx++ Add StartedX1[Sidx].track to Scanning List in Crossing Y Point (CYP) sort order While EndedX2[Eidx].x1 < Xscan AND EidX<NoLines: Eidx++ Remove EndedX1[Eidx].track from Scanning List For tracks in Scanning List: Update CYP If Update increased CYP: If CYP > CYP of next track in Scanning list: Report cross Swap tracks to maintain sort If Update reduced CYP: If CYP < CYP of prev track in Scanning list: Report cross Swap tracks to maintain sort Identify Set of Close Vertical Tracks (SCVT) in Vertical Tracks list based on ScanX and TW For each Vertical Track in SCVT list: For every other Vert Track (OVT) in SCVT list: If ABS(VT.X - OVT.X) < TW AND ((VT.Y1 <= OVT.Y1 AND VT.Y2>=OVT.Y1) OR (VT.Y1 <= OVT.Y2 AND VT.Y2>=OVT.Y2)) Report cross For tracks in Scanning List: If VT.Y1 <= CYP AND VT.Y2 >= CYP Report cross
For all Tracks: If No Net number yet Assigned: Assign next netnumber Push onto Stack Until Stack empty Pop track For all other tracks without netnumbers: If other track crosses popped track Assign netnumber Push it