Solved

Test if point coordinates are colinear

Posted on 2008-10-17
12
2,136 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
 
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
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 
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

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
Inequality 4 58
unix example issues 18 46
Calculating Z-SCORE inside Excel. 4 50
C++ mouse_event mouse look 7 20
Introduction: The undo support, implementing a stack. Continuing from the eigth article about sudoku.   We need a mechanism to keep track of the digits entered so as to implement an undo mechanism.  This should be a ‘Last In First Out’ collec…
We are taking giant steps in technological advances in the field of wireless telephony. At just 10 years since the advent of smartphones, it is crucial to examine the benefits and disadvantages that have been report to us.
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…
This video will show you how to get GIT to work in Eclipse.   It will walk you through how to install the EGit plugin in eclipse and how to checkout an existing repository.

707 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

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now