Solved

Test if point coordinates are colinear

Posted on 2008-10-17
12
2,141 Views
Last Modified: 2013-11-20
How would I test if a series of coordinates are colinear i.e. on the same line, I do not have line segments to work with, because there is no class for it..
0
Comment
Question by:steenpat
  • 3
  • 3
  • 2
  • +3
12 Comments
 
LVL 86

Expert Comment

by:jkr
ID: 22742740
Calculate the linear equation y = mx + b (http://en.wikipedia.org/wiki/Linear_equation) for two pairs of points and check whether m and b are equivalent. If so, they are colinear. I.e.

m = (y2 - y1) / (x2 - x1);
b = y1 - m * x1;
0
 
LVL 22

Assisted Solution

by:NovaDenizen
NovaDenizen earned 125 total points
ID: 22742771
Assuming you're working with floating point numbers, you have to keep in mind that you can't calculate this exactly.  You have to decide on an error range, or at least work with a measure of how collinear the points are.
0
 
LVL 18

Accepted Solution

by:
WaterStreet earned 375 total points
ID: 22743029
Pick one point and make sure that the slope (m) of all lines between that point and all the points is the same (using the coordinates for each point).  
Then if the slopes are the same for all, the points are colinear
0
Courses: Start Training Online With Pros, Today

Brush up on the basics or master the advanced techniques required to earn essential industry certifications, with Courses. Enroll in a course and start learning today. Training topics range from Android App Dev to the Xen Virtualization Platform.

 
LVL 1

Expert Comment

by:siddhant3s
ID: 22743172
Oh man, what I can guess is this,
There is a simple formula that calculates the area of a triangle(or any polygon) with coordinate of the points given set of points given.
The given points will be collinear if the area comes out to be zero.

Now I am giving the formula for the area of triangle, which will be zero when all the three points are collinear:
Area=(1/2)*(x1*y2 - x2*y1+ x2*y3 - x3*y2 + x3*y1 - x1*y3)
where x1,y1 are the coordinate of first point; x2,y2 are the coordinate of second point and so on.
So, if the area is zero we have
x1* y2 + x2* y3 + x3* y1 = x2* y1+ x3* y2 +x1* y3
 
So what you should do is take the first three points and check for colinearity, then the next three and so on.
Enjoy,


0
 
LVL 22

Expert Comment

by:NovaDenizen
ID: 22743920
@WaterStreet:
Using slopes instead of 2-d linear algebra is almost always a bad idea.  You have to set up special cases for when the lines are vertical.  It's worth the effort to do it the proper way.
0
 
LVL 86

Expert Comment

by:jkr
ID: 22744563
Um a maybe simpler approach from vector algebra: Calculate the normalized spatial vectors between two points and compare these (within reasonable limits) - i.e.


xn = (x2 - x1) / sqrt(pow(x2,2.0) + pow(x1,2.0));
yn = (y2 - y1) / sqrt(pow(y2,2.0) + pow(y1,2.0));

Open in new window

0
 
LVL 86

Expert Comment

by:jkr
ID: 22744812
Huh?
0
 
LVL 18

Expert Comment

by:WaterStreet
ID: 22745440
Nova,
I see what you mean.  Good to mention that.  Thanks.
0
 
LVL 84

Expert Comment

by:ozo
ID: 22745474
the area method should be the simplest.
If you set a threshold to also accept points that are almost colinear,
you may want to scale the threshhold by the distance between the points, since it gets harder to have a small area with widely separated points.
The other methods also become more difficult to meet a threshold when the points are far apart (and in the ones that check slope, when the slope becomes large) so they would also need be scaled if you wanted to be equally fair to almost collinear points at any size/angle
0
 
LVL 1

Expert Comment

by:siddhant3s
ID: 22747423
ozo, I think they have selected their choice, and they wont listen too.
Tell them what about these three points : (2,3)   (2,2)  ,  (2,10)
You cant tell if these points are collinear using the slope method.
Slope of the lines joining these points are not defined
0
 

Author Comment

by:steenpat
ID: 22757628
siddhant3s you are right,
but i set up a special case for that like nova said.
0
 
LVL 1

Expert Comment

by:siddhant3s
ID: 22758987
go ahead for that speacial case, i cant stop you.
but there is one more glitch.
your method requires division of float point numbers which are less efficient.
Also, by the slope method you will never be accurate if the points are far apart.

By the way enjoy.
PS: Good programing lies in efficient algorithms.

0

Featured Post

Gigs: Get Your Project Delivered by an Expert

Select from freelancers specializing in everything from database administration to programming, who have proven themselves as experts in their field. Hire the best, collaborate easily, pay securely and get projects done right.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

If you use Adobe Reader X it is possible you can't open OLE PDF documents in the standard. The reason is the 'save box mode' in adobe reader X. Many people think the protected Mode of adobe reader x is only to stop the write access. But this fe…
Lithium-ion batteries area cornerstone of today's portable electronic devices, and even though they are relied upon heavily, their chemistry and origin are not of common knowledge. This article is about a device on which every smartphone, laptop, an…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

785 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question