Determine straight line
-
Hello everybody, i am having n-number of points like p1(x,y), p2(x,y), p3(x,y), .... pn(x,y). All points lie on a single line.(either a curve or a straight line). i would like to find, using those points, whether that line is straight or not straight. i googled and tried some of the methods given in examples, (straight line equation, finding if collinear) but those are not working fine even for straight line also. i am using visual studio 2008 with win32 (not MFC). Any ideas ? Thanks in advance, A. Gopinath.
-
Hello everybody, i am having n-number of points like p1(x,y), p2(x,y), p3(x,y), .... pn(x,y). All points lie on a single line.(either a curve or a straight line). i would like to find, using those points, whether that line is straight or not straight. i googled and tried some of the methods given in examples, (straight line equation, finding if collinear) but those are not working fine even for straight line also. i am using visual studio 2008 with win32 (not MFC). Any ideas ? Thanks in advance, A. Gopinath.
-
Hello everybody, i am having n-number of points like p1(x,y), p2(x,y), p3(x,y), .... pn(x,y). All points lie on a single line.(either a curve or a straight line). i would like to find, using those points, whether that line is straight or not straight. i googled and tried some of the methods given in examples, (straight line equation, finding if collinear) but those are not working fine even for straight line also. i am using visual studio 2008 with win32 (not MFC). Any ideas ? Thanks in advance, A. Gopinath.
One way would be by using slope. Find the slope of the line corresponding to the first two points (y-coord of p2 - y-coord of p1) / (x-coord of p2 - x-coord of p1). Find the slopes of the lines corresponding to all other points (with respect to the first point), say (y-coord of pk - y-coord of p1) / (x-coord of pk - x-coord of p1), where k varies from 3 to n. All of these slopes should be within a reasonable tolerance band. And, since all of these lines pass through p1, they all would lie on the same straight line if they fell within the tolerance band. The above would not work if the x-coordinates of p2 and p1 are the same (because denominator would be zero). In that case, you choose a point whose x-coordinate is unique as the reference point. Not sure whether this is the most efficient way, but it certainly a way of achieving what you want.
-
The problem is one of mathematics not programming; once you find the mathematical solution, converting it to C/C++ is the easy part.
One of these days I'm going to think of a really clever signature.
-
One way would be by using slope. Find the slope of the line corresponding to the first two points (y-coord of p2 - y-coord of p1) / (x-coord of p2 - x-coord of p1). Find the slopes of the lines corresponding to all other points (with respect to the first point), say (y-coord of pk - y-coord of p1) / (x-coord of pk - x-coord of p1), where k varies from 3 to n. All of these slopes should be within a reasonable tolerance band. And, since all of these lines pass through p1, they all would lie on the same straight line if they fell within the tolerance band. The above would not work if the x-coordinates of p2 and p1 are the same (because denominator would be zero). In that case, you choose a point whose x-coordinate is unique as the reference point. Not sure whether this is the most efficient way, but it certainly a way of achieving what you want.
-
Hello everybody, i am having n-number of points like p1(x,y), p2(x,y), p3(x,y), .... pn(x,y). All points lie on a single line.(either a curve or a straight line). i would like to find, using those points, whether that line is straight or not straight. i googled and tried some of the methods given in examples, (straight line equation, finding if collinear) but those are not working fine even for straight line also. i am using visual studio 2008 with win32 (not MFC). Any ideas ? Thanks in advance, A. Gopinath.
Typically this is where you'd post questions regarding algorithms: http://www.codeproject.com/Forums/326859/Algorithms.aspx[^]
-
Hello Amarnath, yes, i tried this method also, but iam getting like 0.000002 or something like difference which fails the condition checking. rounding off will solve the solution ? is that right method? Regards, A. Gopinath.
You mean, that your slope value is 0.000002? This means that your line is almost horizontal. Your tolerance values would have to be at least 1/1000 or 1/10000 of your "average" slope value. Then, it would indicate that these points are on a straight line. (You need to use a "double" type to store these numbers, and a "float" may not suffice). By the way, what is the purpose of this exercise? That purpose would in some sense determine the method of straight-line detection.
-
You mean, that your slope value is 0.000002? This means that your line is almost horizontal. Your tolerance values would have to be at least 1/1000 or 1/10000 of your "average" slope value. Then, it would indicate that these points are on a straight line. (You need to use a "double" type to store these numbers, and a "float" may not suffice). By the way, what is the purpose of this exercise? That purpose would in some sense determine the method of straight-line detection.
-
Typically this is where you'd post questions regarding algorithms: http://www.codeproject.com/Forums/326859/Algorithms.aspx[^]
-
Hello Amarnath, yes, i tried this method also, but iam getting like 0.000002 or something like difference which fails the condition checking. rounding off will solve the solution ? is that right method? Regards, A. Gopinath.
One more way would be by using the cross product. Take two points, say p1 and p2 as reference. Consider the vector p1-p2. Now, take a point pk, and hence that vector p1-pk. Find the cross product of these two vectors (p1-p2 and p1-pk). That cross product should be near zero (all three components of the cross product) if the points are collinear. Repeat this for all points pk (k belonging to the set 3 to n).
-
Hello, i will try using "double" type. actually this is related 3D project, need to find straight line or not. Thanks again, A. Gopinath.
- Take the first and last points to build the 3D law of their straightness - Define the fluctuation radius as "allowed error" - All other points must lie in the "pipe" => => any point projection onto the law(1) may not be greather as the radius(2) :)
They sought it with thimbles, they sought it with care; They pursued it with forks and hope; They threatened its life with a railway-share; They charmed it with smiles and soap. :)
-
Hello everybody, i am having n-number of points like p1(x,y), p2(x,y), p3(x,y), .... pn(x,y). All points lie on a single line.(either a curve or a straight line). i would like to find, using those points, whether that line is straight or not straight. i googled and tried some of the methods given in examples, (straight line equation, finding if collinear) but those are not working fine even for straight line also. i am using visual studio 2008 with win32 (not MFC). Any ideas ? Thanks in advance, A. Gopinath.
With some algorithm you should pick 2 points that are far enough from each other. After this you can create a line object using these 2 points. The line object can be used to easily determine the distance of the other points from this line and you can accept distances less then a defined epsilon value. An O(n) algorithm to determine the 2 endpoints (assuming that the points are in a line) before your create the line object: Initialize an empty bounding AABB and then expand it by adding all points. Declare six point variables and each of them should store the last point that was used to expand the AABB in +x,-x,+y,-y,+z,-z directions (note: the first point should fill all the six variables). When this is done choose a dimension in which the size of the AABB is the biggest (x, y, or z). If the biggest dimension is zero (or near zero) then all points are located at the same spot. Lets say its x: in this case the two endpoints (from the previously mentioned 6 point variables) are the points that were stored when the AABB was expanded last time in -x and +x directions.
-
Hello everybody, i am having n-number of points like p1(x,y), p2(x,y), p3(x,y), .... pn(x,y). All points lie on a single line.(either a curve or a straight line). i would like to find, using those points, whether that line is straight or not straight. i googled and tried some of the methods given in examples, (straight line equation, finding if collinear) but those are not working fine even for straight line also. i am using visual studio 2008 with win32 (not MFC). Any ideas ? Thanks in advance, A. Gopinath.