435,425 Members | 2,549 Online
Need help? Post your question and get tips & solutions from a community of 435,425 IT Pros & Developers. It's quick & easy.

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

65 Replies

 P: n/a 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; Cheers, Nicholas Sherlock Nov 15 '05 #2

 P: n/a "Nicholas Sherlock" wrote in message news:dg**********@lust.ihug.co.nz... 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; Congratulations, you just reposted the C/second method ;) Though the < 0.0000001 is new which I dont quite understand ;) Bye, Skybuck. Nov 15 '05 #3

 P: n/a "Nicholas Sherlock" wrote in message news:dg**********@lust.ihug.co.nz... 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; Besides it says OnLine ? I need OnLineSegment... See the difference ? Bye, Skybuck. Nov 15 '05 #4

 P: n/a 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; I had to rip it out of some other bit of code, so check it carefully against your data. Cheers, Nicholas Sherlock Nov 15 '05 #5

 P: n/a Skybuck Flying wrote: Besides it says OnLine ? I need OnLineSegment... See the difference ? The other code I posted does segment. Cheers, Nicholas Sherlock Nov 15 '05 #6

 P: n/a 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. Cheers, Nicholas Sherlock Nov 15 '05 #7

 P: n/a "Nicholas Sherlock" wrote in message news:dg**********@lust.ihug.co.nz... Skybuck Flying wrote: Besides it says OnLine ? I need OnLineSegment... See the difference ? The other code I posted does segment. Actually I have a confesion to make as well ;) The second method (the C method is flawed). I am writing a test/measure program, I still need to input some more verification data ;) Tomorrow or so it will be done and then I will post it so everybody can verify and test there goddamn methods lol =D Bye, Skybuck. Nov 15 '05 #8

 P: n/a * Removed from followup: comp.lang.asm sci.electronics.design In article , Nicholas Sherlock wrote: || 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; || || I had to rip it out of some other bit of code, so check it carefully || against your data. || || Cheers, || Nicholas Sherlock Let's leave the two bounds out for clarity: ((x2 - x1) * (y3 - y1)) - ((x3 - x1) * (y2 - y1)) < epsilon Distribute: +x2y3 -x2y1 -x1y3 +x1y1 -x3y2 +x3y1 +x1y2 -x1y1 < epsilon Cancel: +x2y3 -x2y1 -x1y3 -x3y2 +x3y1 +x1y2 < epsilon Reorder: -x1y3 +x1y2 -x2y1 +x3y1 +x2y3 -x3y2 < epsilon Inverse distribute: (y2-y3)*x1 + (x3-x2)*y1 + x2*y3-x3*y2 < epsilon Name constants: a*x1 + b*y1 + c < epsilon a,b,c are constant. For a given line, you can precompute: a = y2-y3 b = x3-x2 c = x2*y3 - x3*y2 This helps when you want to check a lot of points against the same line, because it involves only two multiplications, two additions and a comparison against epsilon. The original formula had 5 additions (or subtractions) instead. It corresponds to the general formula for a line in 2d: ax + by + c = 0 Incidentally, vector (a,b) is a normal vector of the line: perpendicular to the direction of the line. For checking the bounds of the line segment, just precomputing the bounding box and checking against that will do. Ciao. Vincent. -- Vincent Zweije | "If you're flamed in a group you | don't read, does anybody get burnt?" [Xhost should be taken out and shot] | -- Paul Tomblin on a.s.r. Nov 15 '05 #9

 P: n/a "Nicholas Sherlock" wrote in message news:dg**********@lust.ihug.co.nz... 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 ? 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; I have asked a question on the math newsgroup and also algorithms newsgroup if the points of the line segment are to be considered part of the line segment. This code considers the points to be part of the line segment seeing the >= and <= instead of > and <. I myself choose to exclude the points from the line segment. Since I will probably have to treat overlapping points as a special case, so those will have to be specially detected etc by another routine to keep things simple ;) As somebody else already pointed out it's free to interpretation ? I wonder if others agree with that, so far I have only see one reply to it. Anyway this construction is kinda interesting since it contains controversial/oppositing conditions so not all conditions will be checked since some will jump out/forward prematurely etc... I wonder what the worst case would be... Maybe 8 compares ? In that case it would be worse than both other methods which only have 7 to 5 compares. (7 for the C method which is like this one... and only 5 for my version ^^ =D ) Bye, Skybuck. Nov 15 '05 #10

 P: n/a "Skybuck Flying" wrote in message news:dg**********@news6.zwoll1.ov.home.nl... "Nicholas Sherlock" wrote in message news:dg**********@lust.ihug.co.nz... 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. Groetjes, Maarten Wiltink Nov 15 '05 #12

 P: n/a "Maarten Wiltink" wrote in message news:43***********************@news.xs4all.nl... "Skybuck Flying" wrote in message news:dg**********@news6.zwoll1.ov.home.nl... "Nicholas Sherlock" wrote in message news:dg**********@lust.ihug.co.nz... 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. Bye, Skybuck. Nov 15 '05 #13

 P: n/a Skybuck Flying wrote: "Nicholas Sherlock" wrote in message news:dg**********@lust.ihug.co.nz... (snip) Floating point math is always inaccurate as most numbers cannot beexactly represented. This bit basically takes care of that by adding afudge 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. -- glen Nov 15 '05 #14

 P: n/a 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 expect everyone to help you, but don't seem interested in helping much yourself. -- glen Nov 15 '05 #15

 P: n/a [some off-topic newsgroups trimmed] Skybuck Flying wrote: "Maarten Wiltink" wrote:"Skybuck Flying" wrote:"Nicholas Sherlock" 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 beexactly represented. This bit basically takes care of that by addinga fudge factor.Yes I figured that much. So this would mean the function returns trueif 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 forerror/malfunction ?Some real life logic: once in a graphics rendering lab assignment, wewere instructed to approximate Bezier curves. This is an iterativeprocess; the stop condition was for the error to become less thenhalf a pixel. For visualisation on a raster display, that is exactlywhat'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 Nov 15 '05 #17

 P: n/a "Skybuck Flying" writes: 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 Nov 15 '05 #18

 P: n/a "glen herrmannsfeldt" wrote in message news:gv********************@comcast.com... 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. Nov 15 '05 #19

 P: n/a "glen herrmannsfeldt" wrote in message news:dP********************@comcast.com... Skybuck Flying wrote: "Nicholas Sherlock" wrote in message news:dg**********@lust.ihug.co.nz... (snip)Floating point math is always inaccurate as most numbers cannot beexactly represented. This bit basically takes care of that by adding afudge 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. Nov 15 '05 #20

 P: n/a Skybuck Flying 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 etc... .... otherwise you might wind up learning how to use relevant features of the C standard library. -- pete Nov 15 '05 #21

 P: n/a "Skybuck Flying" wrote: Using epsilon's and stuff like should probably be prevented as much aspossible 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. Nov 15 '05 #22

 P: n/a 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 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; } Nov 15 '05 #23

 P: n/a Skybuck Flying wrote: "glen herrmannsfeldt" wrote in message news:dP********************@comcast.com... (snip) Otherwise, if you select two end points somewhat randomly there is ahigh probability that no floating point values lie on the segmentbetween 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 Nov 15 '05 #24

 P: n/a Skybuck Flying wrote: "glen herrmannsfeldt" 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. -- Paul Hsieh http://www.pobox.com/~qed/ http://bstring.sf.net/ Nov 15 '05 #25

 P: n/a wrote in message news:11**********************@g49g2000cwa.googlegr oups.com... Skybuck Flying wrote: "glen herrmannsfeldt" 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/show...group_id=53726 See the other usenet thread called "VerificationProgram009 etc" for more details etc ;) Bye, Skybuck. Nov 15 '05 #26

 P: n/a "glen herrmannsfeldt" wrote in message news:0t********************@comcast.com... Skybuck Flying wrote: "glen herrmannsfeldt" wrote in message news:dP********************@comcast.com... (snip)Otherwise, if you select two end points somewhat randomly there is ahigh probability that no floating point values lie on the segmentbetween 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/show...group_id=53726 See the other usenet thread called "VerificationProgram009 etc" for more details etc ;) Bye, Skybuck. Nov 15 '05 #27

 P: n/a "John Bode" wrote in message news:11*********************@z14g2000cwz.googlegro ups.com... 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 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/show...group_id=53726 See the other usenet thread called "VerificationProgram009 etc" for more details etc ;) Bye, Skybuck. Nov 15 '05 #28

 P: n/a 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.FormCreate(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 := CreatePolygonRgn(PointArray, 4, WINDING); end; procedure TForm1.FormMouseUp(Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer); var OnLine : boolean; begin StartPeriod; // timer start OnLine := PtInRegion(hndRgn, X, Y); EndPeriod; // timer stop {indicate if on line} if OnLine then Shape1.Brush.Color := clLime else Shape1.Brush.Color := 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 . Alan Lloyd Nov 15 '05 #29

 P: n/a In comp.arch glen herrmannsfeldt wrote: 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 expect everyone to help you, but don't seem interested in helping much yourself. Its rather clear he is interested in generating lots of usenet traffic and not much else... -- glen -- Sander +++ Out of cheese error +++ Nov 15 '05 #30

 P: n/a "John Bode" wrote in message news:11*********************@z14g2000cwz.googlegro ups.com... 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 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; } Ok, your method has been added to the verification program. However during verification the algorithm hangs at this data: Verifieing: Type index: 1 Type description: Diagonal line with point inside line segment Data index: 2 Data description: positive area, third crossed Which is this one: AddGeneratedVerificationData( 'positive area, third crossed', 200,2000, 3000,100, 0.3, 0.0 ); Which means: X1 := 200; Y1 := 2000; X2 := 3000; Y2 := 100; PX := 1040; // generated/calculated PY := 1430; // generated/calculated I put your source code in a library/DLL which looks like this: JOHNBODERATIONALMETHOD_API BOOL __stdcall PointOnLineSegmentIn2D( double StartX, double StartY, double EndX, double EndY, double PointX, double PointY ) { point_t p1; point_t p2; point_t p3; if (StartX <= EndX) { p1.x = long(StartX); // typecast to prevent loss of data warning p1.y = long(StartY); // typecast to prevent loss of data warning p2.x = long(EndX); // typecast to prevent loss of data warning p2.y = long(EndY); // typecast to prevent loss of data warning } else { p1.x = long(EndX); // typecast to prevent loss of data warning p1.y = long(EndY); // typecast to prevent loss of data warning p2.x = long(StartX); // typecast to prevent loss of data warning p2.y = long(StartY); // typecast to prevent loss of data warning } p3.x = long(PointX); // typecast to prevent loss of data warning p3.y = long(PointY); // typecast to prevent loss of data warning return isOnLine(p1,p2,p3); } It might be hanging because Y2 is smaller than Y1 ? or maybe there is another problem ? ;) Bye, Skybuck. Nov 15 '05 #31

 P: n/a Hi John, your posted method has now also been added to the program/project/etc in VerificationProgram0.10 for PointOnLineSegmentIn2D =D (Though the dll has been disabled by simply renaming it until the hang/bug is fixed ;) ) Hello Peeps. Here is what's new ;) version 0.10 created on 18 and 19 september 2005 by Skybuck Flying + Some code moved to other/new units etc. + New source and binary implementation added: Nils from www.simdesign.nl + New source and binary implementation added: Skybuck Flying method 3 + New binary implementation added: JohnBodeRationalMethod (source in visual cpp). + ProjectGroups added + Each verification is displayed in case a binary plug in hangs.. then at least it's possible to see at which verification it hangs. Get the source and binaries from: https://sourceforge.net/project/show...group_id=53726 =D Bye, Skybuck. "John Bode" wrote in message news:11*********************@z14g2000cwz.googlegro ups.com... 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 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; } Nov 15 '05 #32

 P: n/a wrote in message news:11*********************@f14g2000cwb.googlegro ups.com... Why don't you make a region slightly larger than the line, and use PtInRegion to check if the click is on the line. Not too shabby ;) This would/could be pretty good for gui's where the user needs to pick a line etc. That's just one application of this method. Another application is for massive calculations of all kinds of geometry algorithms etc. Your method is kinda funny since it uses windows to do it's thing. Tomorrow or so I will add it as well to see how it performance, speed wise, compared to all the other methods =D That's going to be much fun ;) I also wonder how stable it would be... probably pretty stable though ;) I also wonder how large or small the values could be. So this method works with integers etc... small values would get rounded to zero or so or one like 0.05 and 0.0002 etc.. and point 0.06 whatever... then this method would always return true or something like that ;) could be fun and maybe even handy as well =D Bye, Skybuck. var hndRgn : hRGN; const LineSt : TPoint = (X:0; Y:0); LineEnd : TPoint = (X:997; Y:512); LineWidth : integer = 2; procedure TForm1.FormCreate(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 := CreatePolygonRgn(PointArray, 4, WINDING); end; procedure TForm1.FormMouseUp(Sender: TObject; Button: TMouseButton; Shift: TShiftState; X, Y: Integer); var OnLine : boolean; begin StartPeriod; // timer start OnLine := PtInRegion(hndRgn, X, Y); EndPeriod; // timer stop {indicate if on line} if OnLine then Shape1.Brush.Color := clLime else Shape1.Brush.Color := 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. Nice one ;) I can't believe that this is too slow for you . For one click no :) For massive calculations I dont know lol =D Bye, Skybuck. Nov 15 '05 #33

 P: n/a we******@gmail.com wrote (in article <11**********************@g49g2000cwa.googlegroups .com>): Skybuck Flying wrote: "glen herrmannsfeldt" 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. Shouldn't be a surprise. If you search newsgroup archives for "Skybuck" you'll find his been doing that sort of thing in a lot of different groups for a long time. -- Randy Howard (2reply remove FOOBAR) Nov 15 '05 #34

 P: n/a On Mon, 19 Sep 2005 08:05:41 GMT, Randy Howard wrote: we******@gmail.com wrote(in article<11**********************@g49g2000cwa.googlegroup s.com>): Skybuck Flying wrote: "glen herrmannsfeldt" 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.Shouldn't be a surprise. If you search newsgroup archives for"Skybuck" you'll find his been doing that sort of thing in a lotof different groups for a long time. Yep. I changed his filter from specific newsgroup to global a long time ago. -- Al Balmer Balmer Consulting re************************@att.net Nov 15 '05 #35

 P: n/a "glen herrmannsfeldt" wrote in message news:0t********************@comcast.com... Skybuck Flying wrote: "glen herrmannsfeldt" wrote in message news:dP********************@comcast.com... (snip)Otherwise, if you select two end points somewhat randomly there is ahigh probability that no floating point values lie on the segmentbetween 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. I wrote a little program which uses rational numbers and floating point numbers and shows the difference. The rational number version is able to perfectly calculate the point. The floating point version fails miserably at it ;) The rational number version is about 20 times slower than the floating point version ;) program started (Rational) PointX in rational notation: 768/5 (Rational) PointY in rational notation: 2991/10 (Rational) PointX in real notation: 153.6000000000000000 (Rational) PointY in real notation: 299.1000000000000000 (Rational) ticks: 282 (Rational) time (in seconds): 0.0000787809623849 (Floating point) PointX: 153.5999999999999940 (Floating point) PointY: 299.0999999999999660 (Floating point) ticks: 14 (Floating point) time (in seconds): 0.0000039111116078 press enter to exit Here is the source code. Thanks to delphi fundamentals for the Trational class etc =D Now for the final question ;) 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 ? ;) program TestRationalNumbers; {\$APPTYPE CONSOLE} uses SysUtils, cUtils in 'Utils\cUtils.pas', cStrings in 'Utils\cStrings.pas', cRational in 'Maths\cRational.pas', cMaths in 'Maths\cMaths.pas', Windows; // rational number versions: procedure calc_perpendicular( var x, y : Trational ); var temp_x, temp_y : Trational; begin temp_x := Trational.Create; temp_y := Trational.Create; // temp_x := -y; temp_x.Assign( y ); temp_x.Negate; // temp_y := x; temp_y.Assign( x ); // x := temp_x; // y := temp_y; x.Assign( temp_x ); y.Assign( temp_y ); temp_x.Destroy; temp_y.Destroy; end; procedure calc_normalize( var x, y : Trational ); var temp_squared_x : Trational; temp_squared_y : Trational; temp_length : Trational; begin temp_squared_x := Trational.Create; temp_squared_y := Trational.Create; temp_length := Trational.Create; // temp_length := sqrt( (x*x) + (y*y) ); temp_squared_x.Assign( x ); temp_squared_y.Assign( y ); temp_squared_x.Sqr; temp_squared_y.Sqr; temp_length.Assign( temp_squared_x ); temp_length.Add( temp_squared_y ); temp_length.Sqrt; // if temp_length<>0 then if not temp_length.IsZero then begin // x := x / temp_length; // y := y / temp_length; x.Divide( temp_length ); y.Divide( temp_length ); end; temp_squared_x.Destroy; temp_squared_y.Destroy; temp_length.Destroy; end; procedure calc_normal( _x1,_y1, _x2,_y2 : Trational; var _normal_x, _normal_y : Trational ); begin // _normal_x := _x2-_x1; // _normal_y := _y2-_y1; _normal_x.Assign( _x2 ); _normal_y.Assign( _y2 ); _normal_x.Subtract( _x1 ); _normal_y.Subtract( _y1 ); // calculate perpendicular "vector". calc_perpendicular( _normal_x, _normal_y ); // divide vector by it's own length there by creating a "normal" :) calc_normalize( _normal_x, _normal_y ); end; // original double versions // using flawed floating point shit ;) // helper procedure to generate points on or near line segments procedure GeneratePointForLineSegment( StartX, StartY, EndX, EndY : Trational; DistanceFromStart : Trational; // distance from start // < 0 is before start // 0 is on start // 0.5 is on center // 1 is one end // > 1 is after end DistanceFromLine : Trational; // closest distance from line // follows the normal // positive is left side of line // zero is on line // negative is right side of line var px, py : Trational ); var NX, NY : Trational; begin NX := Trational.Create; NY := Trational.Create; // theory of method1 ;) // PX := StartX + DistanceFromStart * (EndX - StartX); // PY := StartY + DistanceFromStart * (EndY - StartY); PX.Assign( EndX ); PX.Subtract( StartX ); PX.Multiply( DistanceFromStart ); PX.Add( StartX ); PY.Assign( EndY ); PY.Subtract( StartY ); PY.Multiply( DistanceFromStart ); PY.Add( StartY ); // create a perpendicular point... we do this by calculating a normal and multiplieing // this with the distance from the line and adding this to px and py ;) // calculate normilized normal for line calc_normal( StartX,StartY, EndX,EndY, NX,NY ); // offset the point along the normal with distance from line // PX := PX + NX * DistanceFromLine; // PY := PY + NY * DistanceFromLine; NX.Multiply( DistanceFromLine ); NY.Multiply( DistanceFromLine ); PX.Add( NX ); PY.Add( NY ); NX.Destroy; NY.Destroy; end; procedure org_calc_perpendicular( var x, y : double ); var temp_x, temp_y : double; begin temp_x := -y; temp_y := x; x := temp_x; y := temp_y; end; procedure org_calc_normalize( var x, y : double ); var temp_length : double; begin temp_length := sqrt( (x*x) + (y*y) ); if temp_length<>0 then begin x := x / temp_length; y := y / temp_length; end; end; procedure org_calc_normal( _x1,_y1, _x2,_y2 : double; var _normal_x, _normal_y : double ); begin _normal_x := _x2-_x1; _normal_y := _y2-_y1; // calculate perpendicular "vector". org_calc_perpendicular( _normal_x, _normal_y ); // divide vector by it's own length there by creating a "normal" :) org_calc_normalize( _normal_x, _normal_y ); end; // helper procedure to generate points on or near line segments procedure org_GeneratePointForLineSegment( StartX, StartY, EndX, EndY : double; DistanceFromStart : double; // distance from start // < 0 is before start // 0 is on start // 0.5 is on center // 1 is one end // > 1 is after end DistanceFromLine : double; // closest distance from line // follows the normal // positive is left side of line // zero is on line // negative is right side of line var px, py : double ); var NX, NY : double; begin // theory of method1 ;) PX := StartX + DistanceFromStart * (EndX - StartX); PY := StartY + DistanceFromStart * (EndY - StartY); // create a perpendicular point... we do this by calculating a normal and multiplieing // this with the distance from the line and adding this to px and py ;) // calculate normilized normal for line org_calc_normal( StartX,StartY, EndX,EndY, NX,NY ); // offset the point along the normal with distance from line PX := PX + NX * DistanceFromLine; PY := PY + NY * DistanceFromLine; end; var vHighPerformanceCounterFrequency : int64; vCounter1 : int64; vCounter2 : int64; vStartX, vStartY, vEndX, vEndY, vPointX, vPointY, vDistanceFromStart, vDistanceFromLine : Trational; vOrgStartX, vOrgStartY, vOrgEndX, vOrgEndY, vOrgPointX, vOrgPointY, vOrgDistanceFromStart, vOrgDistanceFromLine : double; vMeasurementsEnabled : boolean; vRationalTicks : int64; vRationalTime : double; vFloatingPointTicks : int64; vFloatingPointTime : double; begin writeln('program started'); vMeasurementsEnabled := true;; vRationalTicks := 0; vRationalTime := 0; vFloatingPointTicks := 0; vFloatingPointTime := 0; if vMeasurementsEnabled then begin if not QueryPerformanceFrequency( vHighPerformanceCounterFrequency ) then begin writeln('High performance counter not present, speed measurements disabled'); vMeasurementsEnabled := false; end; end; vStartX := Trational.Create; vStartY := Trational.Create; vEndX := Trational.Create; vEndY := Trational.Create; vPointX := Trational.Create; vPointY := Trational.Create; vDistanceFromStart := Trational.Create; vDistanceFromLine := Trational.Create; vStartX.Assign( 0, 1 ); vStartY.Assign( 0, 1 ); vEndX.Assign( 512, 1 ); vEndY.Assign( 997, 1 ); vDistanceFromStart.Assign( 3, 10 ); vDistanceFromLine.Assign( 0, 1 ); if vMeasurementsEnabled then begin QueryPerformanceCounter( vCounter1 ); end; GeneratePointForLineSegment( vStartX, vStartY, vEndX, vEndY, vDistanceFromStart, vDistanceFromLine, vPointX, vPointY ); if vMeasurementsEnabled then begin QueryPerformanceCounter( vCounter2 ); vRationalTicks := vCounter2-vCounter1; vRationalTime := ( (vCounter2-vCounter1)/ vHighPerformanceCounterFrequency ); end; writeln; writeln( '(Rational) PointX in rational notation: ', vPointX.AsString ); writeln( '(Rational) PointY in rational notation: ', vPointY.AsString ); writeln; writeln( '(Rational) PointX in real notation: ', vPointX.AsReal : 16 : 16 ); writeln( '(Rational) PointY in real notation: ', vPointY.AsReal : 16 : 16 ); if vMeasurementsEnabled then begin writeln('(Rational) ticks: ', vRationalTicks ); writeln('(Rational) time (in seconds): ', vRationalTime : 16 : 16 ); end; vOrgStartX := 0.0; vOrgStartY := 0.0; vOrgEndX := 512.0; vOrgEndY := 997.0; vOrgDistanceFromStart := 0.3; vOrgDistanceFromLine := 0.0; if vMeasurementsEnabled then begin QueryPerformanceCounter( vCounter1 ); end; org_GeneratePointForLineSegment( vOrgStartX, vOrgStartY, vOrgEndX, vOrgEndY, vOrgDistanceFromStart, vOrgDistanceFromLine, vOrgPointX, vOrgPointY ); if vMeasurementsEnabled then begin QueryPerformanceCounter( vCounter2 ); vFloatingPointTicks := vCounter2-vCounter1; vFloatingPointTime := ( (vCounter2-vCounter1)/ vHighPerformanceCounterFrequency ); end; writeln; writeln( '(Floating point) PointX: ', vOrgPointX : 16 : 16 ); writeln( '(Floating point) PointY: ', vOrgPointY : 16 : 16 ); if vMeasurementsEnabled then begin writeln('(Floating point) ticks: ', vFloatingPointTicks ); writeln('(Floating point) time (in seconds): ', vFloatingPointTime : 16 : 16 ); end; vStartX.Destroy; vStartY.Destroy; vEndX.Destroy; vEndY.Destroy; vPointX.Destroy; vPointY.Destroy; vDistanceFromStart.Destroy; vDistanceFromLine.Destroy; writeln; writeln('press enter to exit'); readln; writeln('program finished'); end. Bye, Skybuck. Nov 15 '05 #36

 P: n/a "Nicholas Sherlock" wrote in message news:dg**********@lust.ihug.co.nz... 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 Nov 15 '05 #38

 P: n/a "glen herrmannsfeldt" wrote in message news:gv********************@comcast.com... 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 You expect everyone to help you, but don't seem interested in helping much yourself. No on the contrary ;) See above lol. Bye, Skybuck. Nov 15 '05 #39

 P: n/a "nobody" wrote in message news:43********************************@4ax.com... "Skybuck Flying" wrote:Using epsilon's and stuff like should probably be prevented as much aspossible 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. I don't need to understand fully how floating point works. Sometimes I forget about rounding errors, so this thread was a nice refreshment. However in the back of my mind I know floating points are inaccurate, that is why I requested the methods to be "as accurate as possible". "as possible" meaning as possibly as *you* can get it without being to fricking slow lol =D The epsilon method is flawed in my mind since it assumes the points are quite large but in fact could be quite small thereby completely failing. Maybe you have a gross and dangerous misunderstanding of using a smudge factor/epsilon ;) I also don't like to study flawed/worthless shit like floating point format etc... I rather spent my time finding solutions to this shit lol =D. So far I have found a better alternative which is a rational number library... it still uses floating points inside which are used to represent the rational numbers but since it uses fractions it should be a lot more accurate than just using floating points directly ;) Another solution might be a fixed point library =D Bye, Skybuck. Nov 15 '05 #40

 P: n/a Skybuck Flying wrote: "nobody" wrote in message news:43********************************@4ax.com..."Skybuck Flying" wrote:Using epsilon's and stuff like should probably be prevented as much aspossible since those are common forms of errors etc and limitationsYou have a gross and dangerous misunderstanding of principles of doingnumerical 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. Nicholas Sherlock Nov 15 '05 #41

 P: n/a wrote in message news:11**********************@g49g2000cwa.googlegr oups.com... Skybuck Flying wrote: "glen herrmannsfeldt" 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. Lol, don't get carried away ;) Relax, take a break, it's never been my intention to piss anybody off. Though I can understand the frustration some people might be having because the requirements seem to be impossible to unite with floating points because of floating point rounding errors. Those people should really try and find some nice rational number or fixed point library and poof your frustration will turn into pure relaxation lol =D Here's the thing, the "epsilon thing" is far and away the most practical way of doing this; but just as a matter of correctness, you actually should not choose a constant epsilon. The correct epsilon will depend on the magnitude of the coordinates for the original segment points. For example it would be easy to construct an example where the best correct epsilon is a million. And how would such a dynamic epsilon be determined or constructed ? ;) Besides from that... the code will have to be modified to isolate the rounding error... which might be quite difficult sometimes (?) or maybe not.. but just extra boring work which also slows down the code ;) Ok, perhaps a better way to ask you for more information, is this.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. This is a good point you make. The source that constructs the points could introduce rounding errors... Then the method which checks the points could also introduce the same rounding errors thereby cancelling the rounding errors against each other and still returning success while in reality the point is slighty wrong/besides the line... other methods might thus correctly detect this. The verification program would then verify this correct method as being flawed which is not the case. It's exactly the opposite =D Thus the verification program needs to be improved to use more accurate point construction.. for example by using rational numbers or fixed point numbers ;) The problem with this is that starting with an x and computing a y, or the other way around will not necessarily yield the same results. Further more if you compute the point as (alpha * p_0 + (1-alpha)* p_1) (which might be *WAY* harder to match -- intuitively it seems so to me, but I don't have a 100% clear idea), you will again get different LSB round offs. Yeah, I understand what you mean =D So I hope you understand that these accuracy issues are pretty integral to what it is that you want to do. Without more information from you, I don't believe that anyone can suggest anything else more with any expectation of it necessarily working better. At this point I disagree... math is math... it shouldn't matter what the source of the information/variables are. You all have been helpfull at pointing out the inaccuracy problems =D Bye, Skybuck. -- Paul Hsieh http://www.pobox.com/~qed/ http://bstring.sf.net/ Nov 15 '05 #42

 P: n/a Skybuck Flying wrote: (snip) I don't need to understand fully how floating point works. Sometimes I forget about rounding errors, so this thread was a nice refreshment. However in the back of my mind I know floating points are inaccurate, that is why I requested the methods to be "as accurate as possible". "as possible" meaning as possibly as *you* can get it without being to fricking slow lol =D The epsilon method is flawed in my mind since it assumes the points are quite large but in fact could be quite small thereby completely failing. It is not only floating point, but that usually makes it worse. My example of (0,0) and (997,512) is fixed point. There are no points on the line segment between them in fixed point. -- glen Nov 15 '05 #43

 P: n/a "David Hopwood" wrote in message news:VP******************@fe1.news.blueyonder.co.u k... [some off-topic newsgroups trimmed] Skybuck Flying wrote: "Maarten Wiltink" wrote:"Skybuck Flying" wrote:"Nicholas Sherlock" 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 trueif 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 forerror/malfunction ?Some real life logic: once in a graphics rendering lab assignment, wewere instructed to approximate Bezier curves. This is an iterativeprocess; the stop condition was for the error to become less thenhalf a pixel. For visualisation on a raster display, that is exactlywhat'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. Not quite... it depends on the input/data and how the floating points are used. The rational number library uses floating points but since it uses them only to represent fractions like 2/3 which could also be represented with integers... but it probably uses floating points for more convenience and internal conversions etc.. it will be a lot more accurate... but at some point it might again get inaccurate ;) Bye, Skybuck. -- David Hopwood Nov 15 '05 #44

 P: n/a "Ketil Malde" wrote in message news:eg************@polarvier.ii.uib.no... "Skybuck Flying" writes: It should be as exact/accurate as possible. Then use rational numbers? Excellent idea... done that ;) Bye, Skybuck. -k -- If I haven't seen further, it is by standing in the footprints of giants Nov 15 '05 #45

 P: n/a "Skybuck Flying" writes: Can you still find a point which would in theory be on the line segment but would still be mis-calculated by the rational number version ? ;) One that overflows your rational number implementation, perhaps? (If it uses bignums, you may have to exhaust the heap). -k -- If I haven't seen further, it is by standing in the footprints of giants Nov 15 '05 #46

 P: n/a Maarten Wiltink wrote: 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/ Nov 15 '05 #47

 P: n/a "Skybuck Flying" wrote: The epsilon method is flawed in my mind since it assumes the points arequite 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. Nov 15 '05 #48

 P: n/a "glen herrmannsfeldt" wrote in message news:4r********************@comcast.com... 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. Nov 15 '05 #49

 P: n/a "Nicholas Sherlock" wrote in message news:dg**********@lust.ihug.co.nz... Skybuck Flying wrote: "nobody" wrote in message news:43********************************@4ax.com..."Skybuck Flying" wrote:Using epsilon's and stuff like should probably be prevented as much aspossible since those are common forms of errors etc and limitationsYou have a gross and dangerous misunderstanding of principles of doingnumerical 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 Nicholas Sherlock Nov 15 '05 #50

65 Replies

### This discussion thread is closed

Replies have been disabled for this discussion.