If a given point in the plane lies inside, outside, or on the boundary of a polygon ?

This is a discussion on If a given point in the plane lies inside, outside, or on the boundary of a polygon ? within the C Programming forums, part of the General Programming Boards category; Hello friend. I want to write a program whether a given point in the plane lies inside, outside, or on ...

  1. #1
    Registered User
    Join Date
    Aug 2009
    Posts
    12

    If a given point in the plane lies inside, outside, or on the boundary of a polygon ?

    Hello friend.

    I want to write a program whether a given point in the plane lies inside, outside, or on the boundary of a polygon. I have found this interesting website which shows 2 ways of doing that. i.e InsidePolygon() and pnpoly()
    Determining if a point lies on the interior of a polygon

    But these Algo/code don't detect if the input pt is on the boundary of a polygon?
    Can you guys help me in that part of code/algo?

    Your help is much appreciated.

    ~ Jenny

  2. #2
    Bored Programmer
    Join Date
    Jul 2009
    Location
    Tomball, TX
    Posts
    407

  3. #3
    Registered User
    Join Date
    Aug 2009
    Posts
    12
    @ Lesshardtofind, Thanks a ton for the clue

    So looking at the original problem description. I can implement it in 2 parts.
    1. Check if if three points are on the same line by checking if the determinant is 0
    2. Follow that ALGO (as per my earlier update) which tells you if point is outside or inside of Polygon...

    Sounds good to you?

  4. #4
    Bored Programmer
    Join Date
    Jul 2009
    Location
    Tomball, TX
    Posts
    407
    Sounds good ;o). This a random project or part of some collision detection algorythym?

  5. #5
    Registered User
    Join Date
    Aug 2009
    Posts
    12
    ohhh wait, I see a problem here.

    Summarize....
    So looking at the original problem description. I can implement it in below program flow :
    Step1. Check if the input point is one of the vertices of polygon.
    Step2. Check if if three points are on the same line by checking if the determinant is 0
    Step3. Follow that ALGO (as per my earlier update) which tells you if point is outside or inside of Polygon...


    I see a problem here in step2.
    lets take an simple example...

    Suppose I have an polygon, Square with vertices (10,10) (100,10) (100,100) and (10,100)
    and I want to test a point (110,10) to see if this lies inside, outside, or on the boundary of a polygon.

    In this case determinant is 0, but point is actually outside of polygon


    Then I thought to check the return values of step 2 and 3.
    If return from step 2 is TRUE (i.e determinant = 0) AND return from step 3 is TRUE (i.e INSIDE)
    then by ANDing these two return value we can decide if pt is actually inside, outside, or on the boundary of a polygon.

    But again problem here is....step3...it returns random values TRUE/FALSE (i.e INSIDE/OUTSIDE) if input point is on the boundary. So my logic of AND'ing return values fails

    Please help to resolve this.

  6. #6
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,046
    If I were you I'd just use a well-known point-in-polygon algorithm (my personal favourite is the winding algorithm) for the first part. For the second problem, determining whether a point lies on a line segment, an idea that comes to mind is as follows.

    As you may know, the cross product is a mathematical operation (only defined in three dimensions, but if you want 2D you can just use z=0) between two vectors that has several useful properties. The property that's useful here is that the length of the cross-product vector will be the same as the area in the parallelogram between the original two vectors. (Confusing? Look at a picture.)

    So if the vectors are parallel, the area will be zero. Basically, if you take a vector from your point to one endpoint on the line, and another vector from your point to the other line endpoint, and their cross-product is zero, then all three points lie in a line. You can then just use a bounding box calculation to see if the point lies on the line segment.

    BTW: here's an implementation of the winding algorithm I wrote a long time ago. It's undocumented and not very understandable at all, but I thought I'd link to it anyway. You need SDL and SDL_gfx to compile it, or you can just look at the screenshots. http://dwks.theprogrammingsite.com/m...tinpoly.tar.gz
    (Warning: when you extract the archive, all files go into the current directory.)

    Just wondering: why do you care if a point lies on the boundary of the polygon? If you use floating-point numbers then it might be very rare that a point lies in precisely the right place. If you're trying to display a polygon, for example, it's more effective to use something like Bresenham's algorithm.

    If you want reasonably "wide" boundaries for collision detection, I'd find the distance of the point from the edge (one method: find the perpendicular line, find its intersection with the original line segment; use distance from intersection to point unless intersection lies outside line segment, in which case use shortest distance from the point to each endpoint) and then treat points within a small epsilon distance from the edge as being "on the edge".
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  7. #7
    Registered User
    Join Date
    Aug 2009
    Posts
    12
    Thanks dwks !

    What does the Winding number algorithm returns for a point which is on the boundary of a polygon ? Does that output in sameway as point-in-polygon algorithm ? i.e RANDOM ..sometimes INSIDE or OUTSIDE?

  8. #8
    Registered User
    Join Date
    Aug 2009
    Posts
    12
    http://www.engr.colostate.edu/~dga/d...in_polygon.pdf
    Note that the winding number is not defined when the point X is on the polygon

  9. #9
    Bored Programmer
    Join Date
    Jul 2009
    Location
    Tomball, TX
    Posts
    407
    yea on that site I linked no one responded to the guy with his post about the matrix multplication. If you scroll down past that they discuss how to tell if a point lies on a infinite line, and from there how to tell if it lies within a segment of two points.

  10. #10
    Registered User
    Join Date
    Jul 2010
    Location
    Oklahoma
    Posts
    107
    Jenny,

    What sort of constraints are there on the polygon in question? There are several variations, but from Calculus I recall that there are a multitude of assumptions that may be made about certain (convex I think) polygons. Here's an article from the Wikipedia: Polygon - Wikipedia, the free encyclopedia. I'm going to go root around in the library for a minute...brb.

    Best Regards,

    New Ink -- Henry
    Kept the text books....
    Went interdisciplinary after college....
    Still looking for a real job since 2005....

    During the interim, I may be reached at ELance, vWorker, FreeLancer, oDesk and WyzAnt.

  11. #11
    Registered User
    Join Date
    Jul 2010
    Location
    Oklahoma
    Posts
    107
    Jenny,

    This link came off the page listed in the post a moment ago: Point in polygon - Wikipedia, the free encyclopedia. It looked like "Ray casting" was the most direct solution, but for points that lie very close to the boundary the solutions were a little shady due to computational precision.... How "neat" are these polygons? In operations research, we'd study constrain tableus (tables) that would describe polygon regions using equations for the lines and there extents as part of the polygon...but that was some advanced linear programming material leading to non-linear programming.

    I apologize about the hurried nature of the post, I was about to walk away from the article to hit the books when I saw the reference in the previous article.... I'll get to looking now.

    Best Regards,

    New Ink -- Henry
    Kept the text books....
    Went interdisciplinary after college....
    Still looking for a real job since 2005....

    During the interim, I may be reached at ELance, vWorker, FreeLancer, oDesk and WyzAnt.

  12. #12
    Registered User
    Join Date
    Jul 2010
    Location
    Oklahoma
    Posts
    107
    Jenny,

    A quick way to determine the equation for the line containing the end points of an edge is given by Larson, Ron, Edwards, Bruce

    H and Falvo, David C. Elementary Linear Algebra 4th ed. Boston: Houghton Mifflin Copyright 2000. ISBN: 0-395-96717-1,

    on page 148 as:

    Code:
    The equation of the line passing through the distinct points (x1, y1) and (x2, y2) is given by
    
           [ x  y  1 ]
        det[ x1 y1 1 ] = 0.
           [ x2 y2 1 ]
    
         | y1 1 |    | x1 1 |   | x1 y1 |
    <=> x| y2 1 | - y| x2 1 | + | x2 y2 | = 0
    
    <=> x(y1 - y2) -y(x1 - x2) + (x1*y2 - x2*y1) = 0
    
    <=> x(y1 - y2)/(x1 - x2) + (x1*y2 - x2*y1)/(x1 - x2) = y
    
    <=> y = x(y1 - y2)/(x1 - x2) + (x1*y2 - x2*y1)/(x1 - x2)
    Then, after the other tests determine the point to lie outside (not inside or on boundary) of the polygon, one could use this

    familiar equation to determine if it "on" the edge of the polygon. The tedious part would be testing which edge to test against

    the test point...that is:

    Code:
    for( i = 0; i < egdes; i++ )
    
       if( ex[i][0] == ex[i][1] && x <= ex[i][0] + epsilon && x >= ex[i][0] - epsilon )  // vertical line, x coinciding with edge
       {
          if( y >= ey[i][0] && y <= ey[i][1] )
          {
             // x, y is on edge i
          }
       }
       else if( x >= ex[i][0] && x <= ex[i][1] )  // non-vertical line
       {
          yprime = x*(ey[i][0] - ey[i][1])/(ex[i][0] - ex[i][1]) + (ex[i][0]*ey[i][1] - ex[i][1]*ey[i][0])/(ex[i][0] - ex[i][1])
    
          if( y <= yprime + epsilon && y >= yprime - epsilon)
          {
             // x, y is on edge i
          }
       }
       else
       {
          // otherwise x,y is not on edge_i
       }
    It may also be difficult to choose epsilon small enough to compensate for computational loss, but for many problems I do not

    believe this will be an issue. Is that what you were looking for? I've heard the problem before, and it always intrigues me

    when I hear/read it....

    Best Regards,

    New Ink -- Henry
    Last edited by new_ink2001; 09-16-2010 at 12:20 AM. Reason: neighborhood around vertical line
    Kept the text books....
    Went interdisciplinary after college....
    Still looking for a real job since 2005....

    During the interim, I may be reached at ELance, vWorker, FreeLancer, oDesk and WyzAnt.

  13. #13
    Registered User
    Join Date
    Jul 2010
    Location
    Oklahoma
    Posts
    107
    Jenny,

    I found a good one in the library that may also be helpful for your problem. It is an observation pointed out by Taha, Hamdy A. Operations Research: An Introduction 7th ed. New Jersey: Prentice Hall Copyright 2003. ISBN: 0-13-032374-8. On pages 289-90 he is discussing some attributes of the Simplex Method. Given the extreme points x1, x2, ... xn which are the corner points of a polygon, a point lying within, x, can be expressed as a convex combination of the extreme points using:

    Code:
    x = a1x1 + a2x2 + ... + anxn
    where
    a1 + a2 + ... + an = 1
    and
    ai >= 0, for i = 1, 2, ..., n
    Using your test point, x, you have a matrix equation:

    Code:
    x = Xe * a
    Using a procedure to invert Xe, for example Eigen values or Gausian elimination, one may find a solution for a:

    Code:
    Xe^-1 * x = a
    And determine if the elements are positive and the norm (sum of the elements) is one to show that x lies within the boundaries specified in Xe, otherwise it is outside.

    I like the predictable nature of the matrix approach, but I would enjoy hearing your ideas too.

    Best Regards,

    New Ink -- Henry
    Last edited by new_ink2001; 09-16-2010 at 01:09 PM. Reason: capitalization
    Kept the text books....
    Went interdisciplinary after college....
    Still looking for a real job since 2005....

    During the interim, I may be reached at ELance, vWorker, FreeLancer, oDesk and WyzAnt.

  14. #14
    Registered User
    Join Date
    Jul 2010
    Location
    Oklahoma
    Posts
    107
    Err...pardon me. The matrix X may not be invertible. One would have to use the a simplex method to determine the solution(s) for a that fall in the feasible region, if any they would imply that the point x lies within the region defined by X. The constraints were given, and then there are a collection of slack/surplus variables which would have to be handled. I apologize about the confusion...sometimes it escapes me that I'm not necessarily speaking to mathematicians.

    Best Regards,

    New Ink -- Henry

  15. #15
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    I use this one. It's super fast and simple.

    Point Inclusion in Polygon Test
    PNPOLY - Point Inclusion in Polygon Test - WR Franklin (WRF)

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 6
    Last Post: 06-02-2006, 02:30 AM
  2. Dikumud
    By maxorator in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2005, 06:39 AM
  3. gravity: jittery camera.
    By psychopath in forum Game Programming
    Replies: 19
    Last Post: 08-06-2005, 12:07 PM
  4. point lies in circle?
    By cozman in forum Game Programming
    Replies: 3
    Last Post: 12-20-2001, 03:39 PM
  5. more with my 1st structure program
    By sballew in forum C Programming
    Replies: 42
    Last Post: 10-22-2001, 08:03 PM

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