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

[Skybuck Flying]

etc...

You have a gross and dangerous misunderstanding of principles of doing
numerical processing with the computer. I suggest you study the
fundmentals carefully first before wasting your time writing what will
undoubtedly be some ridicolously naive and rather useless code.

I don't need to understand fully how floating point works. Sometimes I
forget about rounding errors, so this thread was a nice refreshment. However
in the back of my mind I know floating points are inaccurate, that is why I
requested the methods to be "as accurate as possible". "as possible" meaning
as possibly as *you* can get it without being to fricking slow lol =D

The epsilon method is flawed in my mind since it assumes the points are
quite large but in fact could be quite small thereby completely failing.

Maybe you have a gross and dangerous misunderstanding of using a smudge
factor/epsilon

I also don't like to study flawed/worthless shit like floating point format
etc... I rather spent my time finding solutions to this shit lol =D. So far
I have found a better alternative which is a rational number library... it
still uses floating points inside which are used to represent the rational
numbers but since it uses fractions it should be a lot more accurate than
just using floating points directly

Another solution might be a fixed point library =D

Bye,
Skybuck.

 

[glen herrmannsfeldt]

Skybuck Flying wrote:

(snip)

I don't need to understand fully how floating point works. Sometimes I
forget about rounding errors, so this thread was a nice refreshment. However
in the back of my mind I know floating points are inaccurate, that is why I
requested the methods to be "as accurate as possible". "as possible" meaning
as possibly as *you* can get it without being to fricking slow lol =D

The epsilon method is flawed in my mind since it assumes the points are
quite large but in fact could be quite small thereby completely failing.

It is not only floating point, but that usually makes it worse.

My example of (0,0) and (997,512) is fixed point. There are no points
on the line segment between them in fixed point.

-- glen

 

[Skybuck Flying]

Ok, you are pissing people off with statements like this.

Lol, don't get carried away Relax, take a break, it's never been my
intention to piss anybody off.

Though I can understand the frustration some people might be having because
the requirements seem
to be impossible to unite with floating points because of floating point
rounding errors.

Those people should really try and find some nice rational number or fixed
point library and poof your frustration will turn into pure relaxation lol
=D

Here's the thing, the "epsilon thing" is far and away the most
practical way of doing this; but just as a matter of correctness, you
actually should not choose a constant epsilon. The correct epsilon
will depend on the magnitude of the coordinates for the original
segment points. For example it would be easy to construct an example
where the best correct epsilon is a million.

And how would such a dynamic epsilon be determined or constructed ?

Besides from that... the code will have to be modified to isolate the
rounding error... which might be quite difficult sometimes (?) or maybe
not.. but just extra boring work which also slows down the code

Ok, perhaps a better way to ask you for more information, is this.
they just chosen literally at random? (Using say, the Mersenne Twister
random number generator, which includes floating point random.) Or
(more likely) are they actually constructed to be *ON* the line with
some likelihood, but for some reason you loose track of this fact, and
wish to recalculate it?

This is important because, the *WAY* you construct the point (say, but
being given the x intercept, then computing the y that is supposed to
correspond to it) may actually give an exact matching algorithm without
the need for any epsilons. One could, for example, just try to
reproduce the procedure for finding the point, from one of the
coordinates, and see if the other matches exactly.

This is a good point you make. The source that constructs the points could
introduce rounding errors...

Then the method which checks the points could also introduce the same
rounding errors thereby cancelling the rounding errors against each other
and still returning success while in reality the point is slighty
wrong/besides the line... other methods might thus correctly detect this.
The verification program would then verify this correct method as being
flawed which is not the case. It's exactly the opposite =D

Thus the verification program needs to be improved to use more accurate
point construction.. for example by using rational numbers or fixed point
numbers

The problem with this is that starting with an x and computing a y, or
the other way around will not necessarily yield the same results.
Further more if you compute the point as (alpha * p_0 + (1-alpha)* p_1)
(which might be *WAY* harder to match -- intuitively it seems so to me,
but I don't have a 100% clear idea), you will again get different LSB
round offs.

Yeah, I understand what you mean =D

So I hope you understand that these accuracy issues are pretty integral
to what it is that you want to do. Without more information from you,
I don't believe that anyone can suggest anything else more with any
expectation of it necessarily working better.

At this point I disagree... math is math... it shouldn't matter what the
source of the information/variables are.

You all have been helpfull at pointing out the inaccuracy problems =D

Bye,
Skybuck.

 

[Skybuck Flying]

[some off-topic newsgroups trimmed]

That certainly won't do in this case etc.

It should be as exact/accurate as possible.

Even trying to detect whether a point is on a line using floating point
arithmetic almost certainly indicates a specification error. It's impossible
to do that exactly.

Not quite... it depends on the input/data and how the floating points are
used.

The rational number library uses floating points but since it uses them only
to represent fractions like
2/3 which could also be represented with integers... but it probably uses
floating points for more convenience and internal conversions etc.. it will
be a lot more accurate... but at some point it might again get inaccurate

Bye,
Skybuck.

 

[Skybuck Flying]

Then use rational numbers?

Excellent idea... done that

Bye,
Skybuck.

 

[Ketil Malde]

Can you still find a point which would in theory be on the line segment but
would still be mis-calculated by the rational number version ?

One that overflows your rational number implementation, perhaps? (If
it uses bignums, you may have to exhaust the heap).

-k

 

[Bernd Paysan]

Some real life logic: once in a graphics rendering lab assignment, we
were instructed to approximate Bezier curves. This is an iterative
process; the stop condition was for the error to become less then
half a pixel. For visualisation on a raster display, that is exactly
what's required.

And then the formula is

result:=((x2 - x1) * (y3 - y1)) - ((x3 - x1) * (y2 - y1)) < 0.25;

or < width*width*0.25, if you have a defined line width ("is on a line" begs
the question "line width", anyway).

 

[nobody]

The epsilon method is flawed in my mind since it assumes the points are
quite large but in fact could be quite small thereby completely failing.

And that's why you need to study some fundementals. Start with
absolute versus relative tolerance (GIYF) and decide which (or some
other measure) is better in your case.

 

[Skybuck Flying]

Skybuck Flying wrote:

(snip)



It is not only floating point, but that usually makes it worse.

My example of (0,0) and (997,512) is fixed point. There are no points
on the line segment between them in fixed point.

What do you mean with fixed point ? I guess you are using some kind of fixed
point implementation, which I dont have ofcourse ?

At least in the rational number implementation I have already proven that
there is a point on the line segment.

(Rational) PointX in real notation: 153.6000000000000000
(Rational) PointY in real notation: 299.1000000000000000

Quite easily actually.

It's just that the floating point method can't calculate it accurately.

Bye,
Skybuck.

 

[Skybuck Flying]

Moron.

Lol, Am I a moron because I am right and you were lazy and copied a flawed
method from some library ?

Bye,
Skybuck =D

 

[Keith Thompson]

What do you mean with fixed point ? I guess you are using some kind of fixed
point implementation, which I dont have ofcourse ?

Yes, you do have a fixed point implementation. It has a constant
delta value of 1. It's called integer artithmetic.

In a fixed point numbering system, numbers are represented as integer
multiples of some base value, which is sometimes called the "delta".
For example, a fixed-point representation with a delta of 0.01 might
be useful for representing money, with dollar amounts being
represented as a whole number of cents.

Some languages have direct support for such types. In others, you can
always simulate it by using integer arithmetic and keeping track of
the delta yourself.

At least in the rational number implementation I have already proven that
there is a point on the line segment.

(Rational) PointX in real notation: 153.6000000000000000
(Rational) PointY in real notation: 299.1000000000000000

Quite easily actually.

Well, not quite; you've swapped the coordinates. You mean
(299.1,153.6), not (153.6,299.1).

It's just that the floating point method can't calculate it accurately.

If your end points are (0,0) and (997,512), and you're using integer
arithmetic (with a delta of 1), there are no representable points on
the line segment excluding the end points. (299.1,153.6) is not
representable.

Equivalently, if you're using a fixed-point delta of 0.01, and your
end points are (0,0) and (9.97,5.12) there are still no representable
points on the line segment excluding the end points. (2.991,1.536) is
not representable.

Now if you're willing to have your is_this_point_on_this_line_segment()
function always return false for some line segments, that's ok. If
you expect it to return true for some significant number of points,
either you can use a numeric representation that supports arbitrary
precision (integer, fixed-point, and floating-point won't do; rational
numbers with unlimited range on the numerator and denominator probably
will), or you can define some concept of "close enough".

What might turn out to be more useful is a function that, given the
end points of a line segment an arbitrary point, tells you the
distance between the line segment and the point. Defining the
"distance" when the point is beyond the end points is left as an
exercise.

 

[Skybuck Flying]

Yes, you do have a fixed point implementation. It has a constant
delta value of 1. It's called integer artithmetic.

In a fixed point numbering system, numbers are represented as integer
multiples of some base value, which is sometimes called the "delta".
For example, a fixed-point representation with a delta of 0.01 might
be useful for representing money, with dollar amounts being
represented as a whole number of cents.

Ok, fixed point implementations therefore have the same rounding problems as
floating point implementations =D Since both work with a "point" =D

Some languages have direct support for such types. In others, you can
always simulate it by using integer arithmetic and keeping track of
the delta yourself.


Well, not quite; you've swapped the coordinates. You mean
(299.1,153.6), not (153.6,299.1).

No, the original poster has swapped the coordinates

In another post the original poster mentioned this line segment:

"
I pick the points (0,0) and (512,997) slightly easier to see as
integers, but you can shift the binary point over and make them floating
point. Find any point on the segment between them.
"

If your end points are (0,0) and (997,512), and you're using integer
arithmetic (with a delta of 1), there are no representable points on
the line segment excluding the end points. (299.1,153.6) is not
representable.

Equivalently, if you're using a fixed-point delta of 0.01, and your
end points are (0,0) and (9.97,5.12) there are still no representable
points on the line segment excluding the end points. (2.991,1.536) is
not representable.

Now if you're willing to have your is_this_point_on_this_line_segment()
function always return false for some line segments, that's ok. If
you expect it to return true for some significant number of points,
either you can use a numeric representation that supports arbitrary
precision (integer, fixed-point, and floating-point won't do; rational
numbers with unlimited range on the numerator and denominator probably
will), or you can define some concept of "close enough".

Yes "close enough" would be the epsilon method... However using multiple
floating point operations will eventually create numerical drift so at some
point even the epsilon method will probably fail because the rounding errors
get to large !?

What might turn out to be more useful is a function that, given the
end points of a line segment an arbitrary point, tells you the
distance between the line segment and the point. Defining the
"distance" when the point is beyond the end points is left as an
exercise.

Neh, this solution faces the same rounding problems.

Bye,
Skybuck.

 

[Hank Oredson]

news:[email protected]... [...]
My example of (0,0) and (997,512) is fixed point. There are no points
on the line segment between them in fixed point.

What do you mean with fixed point ? I guess you are using some kind of fixed
point implementation, which I dont have ofcourse ?

Yes, you do have a fixed point implementation. It has a constant
delta value of 1. It's called integer artithmetic.

In a fixed point numbering system, numbers are represented as integer
multiples of some base value, which is sometimes called the "delta".
For example, a fixed-point representation with a delta of 0.01 might
be useful for representing money, with dollar amounts being
represented as a whole number of cents.

Ok, fixed point implementations therefore have the same rounding problems
as
floating point implementations =D Since both work with a "point" =D

Some languages have direct support for such types. In others, you can
always simulate it by using integer arithmetic and keeping track of
the delta yourself.


Well, not quite; you've swapped the coordinates. You mean
(299.1,153.6), not (153.6,299.1).

No, the original poster has swapped the coordinates

In another post the original poster mentioned this line segment:

"
I pick the points (0,0) and (512,997) slightly easier to see as
integers, but you can shift the binary point over and make them floating
point. Find any point on the segment between them.
"

If your end points are (0,0) and (997,512), and you're using integer
arithmetic (with a delta of 1), there are no representable points on
the line segment excluding the end points. (299.1,153.6) is not
representable.

Equivalently, if you're using a fixed-point delta of 0.01, and your
end points are (0,0) and (9.97,5.12) there are still no representable
points on the line segment excluding the end points. (2.991,1.536) is
not representable.

Now if you're willing to have your is_this_point_on_this_line_segment()
function always return false for some line segments, that's ok. If
you expect it to return true for some significant number of points,
either you can use a numeric representation that supports arbitrary
precision (integer, fixed-point, and floating-point won't do; rational
numbers with unlimited range on the numerator and denominator probably
will), or you can define some concept of "close enough".

Yes "close enough" would be the epsilon method... However using multiple
floating point operations will eventually create numerical drift so at
some
point even the epsilon method will probably fail because the rounding
errors
get to large !?

What might turn out to be more useful is a function that, given the
end points of a line segment an arbitrary point, tells you the
distance between the line segment and the point. Defining the
"distance" when the point is beyond the end points is left as an
exercise.

Neh, this solution faces the same rounding problems.

Bye,
Skybuck.

Read Knuth.
Google brounding.
Get educated.
It's all quite simple.
Generalize to n dimensions, two is boring.
You have not yet defined the problem you wish to solve.
See if you can do that.
Bet you can't.
"Is this point on this line segment" is not a problem definition.
If you are talking mathematics the solution is simple and known,
if you provide the rest of the problem definition.
If you are talking computers and programming, you didn't pose
any interesting problem. The answer is always "yes and no"
without further definition of what you mean.

Go for it!

--

... Hank

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

 

[Walter Roberson]

Read Knuth.
Google brounding.
Get educated.

Hmmm? I google'd "brounding" and it seems to have something to
do with electrical grounding (but appears to have an inflection
I didn't quite catch... a brazed on grounding point, maybe??)

I don't see what brounding has to do with the topic at hand?

 

[Hank Oredson]

Hmmm? I google'd "brounding" and it seems to have something to
do with electrical grounding (but appears to have an inflection
I didn't quite catch... a brazed on grounding point, maybe??)

I don't see what brounding has to do with the topic at hand?

"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

 

[Bruce Roberts]

Read Knuth.

Skybuck has trouble reading the help. Knuth is, perhaps, asking too much.

You have not yet defined the problem you wish to solve.
See if you can do that.
Bet you can't.

A sure bet if I ever saw one.

 

[Ben Hetland]

Some languages have direct support for such types. In others, you can
always simulate it by using integer arithmetic and keeping track of
the delta yourself.

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-+-

 

[Ben Hetland]

Google brounding.
Get educated.

Google quoting.
Get educated.

(Yes, it's all quite simple.)


-+-Ben-+-

 

[Keith Thompson]

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.

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]

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

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

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.

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.

<OT>Ada has built-in user-defined fixed-point types.</OT>

 

[Hank Oredson]

Skybuck has trouble reading the help. Knuth is, perhaps, asking too much.


A sure bet if I ever saw one.

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