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

[Ketil Malde]

Re: Point on Line Segment in 2D. Which code is faster ? Can youimprove it ?

"Skybuck Flying" <nospam@hotmail .com> writes:
[color=blue]
> 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 ? ;)[/color]

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

-k
--
If I haven't seen further, it is by standing in the footprints of giants

[Bernd Paysan]

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

Maarten Wiltink wrote:[color=blue]
> 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.[/color]

And then the formula is

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

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

--
Bernd Paysan
"If you want it done right, you have to do it yourself"

http://www.jwdt.com/~paysan/

[nobody]

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

"Skybuck Flying" <nospam@hotmail .com> wrote:
[color=blue]
>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.[/color]

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]

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


"glen herrmannsfeldt" <gah@ugcs.calte ch.edu> wrote in message
news:4radndLHS_ t9O7LeRVn-pg@comcast.com. ..[color=blue]
> Skybuck Flying wrote:
>
> (snip)
>[color=green]
> > I don't need to understand fully how floating point works. Sometimes I
> > forget about rounding errors, so this thread was a nice refreshment.[/color][/color]
However[color=blue][color=green]
> > in the back of my mind I know floating points are inaccurate, that is[/color][/color]
why I[color=blue][color=green]
> > requested the methods to be "as accurate as possible". "as possible"[/color][/color]
meaning[color=blue][color=green]
> > as possibly as *you* can get it without being to fricking slow lol =D[/color]
>[color=green]
> > 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.[/color]
>
> 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.[/color]

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.60000000000 00000
(Rational) PointY in real notation: 299.10000000000 00000

Quite easily actually.

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

Bye,
Skybuck.

[Skybuck Flying]

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


"Nicholas Sherlock" <n_sherlock@hot mail.com> wrote in message
news:dgo88c$pe8 $1@lust.ihug.co .nz...[color=blue]
> Skybuck Flying wrote:[color=green]
> > "nobody" <nobody@nowhere .com> wrote in message
> > news:43doi1t5ij 6lcljm2p04k1rga dsmgctqgv@4ax.c om...
> >[color=darkred]
> >>"Skybuck Flying" <nospam@hotmail .com> wrote:
> >>>Using epsilon's and stuff like should probably be prevented as much as
> >>>possible since those are common forms of errors etc and limitations[/color]
> >[color=darkred]
> >>You have a gross and dangerous misunderstandin g of principles of doing
> >>numerical processing with the computer[/color]
> >
> > 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.[/color]
>
> Moron.[/color]

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

Bye,
Skybuck =D
[color=blue]
>
>
>
> Nicholas Sherlock[/color]

[Keith Thompson]

Re: Point on Line Segment in 2D. Which code is faster ? Can youimprove it ?

"Skybuck Flying" <nospam@hotmail .com> writes:[color=blue]
> "glen herrmannsfeldt" <gah@ugcs.calte ch.edu> wrote in message
> news:4radndLHS_ t9O7LeRVn-pg@comcast.com. ..[/color]
[...][color=blue][color=green]
>> My example of (0,0) and (997,512) is fixed point. There are no points
>> on the line segment between them in fixed point.[/color]
>
> What do you mean with fixed point ? I guess you are using some kind of fixed
> point implementation, which I dont have ofcourse ;) ?[/color]

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.
[color=blue]
> 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.60000000000 00000
> (Rational) PointY in real notation: 299.10000000000 00000
>
> Quite easily actually.[/color]

Well, not quite; you've swapped the coordinates. You mean
(299.1,153.6), not (153.6,299.1).
[color=blue]
> It's just that the floating point method can't calculate it accurately.[/color]

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_o n_this_line_seg ment()
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.

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Skybuck Flying]

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


"Keith Thompson" <kst-u@mib.org> wrote in message
news:lnslvzib3a .fsf@nuthaus.mi b.org...[color=blue]
> "Skybuck Flying" <nospam@hotmail .com> writes:[color=green]
> > "glen herrmannsfeldt" <gah@ugcs.calte ch.edu> wrote in message
> > news:4radndLHS_ t9O7LeRVn-pg@comcast.com. ..[/color]
> [...][color=green][color=darkred]
> >> My example of (0,0) and (997,512) is fixed point. There are no points
> >> on the line segment between them in fixed point.[/color]
> >
> > What do you mean with fixed point ? I guess you are using some kind of[/color][/color]
fixed[color=blue][color=green]
> > point implementation, which I dont have ofcourse ;) ?[/color]
>
> 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.[/color]

Ok, fixed point implementations therefore have the same rounding problems as
floating point implementations ;) =D Since both work with a "point" =D
[color=blue]
>
> 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.
>[color=green]
> > At least in the rational number implementation I have already proven[/color][/color]
that[color=blue][color=green]
> > there is a point on the line segment.
> >
> > (Rational) PointX in real notation: 153.60000000000 00000
> > (Rational) PointY in real notation: 299.10000000000 00000
> >
> > Quite easily actually.[/color]
>
> Well, not quite; you've swapped the coordinates. You mean
> (299.1,153.6), not (153.6,299.1).[/color]

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.
"
[color=blue]
>[color=green]
> > It's just that the floating point method can't calculate it accurately.[/color]
>
> 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_o n_this_line_seg ment()
> 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".[/color]

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 !? ;)
[color=blue]
>
> 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.[/color]

Neh, this solution faces the same rounding problems.

Bye,
Skybuck.
[color=blue]
>
> --
> Keith Thompson (The_Other_Keit h) kst-u@mib.org[/color]
<http://www.ghoti.net/~kst>[color=blue]
> San Diego Supercomputer Center <*>[/color]
<http://users.sdsc.edu/~kst>[color=blue]
> We must do something. This is something. Therefore, we must do this.[/color]

[Hank Oredson]

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

"Skybuck Flying" <nospam@hotmail .com> wrote in message
news:dgq6oh$aio $1@news6.zwoll1 .ov.home.nl...[color=blue]
>
> "Keith Thompson" <kst-u@mib.org> wrote in message
> news:lnslvzib3a .fsf@nuthaus.mi b.org...[color=green]
>> "Skybuck Flying" <nospam@hotmail .com> writes:[color=darkred]
>> > "glen herrmannsfeldt" <gah@ugcs.calte ch.edu> wrote in message
>> > news:4radndLHS_ t9O7LeRVn-pg@comcast.com. ..[/color]
>> [...][color=darkred]
>> >> 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[/color][/color]
> fixed[color=green][color=darkred]
>> > point implementation, which I dont have ofcourse ;) ?[/color]
>>
>> 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.[/color]
>
> Ok, fixed point implementations therefore have the same rounding problems
> as
> floating point implementations ;) =D Since both work with a "point" =D
>[color=green]
>>
>> 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.
>>[color=darkred]
>> > At least in the rational number implementation I have already proven[/color][/color]
> that[color=green][color=darkred]
>> > there is a point on the line segment.
>> >
>> > (Rational) PointX in real notation: 153.60000000000 00000
>> > (Rational) PointY in real notation: 299.10000000000 00000
>> >
>> > Quite easily actually.[/color]
>>
>> Well, not quite; you've swapped the coordinates. You mean
>> (299.1,153.6), not (153.6,299.1).[/color]
>
> 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.
> "
>[color=green]
>>[color=darkred]
>> > It's just that the floating point method can't calculate it accurately.[/color]
>>
>> 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_o n_this_line_seg ment()
>> 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".[/color]
>
> 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 !? ;)
>[color=green]
>>
>> 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.[/color]
>
> Neh, this solution faces the same rounding problems.
>
> Bye,
> Skybuck.[/color]


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]

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

In article <qd6Ye.1118$zQ3 .58@newsread1.n ews.pas.earthli nk.net>,
Hank Oredson <horedson@earth link.net> wrote:
[color=blue]
>Read Knuth.
>Google brounding.
>Get educated.[/color]

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?
--
These .signatures are sold by volume, and not by weight.

[Hank Oredson]

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

"Walter Roberson" <roberson@ibd.n rc-cnrc.gc.ca> wrote in message
news:dgqrp8$bko $1@canopus.cc.u manitoba.ca...[color=blue]
> In article <qd6Ye.1118$zQ3 .58@newsread1.n ews.pas.earthli nk.net>,
> Hank Oredson <horedson@earth link.net> wrote:
>[color=green]
>>Read Knuth.
>>Google brounding.
>>Get educated.[/color]
>
> 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?[/color]


"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]

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


"Hank Oredson" <horedson@earth link.net> wrote in message
news:qd6Ye.1118 $zQ3.58@newsrea d1.news.pas.ear thlink.net...

<trim of an excessively long, non-contributory quote>
[color=blue]
> Read Knuth.[/color]

Skybuck has trouble reading the help. Knuth is, perhaps, asking too much.
[color=blue]
> You have not yet defined the problem you wish to solve.
> See if you can do that.
> Bet you can't.[/color]

A sure bet if I ever saw one.

[Ben Hetland]

Re: Point on Line Segment in 2D. Which code is faster ? Can youimprove it ?

Keith Thompson wrote:[color=blue]
> 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.[/color]

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]

Re: Point on Line Segment in 2D. Which code is faster ? Can you improveit ?

Hank Oredson wrote:[color=blue]
> Google brounding.
> Get educated.[/color]

Google quoting.
Get educated.

(Yes, it's all quite simple.)


-+-Ben-+-

[Keith Thompson]

Re: Point on Line Segment in 2D. Which code is faster ? Can youimprove it ?

Ben Hetland <ben.a.hetland@ sintef.no> writes:[color=blue]
> Keith Thompson wrote:[color=green]
>> 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.[/color]
>
> 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.[/color]

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]
[color=blue]
> 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
> :-)[/color]

Exponentiation (if the language supports it) is just repeated
multiplication.
[color=blue]
> 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.[/color]

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>

--
Keith Thompson (The_Other_Keit h) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Hank Oredson]

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

"Bruce Roberts" <ber@bounceitat tcanada.xnet> wrote in message
news:_FfYe.8199 $0u2.1520116@ne ws20.bellglobal .com...[color=blue]
>
> "Hank Oredson" <horedson@earth link.net> wrote in message
> news:qd6Ye.1118 $zQ3.58@newsrea d1.news.pas.ear thlink.net...
>
> <trim of an excessively long, non-contributory quote>
>[color=green]
>> Read Knuth.[/color]
>
> Skybuck has trouble reading the help. Knuth is, perhaps, asking too much.
>[color=green]
>> You have not yet defined the problem you wish to solve.
>> See if you can do that.
>> Bet you can't.[/color]
>
> A sure bet if I ever saw one.[/color]


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