Point on Line Segment in 2D. Which code is faster ? Can you improve it ?

"Bounding and Rounding". Perhaps the term has fallen out of favor.

Has to do with the analysis of problems like point / line distance, and how one computes it, considering the number representation chosen, the accuracy and the precision.

Before I can tell you if a point is "on" a line segment, I need to know a great deal about what you mean by "on", how you represent a point and represent a line segment, how you represent the numbers used to specify a particular point and a particular line segment. Once I know those things, then I can give you a code fragment that will answer the question of whether some particular point is "on" some particular line in your representation and for your purpose.

For example. the line segment (0,0), (1,1) may not have any points on it at all, may have one and only one, may have two and only two, or may have many. Until you tell me more, I cannot answer for any particular point you supply.

--

  ... Hank

http://home.earthlink.net/~horedson
http://home.earthlink.net/~w0rli

Careful! You also have to modify your arithmetic (the formulas) unless you restrict yourself to only doing addition and subtraction. Otherwise you might end up with the wrong amount of dollars... or wrong squares.

E.g., we keep track of length measurements in meters at 1 cm "delta". (delta = 0.01). We measure an area at 5.25m X 10.1m, so we represent it as a = 525 b = 1010 Then we calculate using the very straightforward and obvious formula area = a * b, which is computed as 530250. Remembering the "delta", we might end up concluding that the area is 5302.50 m2, which is not just a bit wrong...

We would need a different formula, except it has to be in integer too, right? Otherwise there's no point in using "fixed point" arithment if we often need to revert to floating points even for intermediate calculations anyway.

That was a very simple formula; but think of a more real-world example where a "correction factor" is no longer so obvious.

We might deduce some formulas though, but it would require us to rewrite every operator in the original formula. Ignoring rounding errors and overflows for now, perhaps using some function substitutes for each operator, we could end up using integer arithmetic in the following way:

delta = 0.01 f = 1/delta -> f=100 (the f is integer!)

a * b -> (a * b) / f a / b -> (a * f) / b

1 / a -> (f * f) / a a ^ 2 -> a * a -> a * a / f a ^ 3 -> (a^2)*a -> (a^2)*a/f -> (a*a/f)*a/f a ^ n -> ((... (( ((a(1) * a(2))/f) * a(3) )/f) *...) * a(n))/f (n whole number) a ^ b -> suggestions anyone?

Think how that translates just for a simple interest calculation like fv = pv * (1 + r/100)^n :-)

Does anyone know how that is implemented for languages that do support this kind of data type when the underlying hardware does not support it directly? I should think that if everything in this manner translates into some "intrinsic routines" or similar support code, then easily the expected gain (speed) from using integer instead of floating point operations is lost to all the extra operations involved.

-+-Ben-+-

Google quoting. Get educated.

(Yes, it's all quite simple.)

-+-Ben-+-

Of course; that's part of what I meant by "keeping track of the delta yourself" (though I suppose I should have been more explicit).

[snip]

Exponentiation (if the language supports it) is just repeated multiplication.

Addition and subtraction are trivial. Multiplication just requires multiplying the integer result by the delta. Division can be a bit more tricky; you might need extra precision for an intermediate result (I don't remember the details). There shouldn't be any need for any intrinsic routines; most or all of it can be done with inline code.

And you'll get better performance if the delta is a power of two.

Ada has built-in user-defined fixed-point types.

--
Keith Thompson (The_Other_Keith) kst-u@mib.org  
San Diego Supercomputer Center               
We must do something.  This is something.  Therefore, we must do this.

Yes, suspect that is true. What do I win?

Kinda fun watching folks post all kinds of "solutions" to a problem which is not yet defined, while ignoring all the important issues.

--

  ... Hank

http://home.earthlink.net/~horedson
http://home.earthlink.net/~w0rli

For rational exponents, the operation involves multiplication and division, or at least one single division to evaluate a reciprocal.

Irrational and transcendental exponentiation is witchcraft and should be proscribed. (;-)

--
Regards, John Woodgate, OOO - Own Opinions Only.
If everything has been designed, a god designed evolution by natural selection.
http://www.jmwa.demon.co.uk Also see http://www.isce.org.uk

In article John Woodgate writes: .... > >When the exponent also has a fractional part (as in "a^b"), then it is > >not more so trivial. I assume this is true even if the "fractional > >exponent" is a "fixed format represented as integer". > > For rational exponents, the operation involves multiplication and > division, or at least one single division to evaluate a reciprocal.

Only for integer exponents, for rational non-integral exponents you need also roots. E.g. a^(1/2) = sqrt(a).

--
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/

This is true only for integer exponents! (As I illustrated with my "a^n" example.)

When the exponent also has a fractional part (as in "a^b"), then it is not more so trivial. I assume this is true even if the "fractional exponent" is a "fixed format represented as integer".

-+-Ben-+-

I read in sci.electronics.design that Dik T. Winter wrote (in ) about 'Point on Line Segment in 2D. Which code is faster ? Can you improve it ?', on Fri, 23 Sep 2005:

They can be calculated to any desired degree of precision by multiplication. Look up 'co-factors', which is how we used to find square roots on a mechanical calculator.

--
Regards, John Woodgate, OOO - Own Opinions Only.
If everything has been designed, a god designed evolution by natural selection.
http://www.jmwa.demon.co.uk Also see http://www.isce.org.uk

In article John Woodgate writes: > I read in sci.electronics.design that Dik T. Winter > wrote (in ) about 'Point on Line Segment in 2D. Which > code is faster ? Can you improve it ?', on Fri, 23 Sep 2005: .... > > > For rational exponents, the operation involves multiplication and > > > division, or at least one single division to evaluate a reciprocal. > >

I know how to calculate square roots etc. Thank you very much. But with your characterisation you can calculate *all* numbers of the form a^b by only the operations multiplication and division, addition and subtraction.

--
dik t. winter, cwi, kruislaan 413, 1098 sj  amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn  amsterdam, nederland; http://www.cwi.nl/~dik/

That's true -- but if you're dealing with exponentation with a non-integer exponent, you probably want to use floating-point anyway.

If you really need to compute a=b**c, where a, b, and c are all fixed-point, you're likely to be better off converting b and c to floating-point and then converting the result back to fixed-point.

--
Keith Thompson (The_Other_Keith) kst-u@mib.org  
San Diego Supercomputer Center               
We must do something.  This is something.  Therefore, we must do this.