Mail Archives: geda-user/2013/08/19/15:09:16
On Mon, 2013-08-19 at 13:15 -0400, Stephen R. Besch wrote:
[...]
>
> There's a lesson in there somewhere. If you are going to rely on the
> internet for an education in basic algebra, I suspect that you will more
> often than not get what you pay for. It is almost always better to do
> your own math and avoid both the problems with others poor math skills
> as well as their poor programming skills. By the way, for simple
> straight line segments, ...
Thank you very much for your help -- it is good to know that there is at
least one math expert on this list (I am sure there are more, but they
may be very busy -- at least all other smart math guys I know are very,
very busy.)
Indeed intersection of lines is a very simple problem, intersection of
line segments too, if you only need a boolean answer. If you need the
point of intersection it is a little bit more complicated.
Doing the math myself is an good advice -- but I have to admit that I am
not very good in it. One basic problem for my topological router was
finding the tangents for two circles -- I did one or two hours of
thinking, but got no solution. Then I asked Google, found this,
http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Tangents_between_two_circles
and spent one or two hours verifying it.
Yes, trying harder to find such solutions myself would be a good idea,
but of course my time is limited, and I wish of course to have the best
solution, i.e. fast and numerical stable.
A similar problem is finding the distance of a point to a line segment
-- http://www.geometrictools.com/ provides a fine solution:
# (c)
# /
# / (p)
# /
# (b)
# see http://www.geometrictools.com/
# see also http://paulbourke.net/geometry/pointlineplane/
def distance_line_segment_point_squared(bx, by, cx, cy, px, py)
mx = cx - bx
my = cy - by
hx = px - bx
hy = py - by
t0 = (mx * hx + my * hy).fdiv(mx ** 2 + my ** 2)
if t0 <= 0
elsif t0 < 1
hx -= t0 * mx
hy -= t0 * my
else
hx -= mx
hy -= my
end
return hx ** 2 + hy ** 2
end
From Google I know that I was not the only one not able to derivate that
short solution.
Another interesting problem is finding the convex hull of a set of
circles in 2d -- assume a rubberband spanned around all of them and
selecting only the ones which touch the rubberband. For a set of points
that is easy -- for circles it took me around 20 hours and 3 attempts.
I think my current solution is ok -- it is called
new_convex_vertices(vertices, prev, nxt) and included in the router
source code available on my page.
One remaining task in finding the exact capacity for traces between a
set of terminals and decreasing that capacity while the board if filled
with traces. Tal Dayan writes much about that in his thesis, but for my
first reading I was not able to get a useful measure. The basic idea is
regarding the cuts, the space between terminals, We can check that space
very easy and fast and we can decrease that space for each trace
inserted. Problem is, that the traces cross this cut not really
perpendicular, so when the triangulation of the terminals have triangles
with very different lengths, traces may touch the terminals. Determining
if a trace touch a terminal is easy -- intersection of line segment with
a few circles. But when we have more traces? We can increase the
terminal diameter instead of decreasing the cut size, but that would
block traces on all sides of the terminal at the same time.
Unfortunately the rubberband generation and routability check -- the
most difficult part -- in only discussed very abstract in that thesis.
For other topics, like layer assignment he gave the sketch of the
algorithm, so a first implementation of layer assignment took me only a
few hours. (It looks nice, but it is O(n^3.5) with n the number of
terminals, so it may be not really fast.)
I will reread Tal Dayan's thesis more carefully in winter. Did you
already read it?
Best regards
Stefan Salewski
- Raw text -