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

1. ## 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;
return (y3 == y1)? 1: 0;
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.

2. 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.)

3. > as it will be called for each pixel of a rectangular area encompasing a polygon.
So, what's the actual task at hand?

4. 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:
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.

5. 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.

6. That sounds good. Currently I'm checking all edges which is a bit of a mess.