Go Premium for a chance to win a PS4. Enter to Win

x
?
Solved

Test if point coordinates are colinear

Posted on 2008-10-17
12
Medium Priority
?
2,173 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 500 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 1500 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
Concerto's Cloud Advisory Services

Want to avoid the missteps to gaining all the benefits of the cloud? Learn more about the different assessment options from our Cloud Advisory team.

 
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 85

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

Important Lessons on Recovering from Petya

In their most recent webinar, Skyport Systems explores ways to isolate and protect critical databases to keep the core of your company safe from harm.

Question has a verified solution.

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

This article seeks to propel the full implementation of geothermal power plants in Mexico as a renewable energy source.
Article by: Nicole
This is a research brief on the potential colonization of humans on Mars.
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

877 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