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

This is a discussion on Need a fast way to check if a point is within a line. within the Game Programming forums, part of the General Programming Boards category; I came up with some code to check if a point is within a line. The problem with it is ...

  1. #1
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218

    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.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.)
    Last edited by tabstop; 08-05-2008 at 10:38 AM.

  3. #3
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,452
    > as it will be called for each pixel of a rectangular area encompasing a polygon.
    So, what's the actual task at hand?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  4. #4
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    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.
    Last edited by mike_g; 08-05-2008 at 11:00 AM.

  5. #5
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,452
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  6. #6
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    That sounds good. Currently I'm checking all edges which is a bit of a mess.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help about point and line
    By audinue in forum Game Programming
    Replies: 12
    Last Post: 01-02-2009, 05:07 PM
  2. Pointer and Polymorphism help.
    By Skyy in forum C++ Programming
    Replies: 29
    Last Post: 12-18-2008, 08:17 PM
  3. Fast way to check list of 0 or 1 values?
    By DrSnuggles in forum C++ Programming
    Replies: 21
    Last Post: 08-05-2008, 08:13 AM
  4. check command line argument for numeric value
    By ephemeralz in forum C Programming
    Replies: 4
    Last Post: 03-17-2004, 04:22 PM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21