| Author |
Message |
Skybuck Flying
Guest
|
 Posted:
Tue Sep 20, 2005 8:15 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
"glen herrmannsfeldt" <gah@ugcs.caltech.edu> wrote in message
news:gvCdnayW-7Xzg7beRVn-vQ@comcast.com...
| Quote: | Skybuck Flying wrote:
(snip)
That certainly won't do in this case etc.
It should be as exact/accurate as possible.
You really need to tell us what "this case" is.
|
I don't see the relevance of the case.
The math is clear and simple and is case independant =D
| Quote: |
You expect everyone to help you, but don't seem
interested in helping much yourself.
|
No on the contrary ;) See above lol.
Bye,
Skybuck. |
|
| Back to top |
|
 |
Skybuck Flying
Guest
|
| Posted:
Tue Sep 20, 2005 8:15 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
"Nicholas Sherlock" <n_sherlock@hotmail.com> wrote in message
news:dge6j3$ufs$1@lust.ihug.co.nz...
| Quote: | Nicholas Sherlock wrote:
Skybuck Flying wrote:
I needed a method to determine if a point was on a line segment in 2D.
So I
googled for some help and so far I have evaluated two methods.
function PointOnLine2D(x1,y1, x2,y2, x3,y3:double):boolean;
begin
result:=((x2 - x1) * (y3 - y1)) - ((x3 - x1) * (y2 - y1)) < 0.0000001;
end;
Sorry, I missed some of this code from my app:
function PointOnLine2D(x1, y1, x2, y2, x3, y3: double): boolean;
begin
result :=
(((x3 >= x1) and (x3 <= x2)) or ((x3 >= x2) and (x3 <= x1))) and
(((y3 >= y1) and (y3 <= y2)) or ((y3 >= y2) and (y3 <= y1))) and
(abs(((x2 - x1) * (y3 - y1)) - ((x3 - x1) * (y2 - y1))) < 0.00001);
end;
|
Ok I first I didn't understand this code, but not I get it.
The other C example was like this example.
The C example compares the first multiplication result with the second
multiplication result.
If they are the same then it's true else false.
Because floating point rounding errors could occur the C example could fail.
Which was demonstrated by my method 2 which was the ported C version.
So your/the fastgeo version solves this rounding error by using an
epsilon...
I still think it's a shabby solution since it could horribly fail if the
points are small enough.
Maybe something like:
0.00000003245
0.000000003245
0.000000003456
0.000000000123
etc...
OUCH
;)
Bye,
Skybuck =D |
|
| Back to top |
|
|
Skybuck Flying
Guest
|
| Posted:
Tue Sep 20, 2005 8:15 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
"Randy" <joe@burgershack.com> wrote in message
news:dgfdcp$s44$1@joe.rice.edu...
| Quote: | Skybuck Flying wrote:
"Hans-Bernhard Broeker" <broeker@physik.rwth-aachen.de> wrote in message
news:3p0cvdF86nt0U1@news.dfncis.de...
In comp.graphics.algorithms Skybuck Flying <nospam@hotmail.com> wrote:
[Massive crossposting reduced to single group. Please, Skybuck, try
to follow netiquette a bit better in the future. If you feel a need
to X-post, at be a bit more selective to where --- this had *no*
business being posted to comp.arch or sci.electronics. And *always*
select a single group for the follow-ups.]
No, I like to have input from all those newsgroups since this is about
optimizations and those newsgroup are related to software and hardware
optimizations. C/Delphi/Asm for software/cpu optimizations and
comp.arch/asm/eletronics about hardware optimizations and algorithms
possibly about algorithm optimization. Those newsgroups are likely to
contain people who know something about this.
I'm with Hans on this one. Skybuck, by your logic you should have
posted to ALL newsgroups, since there's probably someone in every
newsgroup who will be somehow "related to optimization". :-(
Comp.graphics.algorithms was the right place. Comp.lang.c is hard to
justify, since your question has nothing to do with C. But there's no
way to justify posting to sci.electronics.design, comp.arch, or
alt.comp.lang.borland-delphi. Nor comp.lang.asm, unless you want a
response written in assembly language.
That said, other appropriate forums might have included comp.programming
or *maybe* comp.theory.
...
You need to define the task a good deal more cleanly before an
implementation can reasonably be suggested. Missing information:
1) What's a line segment, in this case? It may come as a surprise to
you, but ideas about the details of this actually differ. So: how do
you actually specify this line segment?
A 2D line segment defined by (x1,y1) - (x2,y2)
Integer or floating point? In either case, how big are your points and
how fat is the line? Is it acceptable to return a false positive or
negative? If so, how often? If it's not acceptable, then you have a
problem. On a any machine that lacks infinite numerical precision, you
can never know whether an infinitely small point lies on an infinitely
thin line segment.
In the end, you're going to have to do something like this:
"Draw two lines, one from each point in the line segment to the
candidate point. If these lines' slopes are equal but differ in sign
(e.g. X and -X), then your point lies on the segment."
Of course, what does it mean for slope values to be "equal" on a digital
computer? Unless you can represent the problem entirely symbolically,
"equal" will be necessarily limited by the representation of the data
and the accuracy of the math. In the real world, epsilon is a necessary
evil.
2) When exactly do you want the test to return "true"? I.e.: how
close to the ideal segment does a point have to be to still be
considered "on" it?
As precise as possible. (Floating point precision, no rounding)
This is an oxymoron. Floating point is inescapably about rounding.
Digital representations of floating point are approximations, as are the
math operations that manipulate them. The programmer has to manage
numerical imprecision on computers or live with wrong answers.
For some perspective, read David Goldberg's "What Every Computer
Scientist Should Know About Floating-Point Arithmetic":
http://docs.sun.com/source/806-3568/ncg_goldberg.html
|
Yes I am sure you all right about this... But instead of wasting my time
reading through this highly theoretical shit I rather find practical
solutions to this potential floating point rounding problem. And using
epsilon's is probably not it since it still leaves room for errors etc.
So far I have found one nice solution... Trational class from delphi
fundamentals.
Another solution might be a fixed point library which might be faster =D
Bye,
Skybuck. |
|
| Back to top |
|
|
Skybuck Flying
Guest
|
| Posted:
Tue Sep 20, 2005 8:15 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
"Rich Grise" <rich@example.net> wrote in message
news:pan.2005.09.16.23.00.52.848743@example.net...
| Quote: | On Fri, 16 Sep 2005 19:59:37 +0200, Skybuck Flying wrote:
"Hans-Bernhard Broeker" <broeker@physik.rwth-aachen.de> wrote in message
I needed a method to determine if a point was on a line segment in
2D. So I googled for some help and so far I have evaluated two
methods.
You need to define the task a good deal more cleanly before an
implementation can reasonably be suggested. Missing information:
1) What's a line segment, in this case? It may come as a surprise to
you, but ideas about the details of this actually differ. So: how do
you actually specify this line segment?
A 2D line segment defined by (x1,y1) - (x2,y2)
The points itself should not be considered part of the line segment...
unless you ofcourse
disagree.
I thought that was what you were trying to determine?
Wouldn't it be something like:
IF ((((x3 - x1) / (y3 - y1)) == ((x2 - x3) / (y2 - y3)))
AND (x2 > x3 > x1) AND (y2 > y3 > y1))
THEN
print "Point is on the line"
|
Is this basic or something lol ? ;)
It has to be true programming language code =D
Bye,
Skybuck. |
|
| Back to top |
|
|
nobody
Guest
|
| Posted:
Tue Sep 20, 2005 4:15 pm Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
"Skybuck Flying" <nospam@hotmail.com> wrote:
| Quote: | 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. |
|
| Back to top |
|
|
Bernd Paysan
Guest
|
| Posted:
Tue Sep 20, 2005 4:15 pm Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
Maarten Wiltink wrote:
| Quote: | 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).
--
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://www.jwdt.com/~paysan/ |
|
| Back to top |
|
|
Keith Thompson
Guest
|
| Posted:
Wed Sep 21, 2005 12:15 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
"Skybuck Flying" <nospam@hotmail.com> writes:
| Quote: | "glen herrmannsfeldt" <gah@ugcs.caltech.edu> wrote in message
news:4radndLHS_t9O7LeRVn-pg@comcast.com...
[...]
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.
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.
| Quote: | 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).
| Quote: | 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.
--
Keith Thompson (The_Other_Keith) 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. |
|
| Back to top |
|
|
Skybuck Flying
Guest
|
| Posted:
Wed Sep 21, 2005 12:15 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
"Keith Thompson" <kst-u@mib.org> wrote in message
news:lnslvzib3a.fsf@nuthaus.mib.org...
| Quote: | "Skybuck Flying" <nospam@hotmail.com> writes:
"glen herrmannsfeldt" <gah@ugcs.caltech.edu> wrote in message
news:4radndLHS_t9O7LeRVn-pg@comcast.com...
[...]
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
| Quote: |
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).
|
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.
"
| Quote: |
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".
|
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 !? ;)
| Quote: |
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.
|
|
| Back to top |
|
|
Skybuck Flying
Guest
|
| Posted:
Wed Sep 21, 2005 12:15 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
"glen herrmannsfeldt" <gah@ugcs.caltech.edu> wrote in message
news:4radndLHS_t9O7LeRVn-pg@comcast.com...
| Quote: | 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.
|
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. |
|
| Back to top |
|
|
Skybuck Flying
Guest
|
| Posted:
Wed Sep 21, 2005 12:15 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
"Nicholas Sherlock" <n_sherlock@hotmail.com> wrote in message
news:dgo88c$pe8$1@lust.ihug.co.nz...
| Quote: | Skybuck Flying wrote:
"nobody" <nobody@nowhere.com> wrote in message
news:43doi1t5ij6lcljm2p04k1rgadsmgctqgv@4ax.com...
"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
You have a gross and dangerous misunderstanding of principles of doing
numerical processing with the computer
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.
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
|
|
| Back to top |
|
|
Walter Roberson
Guest
|
| Posted:
Wed Sep 21, 2005 5:40 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
In article <qd6Ye.1118$zQ3.58@newsread1.news.pas.earthlink.net>,
Hank Oredson <horedson@earthlink.net> wrote:
| Quote: | 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?
--
These .signatures are sold by volume, and not by weight. |
|
| Back to top |
|
|
Hank Oredson
Guest
|
| Posted:
Wed Sep 21, 2005 8:15 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
"Skybuck Flying" <nospam@hotmail.com> wrote in message
news:dgq6oh$aio$1@news6.zwoll1.ov.home.nl...
| Quote: |
"Keith Thompson" <kst-u@mib.org> wrote in message
news:lnslvzib3a.fsf@nuthaus.mib.org...
"Skybuck Flying" <nospam@hotmail.com> writes:
"glen herrmannsfeldt" <gah@ugcs.caltech.edu> wrote in message
news:4radndLHS_t9O7LeRVn-pg@comcast.com...
[...]
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.
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).
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.
"
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".
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 |
|
| Back to top |
|
|
Hank Oredson
Guest
|
| Posted:
Wed Sep 21, 2005 4:15 pm Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
"Walter Roberson" <roberson@ibd.nrc-cnrc.gc.ca> wrote in message
news:dgqrp8$bko$1@canopus.cc.umanitoba.ca...
| Quote: | In article <qd6Ye.1118$zQ3.58@newsread1.news.pas.earthlink.net>,
Hank Oredson <horedson@earthlink.net> wrote:
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?
|
"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 |
|
| Back to top |
|
|
Bruce Roberts
Guest
|
| Posted:
Wed Sep 21, 2005 9:13 pm Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
"Hank Oredson" <horedson@earthlink.net> wrote in message
news:qd6Ye.1118$zQ3.58@newsread1.news.pas.earthlink.net...
<trim of an excessively long, non-contributory quote>
Skybuck has trouble reading the help. Knuth is, perhaps, asking too much.
| Quote: | 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. |
|
| Back to top |
|
|
Ben Hetland
Guest
|
| Posted:
Thu Sep 22, 2005 4:15 pm Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
Hank Oredson wrote:
| Quote: | Google brounding.
Get educated.
|
Google quoting.
Get educated.
(Yes, it's all quite simple.)
-+-Ben-+- |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in