| Author |
Message |
Rich Grise
Guest
|
 Posted:
Sat Sep 17, 2005 12:15 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
On Fri, 16 Sep 2005 19:59:37 +0200, Skybuck Flying wrote:
| Quote: | "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"
Good Luck!
Rich |
|
| Back to top |
|
 |
Randy
Guest
|
| Posted:
Sat Sep 17, 2005 12:15 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
Skybuck Flying wrote:
| Quote: | "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.
....
| Quote: |
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.
| Quote: |
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
Randy |
|
| Back to top |
|
|
glen herrmannsfeldt
Guest
|
| Posted:
Sat Sep 17, 2005 12:15 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
Skybuck Flying wrote:
(snip)
| Quote: | 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.
You expect everyone to help you, but don't seem
interested in helping much yourself.
-- glen |
|
| Back to top |
|
|
David Hopwood
Guest
|
| Posted:
Sat Sep 17, 2005 7:03 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
[some off-topic newsgroups trimmed]
Skybuck Flying wrote:
| Quote: | "Maarten Wiltink" <maarten@kittensandcats.net> wrote:
"Skybuck Flying" <nospam@hotmail.com> wrote:
"Nicholas Sherlock" <n_sherlock@hotmail.com> wrote:
Skybuck Flying wrote:
Though the < 0.0000001 is new which I dont quite understand ;)
Floating point math is always inaccurate as most numbers cannot be
exactly represented. This bit basically takes care of that by adding
a fudge factor.
Yes I figured that much. So this would mean the function returns true
if abs(blabla) is near zero ?
Why use 0.00001 why not 0.0000001 or 0.00000000000001 ?
Personally I don't like epsilons like this... it leaves room for
error/malfunction ?
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.
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.
--
David Hopwood <david.nospam.hopwood@blueyonder.co.uk> |
|
| Back to top |
|
|
Ketil Malde
Guest
|
| Posted:
Sat Sep 17, 2005 7:41 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
"Skybuck Flying" <nospam@hotmail.com> writes:
| Quote: | It should be as exact/accurate as possible.
|
Then use rational numbers?
-k
--
If I haven't seen further, it is by standing in the footprints of giants |
|
| Back to top |
|
|
Skybuck Flying
Guest
|
| Posted:
Sat Sep 17, 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:dPidne5UGqDIkbbeRVn-gg@comcast.com...
| Quote: | Skybuck Flying wrote:
"Nicholas Sherlock" <n_sherlock@hotmail.com> wrote in message
news:dge6ot$ufs$3@lust.ihug.co.nz...
(snip)
Floating point math is always inaccurate as most numbers cannot be
exactly represented. This bit basically takes care of that by adding a
fudge factor.
Yes I figured that much. So this would mean the function returns true if
abs(blabla) is near zero ?
Why use 0.00001 why not 0.0000001 or 0.00000000000001 ?
Personally I don't like epsilons like this... it leaves room for
error/malfunction ?
Then don't use floating point math.
As you don't indicate the origin of the problem, we can't help any
more than that. In some cases it can be done in fixed point,
especially if the segment ends and point being checked are fixed point
values.
Otherwise, if you select two end points somewhat randomly there is a
high probability that no floating point values lie on the segment
between them.
|
You are more then welcome to prove this very soon.
I'll shall do or attempt to do two things:
"allow dll plugins" for the test program and
"allow data/verification" files for the test program.
As to provide a binary and test files for those people who don't have a
pascal compiler, or can't program or don't want to program or just want to
supply some verification data =D
It's gonna be quite cool lol.
Bye,
Skybuck. |
|
| Back to top |
|
|
Skybuck Flying
Guest
|
| Posted:
Sat Sep 17, 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.
|
You ll see quite soon the test program is done ;)
Everybody should simply do his/her best at "as accurate" as possible.
Though it should also be fast.
So you can use single or double floating point format.
Whatever floats your boat ;)
Though I would suggest doubles since those can handle higher/better
precision.. bigger/smaller numbers etc.
Using epsilon's and stuff like should probably be prevented as much as
possible since those are common forms of errors etc and limitations etc...
;)
Bye,
Skybuck. |
|
| Back to top |
|
|
nobody
Guest
|
| Posted:
Sat Sep 17, 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: | Using epsilon's and stuff like should probably be prevented as much as
possible since those are common forms of errors etc and limitations 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. |
|
| Back to top |
|
|
John Bode
Guest
|
| Posted:
Sun Sep 18, 2005 5:45 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
Skybuck Flying wrote:
| Quote: | Hi,
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.
|
Here's another one to play with. It goes from the assumption that if
the slope from p1 to p2 is the same as the slope from p1 to p3, then p3
is colinear with p1 and p2. Then it checks x coordinates to see if p3
is on the segment between p1 and p2.
It expresses slope as rational numbers, so the arithmetic is integral.
It probably needs to be bulletproofed.
#include <stdio.h>
typedef struct {
long x;
long y;
} point_t;
typedef struct {
long num;
long denom;
} rational_t;
#define REDUCE(frac) \
do { \
long e1=frac.num, \
e2=frac.denom, \
quot, rem = -1; \
long tmp; \
int done = 0; \
while(!done) \
{ \
if (e1 < e2) \
{ \
tmp = e1; \
e1 = e2; \
e2 = tmp; \
} \
quot = e1/e2; \
rem = e1 % e2; \
if (rem) \
e1 = rem; \
else \
done = 1; \
} \
frac.num /= e2; \
frac.denom /= e2; \
} while(0)
/**
* We are assuming that p1 and p2 have been ordered
* so that p1.x <= p2.x
*/
int isOnLine(point_t p1, point_t p2, point_t p3)
{
rational_t m1 = {p3.y - p1.y, p3.x - p1.x};
rational_t m2 = {p2.y - p1.y, p2.x - p1.x};
/**
* special case -- p1.x == p2.x
*/
if (p1.x == p2.x)
{
return p3.x == p1.x &&
(p1.y <= p3.y && p3.y <= p2.y ||
p1.y >= p3.y && p3.y >= p2.y);
}
/**
* Reduce both fractions before comparing. This is where
* any performance issues would be.
*/
REDUCE(m1);
REDUCE(m2);
if (m1.num == m2.num && m1.denom == m2.denom)
{
return p1.x <= p3.x && p3.x <= p2.x;
}
return 0;
} |
|
| Back to top |
|
|
Skybuck Flying
Guest
|
| Posted:
Sun Sep 18, 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"
|
I ment start and end point should not be considered part of the line segment
;)
Both no big deal if it does... I can probably figure out a way to change it
etc.
Though your method looks like it doesn't include the start and ends points ?
Bye,
Skybuck. |
|
| Back to top |
|
|
glen herrmannsfeldt
Guest
|
| Posted:
Sun Sep 18, 2005 8:15 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
Skybuck Flying wrote:
| Quote: | "glen herrmannsfeldt" <gah@ugcs.caltech.edu> wrote in message
news:dPidne5UGqDIkbbeRVn-gg@comcast.com...
|
(snip)
| Quote: | Otherwise, if you select two end points somewhat randomly there is a
high probability that no floating point values lie on the segment
between them.
You are more then welcome to prove this very soon.
I'll shall do or attempt to do two things:
|
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.
-- glen |
|
| Back to top |
|
|
Guest
|
| Posted:
Sun Sep 18, 2005 8:15 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
Skybuck Flying wrote:
| Quote: | "glen herrmannsfeldt" <gah@ugcs.caltech.edu> wrote:
Skybuck Flying wrote:
It should be as exact/accurate as possible.
You really need to tell us what "this case" is.
You ll see quite soon the test program is done ;)
|
Ok, you are pissing people off with statements like this.
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.
Ok, perhaps a better way to ask you for more information, is this.
| Quote: | From what sort of *SOURCE* are your input points comming from? Are
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.
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.
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.
--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/ |
|
| Back to top |
|
|
Skybuck Flying
Guest
|
| Posted:
Sun Sep 18, 2005 8:15 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
<websnarf@gmail.com> wrote in message
news:1127020232.201983.291220@g49g2000cwa.googlegroups.com...
| Quote: | Skybuck Flying wrote:
"glen herrmannsfeldt" <gah@ugcs.caltech.edu> wrote:
Skybuck Flying wrote:
It should be as exact/accurate as possible.
You really need to tell us what "this case" is.
You ll see quite soon the test program is done ;)
Ok, you are pissing people off with statements like this.
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.
Ok, perhaps a better way to ask you for more information, is this.
From what sort of *SOURCE* are your input points comming from? Are
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.
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.
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.
|
The test program is "done" well not really but a first version is available
on the net.
VerificationProgramVersion009.zip
https://sourceforge.net/project/showfiles.php?group_id=53726
See the other usenet thread called "VerificationProgram009 etc" for more
details etc ;)
Bye,
Skybuck. |
|
| Back to top |
|
|
Skybuck Flying
Guest
|
| Posted:
Sun Sep 18, 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:0tOdndY89v1YcLHeRVn-3w@comcast.com...
| Quote: | Skybuck Flying wrote:
"glen herrmannsfeldt" <gah@ugcs.caltech.edu> wrote in message
news:dPidne5UGqDIkbbeRVn-gg@comcast.com...
(snip)
Otherwise, if you select two end points somewhat randomly there is a
high probability that no floating point values lie on the segment
between them.
You are more then welcome to prove this very soon.
I'll shall do or attempt to do two things:
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.
|
The test program is "done" well not really but a first version is available
on the net.
Which also includes your line. "My" second implementation has problems with
this line. The second method uses some sort of dot product or cross product.
Which is kinda surprising because I think Nicholas's implementation also
works like that... oh well ;)
My first implementation however... which I do fully understand still works
perfectly =D
Can you find/think up any other possibly problems ? ;)
See this link for the source code, binaries, data, etc, etc, etc.
VerificationProgramVersion009.zip
https://sourceforge.net/project/showfiles.php?group_id=53726
See the other usenet thread called "VerificationProgram009 etc" for more
details etc ;)
Bye,
Skybuck. |
|
| Back to top |
|
|
Skybuck Flying
Guest
|
| Posted:
Sun Sep 18, 2005 8:15 am Post subject:
Re: Point on Line Segment in 2D. Which code is faster ? Can |
|
|
"John Bode" <john_bode@my-deja.com> wrote in message
news:1127004301.572916.51700@z14g2000cwz.googlegroups.com...
| Quote: | Skybuck Flying wrote:
Hi,
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.
Here's another one to play with. It goes from the assumption that if
the slope from p1 to p2 is the same as the slope from p1 to p3, then p3
is colinear with p1 and p2. Then it checks x coordinates to see if p3
is on the segment between p1 and p2.
It expresses slope as rational numbers, so the arithmetic is integral.
It probably needs to be bulletproofed.
#include <stdio.h
typedef struct {
long x;
long y;
} point_t;
typedef struct {
long num;
long denom;
} rational_t;
#define REDUCE(frac) \
do { \
long e1=frac.num, \
e2=frac.denom, \
quot, rem = -1; \
long tmp; \
int done = 0; \
while(!done) \
{ \
if (e1 < e2) \
{ \
tmp = e1; \
e1 = e2; \
e2 = tmp; \
} \
quot = e1/e2; \
rem = e1 % e2; \
if (rem) \
e1 = rem; \
else \
done = 1; \
} \
frac.num /= e2; \
frac.denom /= e2; \
} while(0)
/**
* We are assuming that p1 and p2 have been ordered
* so that p1.x <= p2.x
*/
int isOnLine(point_t p1, point_t p2, point_t p3)
{
rational_t m1 = {p3.y - p1.y, p3.x - p1.x};
rational_t m2 = {p2.y - p1.y, p2.x - p1.x};
/**
* special case -- p1.x == p2.x
*/
if (p1.x == p2.x)
{
return p3.x == p1.x &&
(p1.y <= p3.y && p3.y <= p2.y ||
p1.y >= p3.y && p3.y >= p2.y);
}
/**
* Reduce both fractions before comparing. This is where
* any performance issues would be.
*/
REDUCE(m1);
REDUCE(m2);
if (m1.num == m2.num && m1.denom == m2.denom)
{
return p1.x <= p3.x && p3.x <= p2.x;
}
return 0;
}
|
Hi, cool stuff. I haven't had the time yet to look into this.
It would help if someone could make it more suited for my test program and
maybe make a nice little dll ?
Anyway maybe somebody can convert this to delphi as well.
The test program is "done" well not really but a first version is available
on the net.
VerificationProgramVersion009.zip
https://sourceforge.net/project/showfiles.php?group_id=53726
See the other usenet thread called "VerificationProgram009 etc" for more
details etc ;)
Bye,
Skybuck. |
|
| Back to top |
|
|
|
|
|
|
FAQ
Memberlist
Register
Profile
Log in to check your private messages
Log in