Determining if a point is inside of a polygon

I didn’t write this but while i was looking for the quick answer i came across a defunct website that had this information. I had to go back a ways in the wayback machine to get this info. so i post it here for all.

 

Determining if a point lies on the interior of a polygon

Written by Paul Bourke
November 1987 


Solution 1 (2D)

The following is a simple solution to the problem often encountered in computer graphics, determining whether or not a point (x,y) lies inside or outside a 2D polygonally bounded plane. This is necessary for example in applications such as polygon filling on raster devices. hatching in drafting software, and determining the intersection of multiple polygons.

Consider a polygon made up of N vertices (xi,yi) where i ranges from 0 to N-1. The last vertex (xN,yN) is assumed to be the same as the first vertex (x0,y0), that is, the polygon is closed. To determine the status of a point (xp,yp) consider a horizontal ray emanating from (xp,yp) and to the right. If the number of times this ray intersects the line segments making up the polygon is even then the point is outside the polygon. Whereas if the number of intersections is odd then the point (xp,yp) lies inside the polygon. The following shows the ray for some sample points and should make the technique clear.

Note: for the purposes of this discussion 0 will be considered even, the test for even or odd will be based on modulus 2, that is, if the number of intersections modulus 2 is 0 then the number is even, if it is 1 then it is odd.

The only trick is what happens in the special cases when an edge or vertex of the polygon lies on the ray from (xp,yp). The possible situations are illustrated below.

The thick lines above are not considered as valid intersections, the thin lines do count as intersections. Ignoring the case of an edge lying along the ray or an edge ending on the ray ensures that the endpoints are only counted once.

Note that this algorithm also works for polygons with holes as illustrated below

The following C function returns INSIDE or OUTSIDE indicating the status of a point P with respect to a polygon with N points.

#define MIN(x,y) (x < y ? x : y)
#define MAX(x,y) (x > y ? x : y)
#define INSIDE 0
#define OUTSIDE 1

typedef struct {
   double x,y;
} Point;

int InsidePolygon(Point *polygon,int N,Point p)
{
  int counter = 0;
  int i;
  double xinters;
  Point p1,p2;

  p1 = polygon[0];
  for (i=1;i<=N;i++) {
    p2 = polygon[i % N];
    if (p.y > MIN(p1.y,p2.y)) {
      if (p.y <= MAX(p1.y,p2.y)) {
        if (p.x <= MAX(p1.x,p2.x)) {
          if (p1.y != p2.y) {
            xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;
            if (p1.x == p2.x || p.x <= xinters)
              counter++;
          }
        }
      }
    }
    p1 = p2;
  }

  if (counter % 2 == 0)
    return(OUTSIDE);
  else
    return(INSIDE);
}

The following code is by Randolph Franklin, it returns 1 for interior points and 0 for exterior points.

    int pnpoly(int npol, float *xp, float *yp, float x, float y)
    {
      int i, j, c = 0;
      for (i = 0, j = npol-1; i < npol; j = i++) {
        if ((((yp[i] <= y) && (y < yp[j])) ||
             ((yp[j] <= y) && (y < yp[i]))) &&
            (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
          c = !c;
      }
      return c;
    }

Contribution by Alexander Motrichuk: InsidePolygonWithBounds.cpp.
Quote: “For most of the algorithms above there is a pathological case if the point being queried lies exactly on a vertex. The easiest way to cope with this is to test that as a separate process and make your own decision as to whether you want to consider them inside or outside.”

Contribution written in c# by Jerry Knauss: contains.c#.

Solution 2 (2D)

Another solution forwarded by Philippe Reverdy is to compute the sum of the angles made between the test point and each pair of points making up the polygon. If this sum is 2pi then the point is an interior point, if 0 then the point is an exterior point. This also works for polygons with holes given the polygon is defined with a path made up of coincident edges into and out of the hole as is common practice in many CAD packages.

The inside/outside test might then be defined in C as

typedef struct {
   int h,v;
} Point;

int InsidePolygon(Point *polygon,int n,Point p)
{
   int i;
   double angle=0;
   Point p1,p2;

   for (i=0;i<n;i++) {
      p1.h = polygon[i].h - p.h;
      p1.v = polygon[i].v - p.v;
      p2.h = polygon[(i+1)%n].h - p.h;
      p2.v = polygon[(i+1)%n].v - p.v;
      angle += Angle2D(p1.h,p1.v,p2.h,p2.v);
   }

   if (ABS(angle) < PI)
      return(FALSE);
   else
      return(TRUE);
}

/*
   Return the angle between two vectors on a plane
   The angle is from vector 1 to vector 2, positive anticlockwise
   The result is between -pi -> pi
*/
double Angle2D(double x1, double y1, double x2, double y2)
{
   double dtheta,theta1,theta2;

   theta1 = atan2(y1,x1);
   theta2 = atan2(y2,x2);
   dtheta = theta2 - theta1;
   while (dtheta > PI)
      dtheta -= TWOPI;
   while (dtheta < -PI)
      dtheta += TWOPI;

   return(dtheta);
}

Solution 3 (2D)

There are other solutions to this problem for polygons with special attributes. If the polygon is convex then one can consider the polygon as a “path” from the first vertex. A point is on the interior of this polygons if it is always on the same side of all the line segments making up the path.

Given a line segment between P0 (x0,y0) and P1 (x1,y1), another point P (x,y) has the following relationship to the line segment.

Compute 

(y – y0) (x1 - x0) – (x – x0) (y1 - y0

if it is less than 0 then P is to the right of the line segment, if greater than 0 it is to the left, if equal to 0 then it lies on the line segment.

Solution 4 (3D)

This solution was motivated by solution 2 and correspondence with Reinier van Vliet and Remco Lam. To determine whether a point is on the interior of a convex polygon in 3D one might be tempted to first determine whether the point is on the plane, then determine it’s interior status. Both of these can be accomplished at once by computing the sum of the angles between the test point (q below) and every pair of edge points p[i]->p[i+1]. This sum will only be 2pi if both the point is on the plane of the polygon AND on the interior. The angle sum will tend to 0 the further away from the polygon point q becomes.

 

The following code snippet returns the angle sum between the test point q and all the vertex pairs. Note that the angle sum is returned in radians.

typedef struct {
   double x,y,z;
} XYZ;
#define EPSILON  0.0000001
#define MODULUS(p) (sqrt(p.x*p.x + p.y*p.y + p.z*p.z))
#define TWOPI 6.283185307179586476925287
#define RTOD 57.2957795

double CalcAngleSum(XYZ q,XYZ *p,int n)
{
   int i;
   double m1,m2;
   double anglesum=0,costheta;
   XYZ p1,p2;

   for (i=0;i<n;i++) {

      p1.x = p[i].x - q.x;
      p1.y = p[i].y - q.y;
      p1.z = p[i].z - q.z;
      p2.x = p[(i+1)%n].x - q.x;
      p2.y = p[(i+1)%n].y - q.y;
      p2.z = p[(i+1)%n].z - q.z;

      m1 = MODULUS(p1);
      m2 = MODULUS(p2);
      if (m1*m2 <= EPSILON)
         return(TWOPI); /* We are on a node, consider this inside */
      else
         costheta = (p1.x*p2.x + p1.y*p2.y + p1.z*p2.z) / (m1*m2);

      anglesum += acos(costheta);
   }
   return(anglesum);
}

Note

For most of the algorithms above there is a pathological case if the point being queries lies exactly on a vertex. The easiest way to cope with this is to test that as a separate process and make your own decision as to whether you want to consider them inside or outside.

Posted in Uncategorized | 1 Comment

Using Scrollwheel in C++ OpenGl

A few years ago i decided to make a small game engine. It works well enough but as with any project there is always more to do.

One day i decided to make a media player based off the engine. Put a few squares on the screen, some artwork and fmod, then BAM, a fully working media player.(please excuse the excessive comma usage)

If you interested I will post a link later. Anyway If your familiar with OpenGl then you know that a lot of things are not naively available. So using additional libraries is essential to making things go quickly. One of those libraries is GLUT. Glut takes care of a lot of the window management and interaction with the os(keyboard, mouse, ect).

When i first built the player it was all clickable. Which is fine for  a v1 (or v4 is what the version before the change was on) but there comes a time in  a mans life when he has to make a change. That change came into the form of using the scroll wheel. The scroll wheel has be come an integral part of everyday life and it kills me that i couldn’t use it to traverse the albums in my media player sooooooo, i added it.

The library mentioned above GLUT, does not handle the scroll wheel with the original version( made sometime in the 90′s), but the great people on the FREEGLUT team have been updating a version consistently over the years. Using the freeglut lib instead of the original glut lib allows you to take advantage of the scroll wheel. Its very easy to do.

1) Download the freegult binaries and add the reference to your project:
#include <GL\freeglut.h>
2) add the callback to your code with the handling function:
glutMouseWheelFunc(mouse_wheel);
3) Write your handling function:

void mouse_wheel(int wheel, int direction, int x, int y) {
if (wheel == 0) { //1st (usually only) mouse wheel
if (direction < 0) { //Down

} else {//UP

}
}
}

And that’s it. I had scroll wheel functionality. I replaced my regular glut.h with freeglut.h and didn’t need to do anything except add my mouse wheel callback.

Posted in Uncategorized | Tagged , , , | Leave a comment

Linq strikes again

Linq has become one of my favorite things to use. It allows you to approach the concepts of objects just as you would a sql query on a database. Linq is very flexible and i have not found an instance in when it does not work, but…….
And yes there is a big BUT, i have now found a situation where the performance suffers substantially.

The theory for me was “use linq on objects in memory and it will be even faster”, well this was not the case. I used linq on various datatables in memory and it worked but was very very slow. It seems the more i added to the where clause of the linq statement the slower it got. Since this was a program in which the performance hit was very very noticeable i had to remove all instances of linq. Since i was using a data table i went back to the dataview and the rowfilter.

The row filters performance was far superior to the linq statement.

The moral of the story is check the things you change first before you alter your code around the problem instead of getting rid of it completely. For my AI crowd its sort of like a conflict set!

Posted in Uncategorized | Tagged , , , , , , , | Leave a comment

Blurb of the day

ADO.net

If you using ado.net and are getting this error

Could not load type ‘ADODB.FieldsToInternalFieldsMarshaler’ from assembly

You need to go to your project references-> Embed Interop Types: false.

Once you do this it will fix your issue.

Posted in Uncategorized | Tagged , , , , , | Leave a comment

Wisdom of the day

When dealing with vectors (or any object) PLEASE make sure the vector (or any object) is set to something and not null/nothing before you start to process it. If you don’t you will spend a lot of time diagnosing a self inflicted issued that should have been a non issue from the beginning.

Even though this is 101, sometimes we forget the basics….

Posted in Uncategorized | 3 Comments

Blurb of the day: More .net Madness

If you are using web services and are using visual stuido 2010, when you consume that service to be used in your application make sure the machine that it is being deployed to has .net framework 3.5 sp1. If it only has .net framework 3.5 that is not good enough. You will get an error like this

an error occurred while loading attribute ‘xmlserializerformatattribute’ on method blah blah blah

This error is basically telling you to install 3.5 sp1. Then the error will go away.

This happens because in vs2010 there are a few attributes that get added to web service proxies that are only usable when 3.5 sp1 is installed.

 

Posted in Uncategorized | Tagged , , , , , , , | 1 Comment

Blurb of the day: .net framework madness

Soooooooo what do you do when the a .net framework update wont install……. Go CRAZY!!!!! or you can try everything you can until something works.

I kept getting a 1603 msi error when installing the .net framework. So i went to check the error logger. It gave me a error 25007. Error occurred while initializing fusion. Setup could not load fusion with LoadLibraryShim(). Error: 0×80131700.

Looking at this error i saw that i should be able to solve it by deleting the polices folder from the windows\winsxs folder. Of course i renamed the folder instead of deleting. Next i retried the installation of the .net framework. And i get what?… You guessed it, the same error. After hours of search i found light at the end of the tunnel. This bright fellow here,
realized that if you had the .net framework 4 installed while trying to do an update on a previous version it would fail.

And once i uninstalled the .net framework 4 using the .net cleanup tool from here, everything worked just fine.

Below are all of the useful links i found for this problems:

http://da.mned.co.uk/2012/04/error-25007-error-occurred-while-initializing-fusion-setup-could-not-load-fusion-with-loadlibraryshim-error-0×80131700/

http://social.msdn.microsoft.com/Forums/en-US/netfxbcl/thread/47c93410-2ee2-4dd1-812a-04475d50de7c/

http://blogs.msdn.com/b/astebner/archive/2008/08/28/8904493.aspx

Posted in Uncategorized | Tagged , , , | 4 Comments

Blurb of the day: Data Retrieval from Sybase using .net

If you ever need to pull data from a sybase database and you are using .net to accomplish this task, you will need download the sybase developer kit for the version in which you are attempting to use. Now i may edit this but i have now found the new versions of the developer kit to be compatible with the older versions. Once you have the developer kit downloaded you will be able to utilize the .net dll’s that accompany the package and then use your connection string to connect back to the database. The best source for connection strings is http://connectionstrings.com/

Posted in Uncategorized | Tagged , , | 1 Comment

Deciphering the Database

Data migrations for one systems to the next are always a bit tricky. The level of involvement can be minimal. The small things like already knowing where certian tables are located or even using a sproc/view that can get you the requested data in an instance make some migrations as easy as pie.

On the other ther hand if you dont have help from the other party(whatever the reason may be) this is where the process can get somewhat time consuming. If this is the case you are stuck with days (possibly weeks) of data analysis before you can even start to understand the complexity in which they have structured their db. While specifc table names that denote what a table does or the data that it holds can come in handy it can also be misleading. A good db will have a lot of comments when the structure is complex. This can help tremendously. If this is not the case then you can just start at the sprocs(stored procedures).

Starting with the sprocs will allow you to see the naming conventions they use and also the manner in which they pull data themselves. This can be a great starting poing for that reason. Once you have a somewhat small grasp on whats going on or even if they dont have any sprocs, the next place you go is into the Views.

The views will be your best friend through it all. The views will allow you to see the matter in which the data is connected. The point of a view is usually for the end user to use. In this case it will be the data they want to see in the way in which they have requested. Using the create sql for the view you should be able to back track to the actual tables that are a part of it and see how everything is linked together. Once you have those links it should be simple to start creating your own sql statements to pull the required data from the database.

You can also use the functions to see if there is anything to help you decipher the structure also.

If once you are done you have the info you were looking for then you have successfully reverse engineered the database. (It helps to some how be able to verify the data in which ou have retrieved from the database.)

Posted in Uncategorized | Tagged , , , | 9 Comments

Native Boot A VHD, from not working to working

To remedy this issue with my VM performance in my previous post.  My coworker suggested i take a look at scott hanselmans blog at the Booting from a VHD post. This was a great post and I never had any idea that this was even possible. So i converted my vmdx(or whatever the vmware hd format is) back to a vhd and then went to making the changes to the boot partation using bdedit that were suggested…..

c:\> bcdedit /copy {current} /d “myVHD”

Copy the CSLID that is displayed and then run…

c:\> bcdedit /set {CLSID} device vhd=[C:]\vhds\vhdname.vhd

c:\> bcdedit /set {CLSID} osdevice vhd=[C:]\vhds\vhdname.vhd

c:\> bcdedit /set {CLSID} detecthal on

This didnt work, but upon further looking i found this. It used the bdboot command instead.I ran this command and then it booted right up into my server 2012 vhd.

I must add that i used the disk managment tool to attach the vhd in my 32bit host first and i gave it a drive letter of p. Then i ran the bcdboot (driveletter:\windows) command and it worked.

ex.
bcdboot p:\windows

This created the boot entry and did all the setup that was needed. I restarted the computer and booted from the new entry.

Dont forget to backup your boot partition first.

Backup:
bcdedit /export c:\BACKUPBCD

Restore:
bcdedit /import c:\BACKUPBCD

Posted in Uncategorized | Tagged , , , , , , | Leave a comment