Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Test if point coordinates are colinear

Posted on 2008-10-17
12
Medium Priority
?
2,169 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 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
Moving data to the cloud? Find out if you’re ready

Before moving to the cloud, it is important to carefully define your db needs, plan for the migration & understand prod. environment. This wp explains how to define what you need from a cloud provider, plan for the migration & what putting a cloud solution into practice entails.

 
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] Lessons on Recovering from Petya

Skyport is working hard to help customers recover from recent attacks, like the Petya worm. This work has brought to light some important lessons. New malware attacks like this can take down your entire environment. Learn from others mistakes on how to prevent Petya like worms.

Question has a verified solution.

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

Introduction: Dialogs (2) modeless dialog and a worker thread.  Handling data shared between threads.  Recursive functions. Continuing from the tenth article about sudoku.   Last article we worked with a modal dialog to help maintain informat…
In this post we will learn different types of Android Layout and some basics of an Android App.
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor 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…

704 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