js9b+@andrew.cmu.edu (Jon C. Slenk) (07/23/89)
This is a somewhat simplistic question: Given two points (a and b, defining a line), how can I calculate a points that is x units from point a along that line? My solution is to use similar triangles and ratios. The only problem is that this requires multiplications, divisions and also a square root (ouch!). I would like to ask if there are better algorithms that would give good results without these heavy-duty functions (particularty the sqrt). TIA! Sincerely, Jon Slenk / js9b CMU. ----------------------------+----------------------- `Land property marked the | Capitalism: beginning of civilization.' | Every man for himself.
NU113738@NDSUVM1.BITNET (07/25/89)
I have a suggestion for locating a point along a line AB without using division or square roots. It may not be what you want, but what you could do is use a polar coordinate system using the following identities (please, double check in an algebra book, its off the top of my head...assume 0=theta) x = r cos0 y = r sin0. Solving for r, r = x/cos0 or r = y/sin0 THETA is found using 0 = arctan(y/x). So r, the distance from A can be deduced from r = x/cos0 or r = y/sin0. Pick up a Geometry text somewhere and examine these formulas, I'm sure you can make it fairly efficient. Oh, to speed this up, if it has to be calculated many times, us a Sin/Cos lookup table, precalculate the values of sin/cos for each 0, (decide on a increment between each value. 1 degree will probably be more than enough) and store them in a array. If you use 1 degree increments, in indexed array could find the value using 0 directly. Anyway, hope I gave you a few ideas. Jeff Bakke NU113738@NDSUVM1.BITNET
libbyb@hpdml93.HP.COM (Libby Bagley) (07/28/89)
/ hpdml93:comp.graphics / js9b+@andrew.cmu.edu (Jon C. Slenk) / 4:44 pm Jul 22, 1989 /
This is a somewhat simplistic question: Given two points (a and b,
defining a line), how can I calculate a points that is x units from
point a along that line?
What's wrong with linear interpolation?
x = (1-t) * a + t * b
where,
t is units usually [0,1]
a,b,x are points (either two or three dimensional)NU113738@NDSUVM1.BITNET (07/28/89)
Ok, I was pointed out a problem in my last response, as sloppy as it was.
I indicated no division was required but then went on to suggest the
formula r = x / cos0. Obviously a division. But this is also equal to
r = x * 1/cos0 and of course 1/cos0 = csc0. So by using csc and sec instead
of sin/cos, division can be removed.
Along this thought line, another item occurs in trying to speed up equation,
mainly, to calculate csc0 or sec0, floating point math is required.
What I did, in a situation where a sin/cos table of the values for each
degree were required, is to create it as such, say the value of 23 degress
is .3907311..... After calculation of this value for storage in the lookup
table, I then used the idea that .390xxx = 390 x 10^-3. But instead of base
10, I used base 2. So I would take .3907311 x 4096 or 2048 or some power
of 2 and store that value as an integer. Now, when I retrieve the value from
the storage table, say I need (3*sin23) then the math is performed as:
(3 *(lookup(23)) >> 11. The arthmethic shift by 11 is performed instead
of a division by 2048... A much faster method and it required no floating point
mathematics. Although, to store the intial value of .3907311, if you want
a fairly accurate estimation, you need to use long integers since a word
(assuming a IBMPC size word) is insufficient to store the value with out
an overflow condition. In timing the differences in this elongated and
somewhat sloppy method of division/multiplication/storage, it still kicks
a floating point arithmetic time. (although, I don't know what would
be the result with a coprocessor, so don't take my word in that case.)
These are just some suggestions. I hope they help or give someone some
ideas.
Jeff Bakke
NU113738@NDSUVM1.BITNET