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

[Randy]

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

Skybuck Flying wrote:[color=blue]
> "Hans-Bernhard Broeker" <broeker@physik .rwth-aachen.de> wrote in message
> news:3p0cvdF86n t0U1@news.dfnci s.de...
>[color=green]
>>In comp.graphics.a lgorithms 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.][/color]
>
> 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.[/color]

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.a lgorithms 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.b orland-delphi. Nor comp.lang.asm, unless you want a
response written in assembly language.

That said, other appropriate forums might have included comp.programmin g
or *maybe* comp.theory.

....[color=blue][color=green]
>>
>>You need to define the task a good deal more cleanly before an
>>implementatio n 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?[/color]
>
>
> A 2D line segment defined by (x1,y1) - (x2,y2)[/color]

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.
[color=blue]
>[color=green]
>>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?[/color]
>
>
> As precise as possible. (Floating point precision, no rounding)[/color]

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

[David Hopwood]

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

[some off-topic newsgroups trimmed]

Skybuck Flying wrote:[color=blue]
> "Maarten Wiltink" <maarten@kitten sandcats.net> wrote:[color=green]
>>"Skybuck Flying" <nospam@hotmail .com> wrote:[color=darkred]
>>>"Nicholas Sherlock" <n_sherlock@hot mail.com> wrote:
>>>>Skybuck Flying wrote:[/color]
>>[color=darkred]
>>>>>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.0000000000000 1 ?
>>>
>>>Personally I don't like epsilons like this... it leaves room for
>>>error/malfunction ?[/color]
>>
>>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]
>
> That certainly won't do in this case etc.
>
> It should be as exact/accurate as possible.[/color]

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.h opwood@blueyond er.co.uk>

[Ketil Malde]

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

"Skybuck Flying" <nospam@hotmail .com> writes:
[color=blue]
> It should be as exact/accurate as possible.[/color]

Then use rational numbers?

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

[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:gvCdnayW-7Xzg7beRVn-vQ@comcast.com. ..[color=blue]
> Skybuck Flying wrote:
>
> (snip)
>[color=green]
> > That certainly won't do in this case etc.[/color]
>[color=green]
> > It should be as exact/accurate as possible.[/color]
>
> You really need to tell us what "this case" is.[/color]

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.

[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:dPidne5UGq DIkbbeRVn-gg@comcast.com. ..[color=blue]
> Skybuck Flying wrote:[color=green]
> > "Nicholas Sherlock" <n_sherlock@hot mail.com> wrote in message
> > news:dge6ot$ufs $3@lust.ihug.co .nz...[/color]
>
> (snip)
>[color=green][color=darkred]
> >>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.[/color][/color]
>[color=green]
> > Yes I figured that much. So this would mean the function returns true if
> > abs(blabla) is near zero ?[/color]
>[color=green]
> > Why use 0.00001 why not 0.0000001 or 0.0000000000000 1 ?[/color]
>[color=green]
> > Personally I don't like epsilons like this... it leaves room for
> > error/malfunction ?[/color]
>
> 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.[/color]

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.

[pete]

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

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

.... otherwise you might wind up learning how to use
relevant features of the C standard library.

--
pete

[nobody]

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

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

You have a gross and dangerous misunderstandin g 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.

[John Bode]

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

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

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;
}

[glen herrmannsfeldt]

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

Skybuck Flying wrote:
[color=blue]
> "glen herrmannsfeldt" <gah@ugcs.calte ch.edu> wrote in message
> news:dPidne5UGq DIkbbeRVn-gg@comcast.com. ..[/color]

(snip)
[color=blue][color=green]
>>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.[/color][/color]
[color=blue]
> You are more then welcome to prove this very soon.
> I'll shall do or attempt to do two things:[/color]

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

[websnarf@gmail.com]

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

Skybuck Flying wrote:[color=blue]
> "glen herrmannsfeldt" <gah@ugcs.calte ch.edu> wrote:[color=green]
> > Skybuck Flying wrote:[color=darkred]
> > > It should be as exact/accurate as possible.[/color]
> >
> > You really need to tell us what "this case" is.[/color]
>
> You ll see quite soon the test program is done ;)[/color]

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.[color=blue]
>From what sort of *SOURCE* are your input points comming from? Are[/color]
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/

[Skybuck Flying]

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


<websnarf@gmail .com> wrote in message
news:1127020232 .201983.291220@ g49g2000cwa.goo glegroups.com.. .[color=blue]
> Skybuck Flying wrote:[color=green]
> > "glen herrmannsfeldt" <gah@ugcs.calte ch.edu> wrote:[color=darkred]
> > > Skybuck Flying wrote:
> > > > It should be as exact/accurate as possible.
> > >
> > > You really need to tell us what "this case" is.[/color]
> >
> > You ll see quite soon the test program is done ;)[/color]
>
> 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.[color=green]
> >From what sort of *SOURCE* are your input points comming from? Are[/color]
> 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.[/color]

The test program is "done" well not really but a first version is available
on the net.

VerificationPro gramVersion009. zip

https://sourceforge.net/project/showfiles.php?group_id=53726

See the other usenet thread called "VerificationPr ogram009 etc" for more
details etc ;)

Bye,
Skybuck.

[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:0tOdndY89v 1YcLHeRVn-3w@comcast.com. ..[color=blue]
> Skybuck Flying wrote:
>[color=green]
> > "glen herrmannsfeldt" <gah@ugcs.calte ch.edu> wrote in message
> > news:dPidne5UGq DIkbbeRVn-gg@comcast.com. ..[/color]
>
> (snip)
>[color=green][color=darkred]
> >>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.[/color][/color]
>[color=green]
> > You are more then welcome to prove this very soon.
> > I'll shall do or attempt to do two things:[/color]
>
> 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]

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.

VerificationPro gramVersion009. zip

https://sourceforge.net/project/showfiles.php?group_id=53726

See the other usenet thread called "VerificationPr ogram009 etc" for more
details etc ;)

Bye,
Skybuck.

[Skybuck Flying]

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


"John Bode" <john_bode@my-deja.com> wrote in message
news:1127004301 .572916.51700@z 14g2000cwz.goog legroups.com...[color=blue]
> Skybuck Flying wrote:[color=green]
> > Hi,
> >
> > I needed a method to determine if a point was on a line segment in 2D.[/color][/color]
So I[color=blue][color=green]
> > googled for some help and so far I have evaluated two methods.
> >[/color]
>
> 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;
> }[/color]

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.

VerificationPro gramVersion009. zip

https://sourceforge.net/project/showfiles.php?group_id=53726

See the other usenet thread called "VerificationPr ogram009 etc" for more
details etc ;)

Bye,
Skybuck.

[alanglloyd@aol.com]

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

Why don't you make a region slightly larger than the line, and use
PtInRegion to check if the click is on the line.

var
hndRgn : hRGN;

const
LineSt : TPoint = (X:0; Y:0);
LineEnd : TPoint = (X:997; Y:512);
LineWidth : integer = 2;

procedure TForm1.FormCrea te(Sender: TObject);
var
PointArray : array[0..3] of TPoint;
LW : integer;
begin
LW := LineWidth;
PointArray[0] := Point(LineSt.X - LW, LineSt.Y - LW);
PointArray[1] := Point(LineEnd.X + LW, LineEnd.Y - LW);
PointArray[2] := Point(LineEnd.X + LW, LineEnd.Y + LW);
PointArray[3] := Point(LineSt.X - LW, LineSt.Y + LW);
hndRgn := CreatePolygonRg n(PointArray, 4, WINDING);
end;

procedure TForm1.FormMous eUp(Sender: TObject; Button: TMouseButton;
Shift: TShiftState; X, Y: Integer);
var
OnLine : boolean;
begin
StartPeriod; // timer start
OnLine := PtInRegion(hndR gn, X, Y);
EndPeriod; // timer stop
{indicate if on line}
if OnLine then
Shape1.Brush.Co lor := clLime
else
Shape1.Brush.Co lor := clRed;
{display time to check in region}
Label1.Caption := Format('%d microsecs',
[trunc(ScaleTime (ElapsedTime, ttMicroSecs))]);
end;

This gives about 13 microsecs for the first click (2 microsecs for
later ones) at the start of the line, and 17 microsecs for the first
click (7 microsecs for later ones) at the end of the line. This is with
a 2.5GHz PC.

I can't believe that this is too slow for you <g>.

Alan Lloyd

[Sander Vesik]

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

In comp.arch glen herrmannsfeldt <gah@ugcs.calte ch.edu> wrote:[color=blue]
> Skybuck Flying wrote:
>
> (snip)
>[color=green]
> > That certainly won't do in this case etc.[/color]
>[color=green]
> > It should be as exact/accurate as possible.[/color]
>
> 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.[/color]

Its rather clear he is interested in generating lots of usenet traffic
and not much else...
[color=blue]
>
> -- glen
>[/color]

--
Sander

+++ Out of cheese error +++