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

**mike_g** · 08-05-2008

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.

**tabstop** · 08-05-2008

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

**Salem** · 08-05-2008

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

**mike_g** · 08-05-2008

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.

**Salem** · 08-05-2008

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.

**mike_g** · 08-05-2008

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

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

Thread Tools

Search Thread

Display

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

Similar Threads

Need help about point and line

Pointer and Polymorphism help.

Fast way to check list of 0 or 1 values?

check command line argument for numeric value

Contest Results - May 27, 2002