# Need a fast way to check if a point is within a line.

• 08-05-2008
mike_g
Need a fast way to check if a point is within a line.
I came up with some code to check if a point is within a line. The problem with it is that it is going to be too slow as it will be called for each pixel of a rectangular area encompasing a polygon. I'm sure there must be a faster way to go about this. Anyway heres what I got:
Code:

```#include <stdio.h> int PointIsOnLine(int x1, int y1, int x2, int y2, int x3, int y3) {         if(x1 == x2 && y1 == y2) //Not a line                 return -1;         if(x1 == x2)        //No gradient                 return (y3 == y1)? 1: 0;         if(y1 == y2)        //Infinite gradient                 return (x3 == x1)? 1: 0;                         double gradient = (y2 - y1) / (x2 - x1);         //Line axis intercept         double y01 = y1 - (x1 * gradient);         double x01 = x1 - (y1 / gradient);         //Test point axis intercept         double y02 = y3 - (x3 * gradient);         double x02 = x3 - (y3 / gradient);         //If intercepts are the same then point is on line         int y0 = ((int)(y02+0.5))-((int)(y01+0.5));         int x0 = ((int)(x02+0.5))-((int)(x01+0.5));         return (y0 || x0)? 0: 1; } int PointIsWithinLine(int x1, int y1, int x2, int y2, int x3, int y3) {         int result = PointIsOnLine(x1, y1, x2, y2, x3, y3);         if(! result) return 0;         int lo_x = (x1 < x2)? x1: x2;         int hi_x = (x1 > x2)? x1: x2;         int lo_y = (y1 < y2)? y1: y2;         int hi_y = (y1 > y2)? y1: y2;         if(x3 < lo_x) return 0;         if(x3 > hi_x) return 0;         if(y3 < lo_y) return 0;         if(y3 > hi_y) return 0;         return 1; } int main() {                 int result = PointIsWithinLine(20, 60, 00, 00, 2, 6);                 if(result == 1)                 printf("Point is on line\n");         else if(result == 0)                 printf("Point is not on line\n");                else                 printf("Not a line\n");         return 0; }```
Any suggestions would be appreciated. Cheers.
• 08-05-2008
tabstop
The point (x3, y3) is on the line determined by (x1, y1) and (x2, y2) if and only if (x3-x1)*(y2-y1)==(x2-x1)*(y3-y1). (Assuming, of course, that (x1, y1) != (x2, y2).)

Edit: This comes from comparing the slope of the line from point 1 to point 3 with the slope of the line from point 1 to point 2, and cross-multiplying to get rid of fractions.

Edit edit: I also don't see how you plan on returning -1 from PointIsWithinLine for "no line".

Edit edit edit: I also don't think you need to check both x and y in your PointIsWithinLine (if x works, y has to work, I should think). Also to check whether x3 is between x1 and x2 (without knowing which of x1 and x2 is larger), you can check whether (x3-x1)*(x3-x2) < 0. (Since if x3 is between, one difference will be positive and one will be negative; if it's outside, both differences will have the same sign.)
• 08-05-2008
Salem
> as it will be called for each pixel of a rectangular area encompasing a polygon.
So, what's the actual task at hand?
• 08-05-2008
mike_g
Tabstop: Cool, that sounds a lot simpler.

Edit: yeah I might just get rid of the -1 thing.

Salem: Well I'm trying to write an algorithm to fill polygons. I was going to go with the raycasting approach shown here: http://en.wikipedia.org/wiki/Point_in_polygon Basically I just scan a rect encompassing the polygon keeping track of whether I am in or out of the polygon; writing while inside.

Edit2: in pseudo code:
Code:

```Get rectangular area to scan Go over each pixel     Go over each line on polygon         If position is within rectangular area covered diagonally by line             If point is on line                 flip in/out state         If in/out state is on then write pixel```
Cheers.

Edit 3:
Quote:

Edit edit edit: I also don't think you need to check both x and y in your PointIsWithinLine (if x works, y has to work, I should think). Also to check whether x3 is between x1 and x2 (without knowing which of x1 and x2 is larger), you can check whether (x3-x1)*(x3-x2) < 0. (Since if x3 is between, one difference will be positive and one will be negative; if it's outside, both differences will have the same sign.)
Cool, I'll do that. Also after writing out the pseudo code I realised that I'd be best off checking this first before I check if the point is on the line. But, I guess that means that I wil have to check both x and y.
• 08-05-2008
Salem
Polgon filling is usually done with a scanline fill algorithm.
http://www.ccs.neu.edu/home/fell/CSU...llProblem.html

If you have a list of left/right edges, then filling all points in between is dead easy.
• 08-05-2008
mike_g
That sounds good. Currently I'm checking all edges which is a bit of a mess.