Solved

Test if point coordinates are colinear

Posted on 2008-10-17
12
2,155 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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
Webinar: MongoDB® Index Types

Join Percona’s Senior Technical Services Engineer, Adamo Tonete as he presents “MongoDB Index Types, How, When and Where Should They be Used?” on Wednesday, July 12, 2017 at 11:00 am PDT / 2:00 pm EDT (UTC-7).

 
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

Webinar: MongoDB® Index Types

Join Percona’s Senior Technical Services Engineer, Adamo Tonete as he presents “MongoDB Index Types, How, When and Where Should They be Used?” on Wednesday, July 12, 2017 at 11:00 am PDT / 2:00 pm EDT (UTC-7).

Question has a verified solution.

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

This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
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 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.
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Suggested Courses

632 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