Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Suppose in a given plain there are fixed number of lines. A point P lies on one of the line. How to find which line intersects the point P ? I am giving an exampleenter image description here

In the above graph point P is on the line CE. We can determine it visually.But my problem is how to make the computer understand it. Is there any algorithm available to make it so ?

share|improve this question
1  
Since my own computer has a pretty bad eyesight, how do you state the problem in such a way that it will understand. How do you represent lines and points ? –  babou Feb 18 at 15:21
    
How are the lines specified? If you have equations for them, just test if the point satisfies any of the equations. If you have endpoints for them, produce the equations. If you have a very large number of lines and/or points, something smarter may be appropriate. –  David Richerby Feb 18 at 16:38
    
"Suppose in a given plain...." Plane, not "plain". –  David Conrad Feb 18 at 20:25
add comment

3 Answers 3

Any finite line is described by two points. assuming we are talking 2D here, then your graph can be described as a set of points, having X and Y coordinations, and a set of edges $E$, which describe which pair of points are connected with a line. Elementary geometry tell us the function expressing the points on these lines is $Y=(X-X_0)\frac{Y_1-Y_0}{X_1-X_0}+Y_0$ ($(X_0,Y_0), (X_1,Y_1)$ denote the two point's coordinations)

To check whether a point belongs to this line, insert the point's coordinates to the equation and see if the equation holds. since the line is not infinite, we should also check if the point is between the two points defining the line. If the equation holds, it is sufficient to check if one of the point's coordinates (say $X$) is between the two point's defining the line ($X_0$ and $X_1$).

So, for any line in the graph, perform the check explained above, if the above criteria holds, the line contains P.

Checking if P is on a specific line takes constant amount of computational effort, so the running time of this procedure is $O(E)$.

share|improve this answer
    
+1 Good answer. Also note that whenever working with floating-point representations, checking whether the "equation holds" entails defining an acceptable machine error and making sure that you're using it correctly. This is more of a practical concern than a nitpick of the answer, which is spot-on. –  Patrick87 Feb 18 at 16:28
add comment

As an alternative to Ron Teller's excellent answer, there is a formula that gives the distance separating a point and a line. Using this formula may prove a more natural way to determine whether the point falls on the line if using floating-point representations.

Of course, you must then check that the X and/or Y coordinate of your point fall between the coordinates of the points defining your line segment, as Ron points out.

share|improve this answer
add comment

Using homogeneous coordinates, $P$ lies on the line $EC$ if, and only if, $P^{\mathrm{T}}(E \times C) = 0$, where $\times$ is the cross-product and ${}^{\mathrm{T}}$ denotes transpose.

share|improve this answer
    
Is it normal that this answer is not symetrical in E C and P ? –  babou Feb 18 at 15:51
1  
@babou Yes. If $E$, $C$ and $P$ are distinct and collinear then permuting the three variables in the equation makes no difference because $E$ is on the infinite line through $C$ and $P$, iff $C$ is on the infinite line through $E$ and $P$, iff $P$ is on the infinite line through $E$ and $C$. –  David Richerby Feb 18 at 16:48
    
@01zhou Your test only determines if $P$ is on the infinite line that passes through $E$ and $C$: it doesn't check that it is between $E$ and $C$, as the question seems to require. –  David Richerby Feb 18 at 16:50
    
Checking the point is is on the right segement can be done simply on one coordinate. Thinking of projective geometry is probably a good idea ... even though probably equivalent to the other solution. –  babou Feb 18 at 17:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.