How can I determine whether a 2D Point is within a Polygon

Question

I m trying to create a fast 2D point inside polygon algorithm  for use in hit-testing  e g  Polygon contains p Point    Suggestions for effective techniques would be appreciated

User · Answer

Net port       static void Main string   args                 Console Write  Hola            List lt double gt  vertx   new List lt double gt             List lt double gt  verty   new List lt double gt              int i  j  c   0           vertx Add 1           vertx Add 2           vertx Add 1           vertx Add 4           vertx Add 4           vertx Add 1            verty Add 1           verty Add 2           verty Add 4           verty Add 4           verty Add 1           verty Add 1            int nvert   6     V  rtices del poligono          double testx   2          double testy   5            for  i   0  j   nvert - 1  i  lt  nvert  j   i                          if    verty i   gt  testy      verty j   gt  testy    amp  amp                testx  lt   vertx j  - vertx i      testy - verty i      verty j  - verty i     vertx i                    c   1

User · Answer

I did some work on this back when I was a researcher under Michael Stonebraker - you know  the professor who came up with Ingres  PostgreSQL  etc   We realized that the fastest way was to first do a bounding box because it s SUPER fast  If it s outside the bounding box  it s outside  Otherwise  you do the harder work     If you want a great algorithm  look to the open source project PostgreSQL source code for the geo work     I want to point out  we never got any insight into right vs left handedness  also expressible as an  inside  vs  outside  problem       UPDATE  BKB s link provided a good number of reasonable algorithms  I was working on Earth Science problems and therefore needed a solution that works in latitude longitude  and it has the peculiar problem of handedness - is the area inside the smaller area or the bigger area  The answer is that the  direction  of the verticies matters - it s either left-handed or right handed and in this way you can indicate either area as  inside  any given polygon  As such  my work used solution three enumerated on that page    In addition  my work used separate functions for  on the line  tests      Since someone asked  we figured out that bounding box tests were best when the number of verticies went beyond some number - do a very quick test before doing the longer test if necessary    A bounding box is created by simply taking the largest x  smallest x  largest y and smallest y and putting them together to make four points of a box     Another tip for those that follow  we did all our more sophisticated and  light-dimming  computing in a grid space all in positive points on a plane and then re-projected back into  real  longitude latitude  thus avoiding possible errors of wrapping around when one crossed line 180 of longitude and when handling polar regions  Worked great

User · Answer

VBA VERSION   Note  Remember that if your polygon is an area within a map that Latitude Longitude are Y X values as opposed to X Y  Latitude   Y  Longitude   X  due to from what I understand are historical implications from way back when Longitude was not a measurement   CLASS MODULE  CPoint  Private pXValue As Double Private pYValue As Double       X Value Property       Public Property Get X   As Double     X   pXValue End Property  Public Property Let X Value As Double      pXValue   Value End Property       Y Value Property       Public Property Get Y   As Double     Y   pYValue End Property  Public Property Let Y Value As Double      pYValue   Value End Property   MODULE   Public Function isPointInPolygon p As CPoint  polygon   As CPoint  As Boolean      Dim i As Integer     Dim j As Integer     Dim q As Object     Dim minX As Double     Dim maxX As Double     Dim minY As Double     Dim maxY As Double     minX   polygon 0  X     maxX   polygon 0  X     minY   polygon 0  Y     maxY   polygon 0  Y      For i   1 To UBound polygon          Set q   polygon i          minX   vbMin q X  minX          maxX   vbMax q X  maxX          minY   vbMin q Y  minY          maxY   vbMax q Y  maxY      Next i      If p X  lt  minX Or p X  gt  maxX Or p Y  lt  minY Or p Y  gt  maxY Then         isPointInPolygon   False         Exit Function     End If         SOURCE  http   www ecse rpi edu Homepages wrf Research Short Notes pnpoly html      isPointInPolygon   False     i   0     j   UBound polygon       Do While i  lt  UBound polygon    1         If  polygon i  Y  gt  p Y  Then             If  polygon j  Y  lt  p Y  Then                 If p X  lt   polygon j  X - polygon i  X     p Y - polygon i  Y     polygon j  Y - polygon i  Y    polygon i  X Then                     isPointInPolygon   True                     Exit Function                 End If             End If         ElseIf  polygon i  Y  lt  p Y  Then             If  polygon j  Y  gt  p Y  Then                 If p X  lt   polygon j  X - polygon i  X     p Y - polygon i  Y     polygon j  Y - polygon i  Y    polygon i  X Then                     isPointInPolygon   True                     Exit Function                 End If             End If         End If         j   i         i   i   1     Loop    End Function  Function vbMax n1  n2  As Double     vbMax   IIf n1  gt  n2  n1  n2  End Function  Function vbMin n1  n2  As Double     vbMin   IIf n1  gt  n2  n2  n1  End Function   Sub TestPointInPolygon        Dim i As Integer     Dim InPolygon As Boolean      MARKER Object     Dim p As CPoint     Set p   New CPoint     p X    lt ENTER X VALUE HERE gt      p Y    lt ENTER Y VALUE HERE gt       POLYGON OBJECT     Dim polygon   As CPoint     ReDim polygon  lt ENTER VALUE HERE gt    Amount of vertices in polygon - 1     For i   0 To  lt ENTER VALUE HERE gt   Same value as above        Set polygon i    New CPoint        polygon i  X    lt ASSIGN X VALUE HERE gt   Source a list of values that can be looped through        polgyon i  Y    lt ASSIGN Y VALUE HERE gt   Source a list of values that can be looped through     Next i      InPolygon   isPointInPolygon p  polygon      MsgBox InPolygon  End Sub

User · Answer

Scala version of solution by nirg  assumes bounding rectangle pre-check is done separately    def inside p  Point  polygon  Array Point   bounds  Bounds   Boolean        val length   polygon length     tailrec   def oddIntersections i  Int  j  Int  tracker  Boolean   Boolean         if  i    length        tracker     else         val intersects    polygon i  y  gt  p y      polygon j  y  gt  p y   amp  amp  p x  lt   polygon j  x - polygon i  x     p y - polygon i  y     polygon j  y - polygon i  y    polygon i  x       oddIntersections i   1  i  if  intersects   tracker else tracker               oddIntersections 0  length - 1  tracker   false

User · Answer

This only works for convex shapes  but Minkowski Portal Refinement  and GJK are also great options for testing if a point is in a polygon   You  use minkowski subtraction to subtract the point from the polygon  then run those algorithms to see if the polygon contains the origin   Also  interestingly  you can describe your shapes a bit more implicitly using support functions which take a direction vector as input and spit out the farthest point along that vector   This allows you to describe any convex shape   curved  made out of polygons  or mixed   You can also do operations to combine the results of simple support functions to make more complex shapes   More info  http   xenocollide snethen com mpr2d html  Also  game programming gems 7 talks about how to do this in 3d

User · Answer

David Segond s answer is pretty much the standard general answer  and Richard T s is the most common optimization  though therre are some others   Other strong optimizations are based on less general solutions   For example if you are going to check the same polygon with lots of points  triangulating the polygon can speed things up hugely as there are a number of very fast TIN searching algorithms   Another is if the polygon and points are on a limited plane at low resolution  say a screen display  you can paint the polygon onto a memory mapped display buffer in a given colour  and check the color of a given pixel to see if it lies in the polygons   Like many optimizations  these are based on specific rather than general cases  and yield beneifits based on amortized time rather than single usage   Working in this field  i found Joeseph O Rourkes  Computation Geometry in C  ISBN 0-521-44034-3 to be a great help

User · Answer

For Detecting hit on Polygon we need to test two things    If Point is inside polygon area   can be accomplished by Ray-Casting Algorithm  If Point is on the polygon border can be accomplished by same algorithm which is used for point detection on polyline line

User · Answer

For graphics  I d rather not prefer integers  Many systems use integers for UI painting  pixels are ints after all   but macOS for example uses float for everything  macOS only knows points and a point can translate to one pixel  but depending on monitor resolution  it might translate to something else  On retina screens half a point  0 5 0 5  is pixel  Still  I never noticed that macOS UIs are significantly slower than other UIs  After all 3D APIs  OpenGL or Direct3D  also works with floats and modern graphics libraries very often take advantage of GPU acceleration   Now you said speed is your main concern  okay  let s go for speed  Before you run any sophisticated algorithm  first do a simple test  Create an axis aligned bounding box around your polygon  This is very easy  fast and can already safe you a lot of calculations   How does that work  Iterate over all points of the polygon and find the min max values of X and Y    E g  you have the points  9 1    4 3    2 7    8 2    3 6   This means Xmin is 2  Xmax is 9  Ymin is 1 and Ymax is 7  A point outside of the rectangle with the two edges  2 1  and  9 7  cannot be within the polygon      p is your point  p x is the x coord  p y is the y coord if  p x  lt  Xmin    p x  gt  Xmax    p y  lt  Ymin    p y  gt  Ymax           Definitely not within the polygon      This is the first test to run for any point  As you can see  this test is ultra fast but it s also very coarse  To handle points that are within the bounding rectangle  we need a more sophisticated algorithm  There are a couple of ways how this can be calculated  Which method works also depends on the fact if the polygon can have holes or will always be solid  Here are examples of solid ones  one convex  one concave      And here s one with a hole     The green one has a hole in the middle   The easiest algorithm  that can handle all three cases above and is still pretty fast is named ray casting  The idea of the algorithm is pretty simple  Draw a virtual ray from anywhere outside the polygon to your point and count how often it hits a side of the polygon  If the number of hits is even  it s outside of the polygon  if it s odd  it s inside     The winding number algorithm would be an alternative  it is more accurate for points being very close to a polygon line but it s also much slower  Ray casting may fail for points too close to a polygon side because of limited floating point precision and rounding issues  but in reality that is hardly a problem  as if a point lies that close to a side  it s often visually not even possible for a viewer to recognize if it is already inside or still outside   You still have the bounding box of above  remember  Just pick a point outside the bounding box and use it as starting point for your ray  E g  the point  Xmin - e p y  is outside the polygon for sure    But what is e  Well  e  actually epsilon  gives the bounding box some padding  As I said  ray tracing fails if we start too close to a polygon line  Since the bounding box might equal the polygon  if the polygon is an axis aligned rectangle  the bounding box is equal to the polygon itself    we need some padding to make this safe  that s all  How big should you choose e  Not too big  It depends on the coordinate system scale you use for drawing  If your pixel step width is 1 0  then just choose 1 0  yet 0 1 would have worked as well   Now that we have the ray with its start and end coordinates  the problem shifts from  is the point within the polygon  to  how often does the ray intersects a polygon side   Therefore we can t just work with the polygon points as before  now we need the actual sides  A side is always defined by two points   side 1   X1 Y1 - X2 Y2  side 2   X2 Y2 - X3 Y3  side 3   X3 Y3 - X4 Y4      You need to test the ray against all sides  Consider the ray to be a vector and every side to be a vector  The ray has to hit each side exactly once or never at all  It can t hit the same side twice  Two lines in 2D space will always intersect exactly once  unless they are parallel  in which case they never intersect  However since vectors have a limited length  two vectors might not be parallel and still never intersect because they are too short to ever meet each other      Test the ray against all sides int intersections   0  for  side   0  side  lt  numberOfSides  side             Test if current side intersects with ray         If yes  intersections      if   intersections  amp  1     1           Inside of polygon   else          Outside of polygon     So far so well  but how do you test if two vectors intersect  Here s some C code  not tested   that should do the trick    define NO 0  define YES 1  define COLLINEAR 2  int areIntersecting      float v1x1  float v1y1  float v1x2  float v1y2      float v2x1  float v2y1  float v2x2  float v2y2         float d1  d2      float a1  a2  b1  b2  c1  c2          Convert vector 1 to a line  line 1  of infinite length         We want the line in linear equation standard form  A x   B y   C   0        See  http   en wikipedia org wiki Linear equation     a1   v1y2 - v1y1      b1   v1x1 - v1x2      c1    v1x2   v1y1  -  v1x1   v1y2           Every point  x y   that solves the equation above  is on the line         every point that does not solve it  is not  The equation will have a        positive result if it is on one side of the line and a negative one         if is on the other side of it  We insert  x1 y1  and  x2 y2  of vector        2 into the equation above      d1    a1   v2x1     b1   v2y1    c1      d2    a1   v2x2     b1   v2y2    c1          If d1 and d2 both have the same sign  they are both on the same side        of our line 1 and in that case no intersection is possible  Careful          0 is a special case  that s why we don t test   gt    and   lt             but   lt   and   gt        if  d1  gt  0  amp  amp  d2  gt  0  return NO      if  d1  lt  0  amp  amp  d2  lt  0  return NO          The fact that vector 2 intersected the infinite line 1 above doesn t         mean it also intersects the vector 1  Vector 1 is only a subset of that        infinite line 1  so it may have intersected that line before the vector        started or after it ended  To know for sure  we have to repeat the        the same test the other way round  We start by calculating the         infinite line 2 in linear equation standard form      a2   v2y2 - v2y1      b2   v2x1 - v2x2      c2    v2x2   v2y1  -  v2x1   v2y2           Calculate d1 and d2 again  this time using points of vector 1      d1    a2   v1x1     b2   v1y1    c2      d2    a2   v1x2     b2   v1y2    c2          Again  if both have the same sign  and neither one is 0          no intersection is possible      if  d1  gt  0  amp  amp  d2  gt  0  return NO      if  d1  lt  0  amp  amp  d2  lt  0  return NO          If we get here  only two possibilities are left  Either the two        vectors intersect in exactly one point or they are collinear  which        means they intersect in any number of points from zero to infinite      if   a1   b2  -  a2   b1     0 0f  return COLLINEAR          If they are not collinear  they must intersect in exactly one point      return YES      The input values are the two endpoints of vector 1  v1x1 v1y1 and v1x2 v1y2  and vector 2  v2x1 v2y1 and v2x2 v2y2   So you have 2 vectors  4 points  8 coordinates  YES and NO are clear  YES increases intersections  NO does nothing    What about COLLINEAR  It means both vectors lie on the same infinite line  depending on position and length  they don t intersect at all or they intersect in an endless number of points  I m not absolutely sure how to handle this case  I would not count it as intersection either way  Well  this case is rather rare in practice anyway because of floating point rounding errors  better code would probably not test for    0 0f but instead for something like  lt  epsilon  where epsilon is a rather small number   If you need to test a larger number of points  you can certainly speed up the whole thing a bit by keeping the linear equation standard forms of the polygon sides in memory  so you don t have to recalculate these every time  This will save you two floating point multiplications and three floating point subtractions on every test in exchange for storing three floating point values per polygon side in memory  It s a typical memory vs computation time trade off   Last but not least  If you may use 3D hardware to solve the problem  there is an interesting alternative  Just let the GPU do all the work for you  Create a painting surface that is off screen  Fill it completely with the color black  Now let OpenGL or Direct3D paint your polygon  or even all of your polygons if you just want to test if the point is within any of them  but you don t care for which one  and fill the polygon s  with a different color  e g  white  To check if a point is within the polygon  get the color of this point from the drawing surface  This is just a O 1  memory fetch   Of course this method is only usable if your drawing surface doesn t have to be huge  If it cannot fit into the GPU memory  this method is slower than doing it on the CPU  If it would have to be huge and your GPU supports modern shaders  you can still use the GPU by implementing the ray casting shown above as a GPU shader  which absolutely is possible  For a larger number of polygons or a large number of points to test  this will pay off  consider some GPUs will be able to test 64 to 256 points in parallel  Note however that transferring data from CPU to GPU and back is always expensive  so for just testing a couple of points against a couple of simple polygons  where either the points or the polygons are dynamic and will change frequently  a GPU approach will rarely pay off

User · Answer

Swift version of the answer by nirg   extension CGPoint       func isInsidePolygon vertices   CGPoint   - gt  Bool           guard  vertices isEmpty else   return false           var j   vertices last   c   false         for i in vertices               let a    i y  gt  y      j y  gt  y              let b    x  lt   j x - i x     y - i y     j y - i y    i x              if a  amp  amp  b   c    c               j   i                   return c

User · Answer

This question is so interesting  I have another workable idea different from other answers to this post  The idea is to use the sum of angles to decide whether the target is inside or outside  Better known as winding number    Let x be the target point  Let array  0  1       n  be the all the points of the area  Connect the target point with every border point with a line  If the target point is inside of this area  The sum of all angles will be 360 degrees  If not the angles will be less than 360   Refer to this image to get a basic understanding of the idea    My algorithm assumes the clockwise is the positive direction  Here is a potential input     -122 402015  48 225216    -117 032049  48 999931    -116 919132  45 995175    -124 079107  46 267259    -124 717175  48 377557    -122 92315  47 047963    -122 402015  48 225216     The following is the python code that implements the idea   def isInside self  border  target   degree   0 for i in range len border  - 1       a   border i      b   border i   1         calculate distance of vector     A   getDistance a 0   a 1   b 0   b 1        B   getDistance target 0   target 1   a 0   a 1       C   getDistance target 0   target 1   b 0   b 1          calculate direction of vector     ta x   a 0  - target 0      ta y   a 1  - target 1      tb x   b 0  - target 0      tb y   b 1  - target 1       cross   tb y   ta x - tb x   ta y     clockwise   cross  lt  0        calculate sum of angles     if clockwise           degree   degree   math degrees math acos  B   B   C   C - A   A     2 0   B   C        else          degree   degree - math degrees math acos  B   B   C   C - A   A     2 0   B   C     if abs round degree  - 360   lt   3       return True return False

User · Answer

This is a presumably slightly less optimized version of the C code from here which was sourced from this page   My C   version uses a std  vector lt std  pair lt double  double gt  gt  and two doubles as an x and y  The logic should be exactly the same as the original C code  but I find mine easier to read  I can t speak for the performance   bool point in poly std  vector lt std  pair lt double  double gt  gt  amp  verts  double point x  double point y        bool in poly   false      auto num verts   verts size        for  int i   0  j   num verts - 1  i  lt  num verts  j   i              double x1   verts i  first          double y1   verts i  second          double x2   verts j  first          double y2   verts j  second           if    y1  gt  point y      y2  gt  point y    amp  amp               point x  lt   x2 - x1     point y - y1     y2 - y1    x1               in poly    in poly            return in poly      The original C code is  int pnpoly int nvert  float  vertx  float  verty  float testx  float testy      int i  j  c   0    for  i   0  j   nvert-1  i  lt  nvert  j   i          if     verty i  gt testy      verty j  gt testy    amp  amp        testx  lt   vertx j -vertx i      testy-verty i      verty j -verty i     vertx i            c    c        return c

User · Answer

David Segond s answer is pretty much the standard general answer  and Richard T s is the most common optimization  though therre are some others   Other strong optimizations are based on less general solutions   For example if you are going to check the same polygon with lots of points  triangulating the polygon can speed things up hugely as there are a number of very fast TIN searching algorithms   Another is if the polygon and points are on a limited plane at low resolution  say a screen display  you can paint the polygon onto a memory mapped display buffer in a given colour  and check the color of a given pixel to see if it lies in the polygons   Like many optimizations  these are based on specific rather than general cases  and yield beneifits based on amortized time rather than single usage   Working in this field  i found Joeseph O Rourkes  Computation Geometry in C  ISBN 0-521-44034-3 to be a great help

User · Answer

The answer depends on if you have the simple or complex polygons  Simple polygons must not have any line segment intersections  So they can have the holes but lines can t cross each other  Complex regions can have the line intersections - so they can have the overlapping regions  or regions that touch each other just by a single point   For simple polygons the best algorithm is Ray casting  Crossing number  algorithm  For complex polygons  this algorithm doesn t detect points that are inside the overlapping regions  So for complex polygons you have to use Winding number algorithm   Here is an excellent article with C implementation of both algorithms  I tried them and they work well   http   geomalgorithms com a03- inclusion html

User · Answer

This question is so interesting  I have another workable idea different from other answers to this post  The idea is to use the sum of angles to decide whether the target is inside or outside  Better known as winding number    Let x be the target point  Let array  0  1       n  be the all the points of the area  Connect the target point with every border point with a line  If the target point is inside of this area  The sum of all angles will be 360 degrees  If not the angles will be less than 360   Refer to this image to get a basic understanding of the idea    My algorithm assumes the clockwise is the positive direction  Here is a potential input     -122 402015  48 225216    -117 032049  48 999931    -116 919132  45 995175    -124 079107  46 267259    -124 717175  48 377557    -122 92315  47 047963    -122 402015  48 225216     The following is the python code that implements the idea   def isInside self  border  target   degree   0 for i in range len border  - 1       a   border i      b   border i   1         calculate distance of vector     A   getDistance a 0   a 1   b 0   b 1        B   getDistance target 0   target 1   a 0   a 1       C   getDistance target 0   target 1   b 0   b 1          calculate direction of vector     ta x   a 0  - target 0      ta y   a 1  - target 1      tb x   b 0  - target 0      tb y   b 1  - target 1       cross   tb y   ta x - tb x   ta y     clockwise   cross  lt  0        calculate sum of angles     if clockwise           degree   degree   math degrees math acos  B   B   C   C - A   A     2 0   B   C        else          degree   degree - math degrees math acos  B   B   C   C - A   A     2 0   B   C     if abs round degree  - 360   lt   3       return True return False

User · Answer

To deal with the following special cases in Ray casting algorithm    The ray overlaps one of the polygon s side  The point is inside of the polygon and the ray passes through a vertex of the polygon  The point is outside of the polygon and the ray just touches one of the polygon s angle    Check Determining Whether A Point Is Inside A Complex Polygon  The article provides an easy way to resolve them so there will be no special treatment required for the above cases

User · Answer

Java Version   public class Geocode       private float latitude      private float longitude       public Geocode                public Geocode float latitude  float longitude            this latitude   latitude          this longitude   longitude             public float getLatitude             return latitude             public void setLatitude float latitude            this latitude   latitude             public float getLongitude             return longitude             public void setLongitude float longitude            this longitude   longitude           public class GeoPolygon       private ArrayList lt Geocode gt  points       public GeoPolygon             this points   new ArrayList lt Geocode gt                public GeoPolygon ArrayList lt Geocode gt  points            this points   points             public GeoPolygon add Geocode geo            points add geo           return this             public boolean inside Geocode geo            int i  j          boolean c   false          for  i   0  j   points size   - 1  i  lt  points size    j   i                  if    points get i  getLongitude    gt  geo getLongitude        points get j  getLongitude    gt  geo getLongitude      amp  amp                       geo getLatitude    lt   points get j  getLatitude   - points get i  getLatitude       geo getLongitude   - points get i  getLongitude       points get j  getLongitude   - points get i  getLongitude      points get i  getLatitude                     c    c                    return c

User · Answer

Compute the oriented sum of angles between the point p and each of the polygon apices  If the total oriented angle is 360 degrees  the point is inside  If the total is 0  the point is outside   I like this method better because it is more robust and less dependent on numerical precision   Methods that compute evenness of number of intersections are limited because you can  hit  an apex during the computation of the number of intersections   EDIT  By The Way  this method works with concave and convex polygons   EDIT  I recently found a whole Wikipedia article on the topic

User · Answer

Really like the solution posted by Nirg and edited by bobobobo  I just made it javascript friendly and a little more legible for my use   function insidePoly poly  pointx  pointy        var i  j      var inside   false      for  i   0  j   poly length - 1  i  lt  poly length  j   i              if   poly i  y  gt  pointy      poly j  y  gt  pointy    amp  amp   pointx  lt   poly j  x-poly i  x     pointy-poly i  y     poly j  y-poly i  y    poly i  x    inside    inside            return inside

User · Answer

The trivial solution would be to divide the polygon to triangles and hit test the triangles as explained here    If your polygon is CONVEX there might be a better approach though  Look at the polygon as a collection of infinite lines  Each line dividing space into two  for every point it s easy to say if its on the one side or the other side of the line  If a point is on the same side of all lines then it is inside the polygon

User · Answer

If you re using Google Map SDK and want to check if a point is inside a polygon  you can try to use GMSGeometryContainsLocation  It works great   Here is how that works   if GMSGeometryContainsLocation point  polygon  true        print  Inside this polygon      else       print  outside this polygon       Here is the reference  https   developers google com maps documentation ios-sdk reference group   geometry utils gaba958d3776d49213404af249419d0ffd

User · Answer

This seems to work in R  apologies for ugliness  would like to see better version     pnpoly  lt - function nvert vertx verty testx testy             c  lt - FALSE           j  lt - nvert            for  i in 1 nvert                 if    verty i  gt testy      verty j  gt testy    amp  amp       testx  lt   vertx j -vertx i    testy-verty i    verty j -verty i   vertx i                 c  lt -  c               j  lt - i     return c

User · Answer

You can do this by  checking if the area formed by  connecting the desired point to the vertices of your polygon matches the area of the polygon itself    Or you could check if the sum of the inner angles from your point to each pair of two consecutive  polygon vertices to your check point sums to 360  but I have the feeling that the first option is quicker because it doesn t involve divisions nor calculations of inverse of trigonometric functions   I don t know what happens if your polygon has a hole inside it but it seems to me that the main idea can be adapted to this situation   You can as well post the question in a math community  I bet they have one million ways of doing that

User · Answer

Net port       static void Main string   args                 Console Write  Hola            List lt double gt  vertx   new List lt double gt             List lt double gt  verty   new List lt double gt              int i  j  c   0           vertx Add 1           vertx Add 2           vertx Add 1           vertx Add 4           vertx Add 4           vertx Add 1            verty Add 1           verty Add 2           verty Add 4           verty Add 4           verty Add 1           verty Add 1            int nvert   6     V  rtices del poligono          double testx   2          double testy   5            for  i   0  j   nvert - 1  i  lt  nvert  j   i                          if    verty i   gt  testy      verty j   gt  testy    amp  amp                testx  lt   vertx j  - vertx i      testy - verty i      verty j  - verty i     vertx i                    c   1

User · Answer

Heres a point in polygon test in C that isn t using ray-casting  And it can work for overlapping areas  self intersections   see the use holes argument      math lib  defined below     static float dot v2v2 const float a 2   const float b 2    static float angle signed v2v2 const float v1 2   const float v2 2    static void copy v2 v2 float r 2   const float a 2        intersection function    bool isect point poly v2 const float pt 2   const float verts   2   const unsigned int nr                           const bool use holes           we do the angle rule  define that all added angles should be about zero or  2   PI         float angletot   0 0      float fp1 2   fp2 2       unsigned int i      const float  p1   p2       p1   verts nr - 1           first vector        fp1 0    p1 0  - pt 0       fp1 1    p1 1  - pt 1        for  i   0  i  lt  nr  i              p2   verts i               second vector            fp2 0    p2 0  - pt 0           fp2 1    p2 1  - pt 1               dot and angle and cross            angletot    angle signed v2v2 fp1  fp2               circulate            copy v2 v2 fp1  fp2           p1   p2             angletot   fabsf angletot       if  use holes            const float nested   floorf  angletot    float  M PI   2 0     0 00001f           angletot -  nested    float  M PI   2 0           return  angletot  gt  4 0f       int nested   2             else           return  angletot  gt  4 0f               math lib     static float dot v2v2 const float a 2   const float b 2         return a 0    b 0    a 1    b 1      static float angle signed v2v2 const float v1 2   const float v2 2         const float perp dot    v1 1    v2 0   -  v1 0    v2 1        return atan2f perp dot  dot v2v2 v1  v2       static void copy v2 v2 float r 2   const float a 2         r 0    a 0       r 1    a 1       Note  this is one of the less optimal methods since it includes a lot of calls to atan2f  but it may be of interest to developers reading this thread  in my tests its  23x slower then using the line intersection method

User · Answer

Surprised nobody brought this up earlier  but for the pragmatists requiring a database  MongoDB has excellent support for Geo queries including this one   What you are looking for is      db neighborhoods findOne   geometry     geoIntersects     geometry      type   Point   coordinates     longitude    latitude                 Neighborhoods is the collection that stores one or more polygons in standard GeoJson format  If the query returns null it is not intersected otherwise it is   Very well documented here  https   docs mongodb com manual tutorial geospatial-tutorial   The performance for more than 6 000 points classified in a 330 irregular polygon grid was less than one minute with no optimization at all and including the time to update documents with their respective polygon

User · Answer

When using qt  Qt 4 3    one can use QPolygon s function containsPoint

User · Answer

When using qt  Qt 4 3    one can use QPolygon s function containsPoint

User · Answer

Obj-C version of nirg s answer with sample method for testing points  Nirg s answer worked well for me   -  BOOL isPointInPolygon  NSArray   vertices point  CGPoint test       NSUInteger nvert    vertices count       NSInteger i  j  c   0      CGPoint verti  vertj       for  i   0  j   nvert-1  i  lt  nvert  j   i              verti     NSValue    vertices objectAtIndex i  CGPointValue           vertj     NSValue    vertices objectAtIndex j  CGPointValue           if     verti y  gt  test y      vertj y  gt  test y     amp  amp            test x  lt    vertj x - verti x       test y - verti y       vertj y - verti y     verti x                c    c             return  c   YES   NO      -  void testPoint        NSArray  polygonVertices    NSArray arrayWithObjects           NSValue valueWithCGPoint CGPointMake 13 5  41 5             NSValue valueWithCGPoint CGPointMake 42 5  56 5             NSValue valueWithCGPoint CGPointMake 39 5  69 5             NSValue valueWithCGPoint CGPointMake 42 5  84 5             NSValue valueWithCGPoint CGPointMake 13 5  100 0             NSValue valueWithCGPoint CGPointMake 6 0  70 5            nil             CGPoint tappedPoint   CGPointMake 23 0  70 0        if   self isPointInPolygon polygonVertices point tappedPoint             NSLog   YES          else           NSLog   NO

User · Answer

I think the following piece of code is the best solution  taken from here    int pnpoly int nvert  float  vertx  float  verty  float testx  float testy      int i  j  c   0    for  i   0  j   nvert-1  i  lt  nvert  j   i          if     verty i  gt testy      verty j  gt testy    amp  amp        testx  lt   vertx j -vertx i      testy-verty i      verty j -verty i     vertx i            c    c        return c      Arguments   nvert  Number of vertices in the polygon  Whether to repeat the first vertex at the end has been discussed in the article referred above  vertx  verty  Arrays containing the x- and y-coordinates of the polygon s vertices  testx  testy  X- and y-coordinate of the test point    It s both short and efficient and works both for convex and concave polygons  As suggested before  you should check the bounding rectangle first and treat polygon holes separately    The idea behind this is pretty simple  The author describes it as follows      I run a semi-infinite ray horizontally  increasing x  fixed y  out from the test point  and count how many edges it crosses  At each crossing  the ray switches between inside and outside  This is called the Jordan curve theorem    The variable c is switching from 0 to 1 and 1 to 0 each time the horizontal ray crosses any edge  So basically it s keeping track of whether the number of edges crossed are even or odd  0 means even and 1 means odd

User · Answer

David Segond s answer is pretty much the standard general answer  and Richard T s is the most common optimization  though therre are some others   Other strong optimizations are based on less general solutions   For example if you are going to check the same polygon with lots of points  triangulating the polygon can speed things up hugely as there are a number of very fast TIN searching algorithms   Another is if the polygon and points are on a limited plane at low resolution  say a screen display  you can paint the polygon onto a memory mapped display buffer in a given colour  and check the color of a given pixel to see if it lies in the polygons   Like many optimizations  these are based on specific rather than general cases  and yield beneifits based on amortized time rather than single usage   Working in this field  i found Joeseph O Rourkes  Computation Geometry in C  ISBN 0-521-44034-3 to be a great help

User · Answer

Compute the oriented sum of angles between the point p and each of the polygon apices  If the total oriented angle is 360 degrees  the point is inside  If the total is 0  the point is outside   I like this method better because it is more robust and less dependent on numerical precision   Methods that compute evenness of number of intersections are limited because you can  hit  an apex during the computation of the number of intersections   EDIT  By The Way  this method works with concave and convex polygons   EDIT  I recently found a whole Wikipedia article on the topic

User · Answer

Swift version of the answer by nirg   extension CGPoint       func isInsidePolygon vertices   CGPoint   - gt  Bool           guard  vertices isEmpty else   return false           var j   vertices last   c   false         for i in vertices               let a    i y  gt  y      j y  gt  y              let b    x  lt   j x - i x     y - i y     j y - i y    i x              if a  amp  amp  b   c    c               j   i                   return c

User · Answer

I ve made a Python implementation of nirg s  c   code   Inputs   bounding points  nodes that make up the polygon  bounding box positions  candidate points to filter   In my implementation created from the bounding box    The inputs are lists of tuples in the format    xcord  ycord           Returns   All the points that are inside the polygon     def polygon ray casting self  bounding points  bounding box positions         Arrays containing the x- and y-coordinates of the polygon s vertices      vertx    point 0  for point in bounding points      verty    point 1  for point in bounding points        Number of vertices in the polygon     nvert   len bounding points        Points that are inside     points inside             For every candidate position within the bounding box     for idx  pos in enumerate bounding box positions           testx  testy    pos 0   pos 1           c   0         for i in range 0  nvert               j   i - 1 if i    0 else nvert - 1             if    verty i   gt  testy       verty j   gt  testy     and                      testx  lt   vertx j  - vertx i      testy - verty i      verty j  - verty i     vertx i                      c    1           If odd  that means that we are inside the polygon         if c   2    1               points inside append pos        return points inside   Again  the idea is taken from here

User · Answer

I realize this is old  but here is a ray casting algorithm implemented in Cocoa  in case anyone is interested   Not sure it is the most efficient way to do things  but it may help someone out   -  BOOL shape  NSBezierPath   path containsPoint  NSPoint point       NSBezierPath  currentPath    path bezierPathByFlatteningPath       BOOL result      float aggregateX   0    I use these to calculate the centroid of the shape     float aggregateY   0      NSPoint firstPoint 1        currentPath elementAtIndex 0 associatedPoints firstPoint       float olderX   firstPoint 0  x      float olderY   firstPoint 0  y      NSPoint interPoint      int noOfIntersections   0       for  int n   0  n  lt   currentPath elementCount   n              NSPoint points 1            currentPath elementAtIndex n associatedPoints points           aggregateX    points 0  x          aggregateY    points 0  y             for  int n   0  n  lt   currentPath elementCount   n              NSPoint points 1             currentPath elementAtIndex n associatedPoints points             line equations in Ax   By   C form         float  A FOO    aggregateY  currentPath elementCount   - point y            float  B FOO   point x -  aggregateX  currentPath elementCount            float  C FOO     A FOO   point x      B FOO   point y            float  A BAR   olderY - points 0  y          float  B BAR   points 0  x - olderX          float  C BAR     A BAR   olderX      B BAR   olderY            float det     A FOO    B BAR  -   A BAR    B FOO           if  det    0                  intersection points with the edges             float xIntersectionPoint      B BAR    C FOO  -   B FOO    C BAR     det              float yIntersectionPoint      A FOO    C BAR  -   A BAR    C FOO     det              interPoint   NSMakePoint xIntersectionPoint  yIntersectionPoint               if  olderX  lt   points 0  x                      doesn t matter in which direction the ray goes  so I send it right-ward                  if   interPoint x  gt   olderX  amp  amp  interPoint x  lt   points 0  x   amp  amp   interPoint x  gt  point x                           noOfIntersections                                    else                   if   interPoint x  gt   points 0  x  amp  amp  interPoint x  lt   olderX   amp  amp   interPoint x  gt  point x                          noOfIntersections                                                       olderX   points 0  x          olderY   points 0  y            if  noOfIntersections   2    0            result   FALSE        else           result   TRUE            return result

User · Answer

Surprised nobody brought this up earlier  but for the pragmatists requiring a database  MongoDB has excellent support for Geo queries including this one   What you are looking for is      db neighborhoods findOne   geometry     geoIntersects     geometry      type   Point   coordinates     longitude    latitude                 Neighborhoods is the collection that stores one or more polygons in standard GeoJson format  If the query returns null it is not intersected otherwise it is   Very well documented here  https   docs mongodb com manual tutorial geospatial-tutorial   The performance for more than 6 000 points classified in a 330 irregular polygon grid was less than one minute with no optimization at all and including the time to update documents with their respective polygon

User · Answer

Scala version of solution by nirg  assumes bounding rectangle pre-check is done separately    def inside p  Point  polygon  Array Point   bounds  Bounds   Boolean        val length   polygon length     tailrec   def oddIntersections i  Int  j  Int  tracker  Boolean   Boolean         if  i    length        tracker     else         val intersects    polygon i  y  gt  p y      polygon j  y  gt  p y   amp  amp  p x  lt   polygon j  x - polygon i  x     p y - polygon i  y     polygon j  y - polygon i  y    polygon i  x       oddIntersections i   1  i  if  intersects   tracker else tracker               oddIntersections 0  length - 1  tracker   false

User · Answer

The trivial solution would be to divide the polygon to triangles and hit test the triangles as explained here    If your polygon is CONVEX there might be a better approach though  Look at the polygon as a collection of infinite lines  Each line dividing space into two  for every point it s easy to say if its on the one side or the other side of the line  If a point is on the same side of all lines then it is inside the polygon

User · Answer

To deal with the following special cases in Ray casting algorithm    The ray overlaps one of the polygon s side  The point is inside of the polygon and the ray passes through a vertex of the polygon  The point is outside of the polygon and the ray just touches one of the polygon s angle    Check Determining Whether A Point Is Inside A Complex Polygon  The article provides an easy way to resolve them so there will be no special treatment required for the above cases

User · Answer

The trivial solution would be to divide the polygon to triangles and hit test the triangles as explained here    If your polygon is CONVEX there might be a better approach though  Look at the polygon as a collection of infinite lines  Each line dividing space into two  for every point it s easy to say if its on the one side or the other side of the line  If a point is on the same side of all lines then it is inside the polygon

User · Answer

David Segond s answer is pretty much the standard general answer  and Richard T s is the most common optimization  though therre are some others   Other strong optimizations are based on less general solutions   For example if you are going to check the same polygon with lots of points  triangulating the polygon can speed things up hugely as there are a number of very fast TIN searching algorithms   Another is if the polygon and points are on a limited plane at low resolution  say a screen display  you can paint the polygon onto a memory mapped display buffer in a given colour  and check the color of a given pixel to see if it lies in the polygons   Like many optimizations  these are based on specific rather than general cases  and yield beneifits based on amortized time rather than single usage   Working in this field  i found Joeseph O Rourkes  Computation Geometry in C  ISBN 0-521-44034-3 to be a great help

User · Answer

VBA VERSION   Note  Remember that if your polygon is an area within a map that Latitude Longitude are Y X values as opposed to X Y  Latitude   Y  Longitude   X  due to from what I understand are historical implications from way back when Longitude was not a measurement   CLASS MODULE  CPoint  Private pXValue As Double Private pYValue As Double       X Value Property       Public Property Get X   As Double     X   pXValue End Property  Public Property Let X Value As Double      pXValue   Value End Property       Y Value Property       Public Property Get Y   As Double     Y   pYValue End Property  Public Property Let Y Value As Double      pYValue   Value End Property   MODULE   Public Function isPointInPolygon p As CPoint  polygon   As CPoint  As Boolean      Dim i As Integer     Dim j As Integer     Dim q As Object     Dim minX As Double     Dim maxX As Double     Dim minY As Double     Dim maxY As Double     minX   polygon 0  X     maxX   polygon 0  X     minY   polygon 0  Y     maxY   polygon 0  Y      For i   1 To UBound polygon          Set q   polygon i          minX   vbMin q X  minX          maxX   vbMax q X  maxX          minY   vbMin q Y  minY          maxY   vbMax q Y  maxY      Next i      If p X  lt  minX Or p X  gt  maxX Or p Y  lt  minY Or p Y  gt  maxY Then         isPointInPolygon   False         Exit Function     End If         SOURCE  http   www ecse rpi edu Homepages wrf Research Short Notes pnpoly html      isPointInPolygon   False     i   0     j   UBound polygon       Do While i  lt  UBound polygon    1         If  polygon i  Y  gt  p Y  Then             If  polygon j  Y  lt  p Y  Then                 If p X  lt   polygon j  X - polygon i  X     p Y - polygon i  Y     polygon j  Y - polygon i  Y    polygon i  X Then                     isPointInPolygon   True                     Exit Function                 End If             End If         ElseIf  polygon i  Y  lt  p Y  Then             If  polygon j  Y  gt  p Y  Then                 If p X  lt   polygon j  X - polygon i  X     p Y - polygon i  Y     polygon j  Y - polygon i  Y    polygon i  X Then                     isPointInPolygon   True                     Exit Function                 End If             End If         End If         j   i         i   i   1     Loop    End Function  Function vbMax n1  n2  As Double     vbMax   IIf n1  gt  n2  n1  n2  End Function  Function vbMin n1  n2  As Double     vbMin   IIf n1  gt  n2  n2  n1  End Function   Sub TestPointInPolygon        Dim i As Integer     Dim InPolygon As Boolean      MARKER Object     Dim p As CPoint     Set p   New CPoint     p X    lt ENTER X VALUE HERE gt      p Y    lt ENTER Y VALUE HERE gt       POLYGON OBJECT     Dim polygon   As CPoint     ReDim polygon  lt ENTER VALUE HERE gt    Amount of vertices in polygon - 1     For i   0 To  lt ENTER VALUE HERE gt   Same value as above        Set polygon i    New CPoint        polygon i  X    lt ASSIGN X VALUE HERE gt   Source a list of values that can be looped through        polgyon i  Y    lt ASSIGN Y VALUE HERE gt   Source a list of values that can be looped through     Next i      InPolygon   isPointInPolygon p  polygon      MsgBox InPolygon  End Sub

User · Answer

This seems to work in R  apologies for ugliness  would like to see better version     pnpoly  lt - function nvert vertx verty testx testy             c  lt - FALSE           j  lt - nvert            for  i in 1 nvert                 if    verty i  gt testy      verty j  gt testy    amp  amp       testx  lt   vertx j -vertx i    testy-verty i    verty j -verty i   vertx i                 c  lt -  c               j  lt - i     return c

User · Answer

I did some work on this back when I was a researcher under Michael Stonebraker - you know  the professor who came up with Ingres  PostgreSQL  etc   We realized that the fastest way was to first do a bounding box because it s SUPER fast  If it s outside the bounding box  it s outside  Otherwise  you do the harder work     If you want a great algorithm  look to the open source project PostgreSQL source code for the geo work     I want to point out  we never got any insight into right vs left handedness  also expressible as an  inside  vs  outside  problem       UPDATE  BKB s link provided a good number of reasonable algorithms  I was working on Earth Science problems and therefore needed a solution that works in latitude longitude  and it has the peculiar problem of handedness - is the area inside the smaller area or the bigger area  The answer is that the  direction  of the verticies matters - it s either left-handed or right handed and in this way you can indicate either area as  inside  any given polygon  As such  my work used solution three enumerated on that page    In addition  my work used separate functions for  on the line  tests      Since someone asked  we figured out that bounding box tests were best when the number of verticies went beyond some number - do a very quick test before doing the longer test if necessary    A bounding box is created by simply taking the largest x  smallest x  largest y and smallest y and putting them together to make four points of a box     Another tip for those that follow  we did all our more sophisticated and  light-dimming  computing in a grid space all in positive points on a plane and then re-projected back into  real  longitude latitude  thus avoiding possible errors of wrapping around when one crossed line 180 of longitude and when handling polar regions  Worked great

User · Answer

Compute the oriented sum of angles between the point p and each of the polygon apices  If the total oriented angle is 360 degrees  the point is inside  If the total is 0  the point is outside   I like this method better because it is more robust and less dependent on numerical precision   Methods that compute evenness of number of intersections are limited because you can  hit  an apex during the computation of the number of intersections   EDIT  By The Way  this method works with concave and convex polygons   EDIT  I recently found a whole Wikipedia article on the topic

User · Answer

C  version of nirg s answer is here  I ll just share the code  It may save someone some time   public static bool IsPointInPolygon IList lt Point gt  polygon  Point testPoint                bool result   false              int j   polygon Count   - 1              for  int i   0  i  lt  polygon Count    i                      if  polygon i  Y  lt  testPoint Y  amp  amp  polygon j  Y  gt   testPoint Y    polygon j  Y  lt  testPoint Y  amp  amp  polygon i  Y  gt   testPoint Y                        if  polygon i  X    testPoint Y - polygon i  Y     polygon j  Y - polygon i  Y     polygon j  X - polygon i  X   lt  testPoint X                            result    result                                                          j   i                            return result

User · Answer

There is nothing more beutiful than an inductive definition of a problem  For the sake of completeness here you have a version in prolog which might also clarify the thoughs behind ray casting   Based on the simulation of simplicity algorithm in http   www ecse rpi edu Homepages wrf Research Short Notes pnpoly html  Some helper predicates   exor A B  -   A B A   B  in range Coordinate CA CB   - exor  CA gt Coordinate   CB gt Coordinate     inside false   inside            inside X Y   X1 Y1 X2 Y2 R    - in range Y Y1 Y2   X  gt      X2-X1   Y-Y1    Y2-Y1         X1  toggle ray  inside X Y   X2 Y2 R    inside X Y   X2 Y2 R     get line          get line  XA YA XB YB   X1 Y1 X2 Y2 R   -  XA YA XB YB   X1 Y1 X2 Y2   get line  XA YA XB YB   X2 Y2 R      The equation of a line given 2 points A and B  Line A B   is                         YB-YA             Y - YA   -------    X - XA                        XB-YB     It is important that the direction of rotation for the line is setted to clock-wise for boundaries and anti-clock-wise for holes  We are going to check whether the point  X Y   i e the tested point is at the left half-plane of our line  it is a matter of taste  it could also be the right side  but also the direction of boundaries lines has to be changed in that case   this is to project the ray from the point to the right  or left  and acknowledge the intersection with the line  We have chosen to project the ray in the horizontal direction  again it is a matter of taste  it could also be done in vertical with similar restrictions   so we have                   XB-XA             X  lt  -------    Y - YA    XA                 YB-YA     Now we need to know if the point is at the left  or right  side of the line segment only  not the entire plane  so we need to  restrict the search only to this segment  but this is easy since to be inside the segment only one point in the line can be higher than Y in the vertical axis  As this is a stronger restriction it needs to be the first to check  so we take first only those lines meeting this requirement and then check its possition  By the Jordan Curve theorem any ray projected to a polygon must intersect at an even number of lines  So we are done  we will throw the ray to the right and then everytime it intersects a line  toggle its state  However in our implementation we are goint to check the lenght of the bag of solutions meeting the given restrictions and decide the innership upon it  for each line in the polygon this have to be done   is left half plane             is left half plane X Y  XA YA XB YB     X1 Y1 X2 Y2  R   Test   -  XA YA  XB YB      X1 Y1  X2 Y2   call Test  X      XB - XA     Y - YA      YB - YA    XA                                                             is left half plane X Y   XA YA  XB YB   R  Test    in y range at poly Y  XA YA XB YB  Polygon   - get line  XA YA XB YB  Polygon    in range Y YA YB   all in range Coordinate Polygon Lines   - aggregate bag Line      in y range at poly Coordinate Line Polygon   Lines    traverses ray X Y  Lines  Count   - aggregate bag Line   is left half plane X Y  Line  Lines   lt    IntersectingLines   length IntersectingLines  Count      This is the entry point predicate inside poly X Y Polygon Answer   - all in range Y Polygon Lines   traverses ray X Y  Lines  Count    1 is mod Count 2 - gt Answer inside Answer outside

User · Answer

I think the following piece of code is the best solution  taken from here    int pnpoly int nvert  float  vertx  float  verty  float testx  float testy      int i  j  c   0    for  i   0  j   nvert-1  i  lt  nvert  j   i          if     verty i  gt testy      verty j  gt testy    amp  amp        testx  lt   vertx j -vertx i      testy-verty i      verty j -verty i     vertx i            c    c        return c      Arguments   nvert  Number of vertices in the polygon  Whether to repeat the first vertex at the end has been discussed in the article referred above  vertx  verty  Arrays containing the x- and y-coordinates of the polygon s vertices  testx  testy  X- and y-coordinate of the test point    It s both short and efficient and works both for convex and concave polygons  As suggested before  you should check the bounding rectangle first and treat polygon holes separately    The idea behind this is pretty simple  The author describes it as follows      I run a semi-infinite ray horizontally  increasing x  fixed y  out from the test point  and count how many edges it crosses  At each crossing  the ray switches between inside and outside  This is called the Jordan curve theorem    The variable c is switching from 0 to 1 and 1 to 0 each time the horizontal ray crosses any edge  So basically it s keeping track of whether the number of edges crossed are even or odd  0 means even and 1 means odd

User · Answer

If you are looking for a java-script library there s a javascript google maps v3 extension for the Polygon class to detect whether or not a point resides within it    var polygon   new google maps Polygon       000000   1  1    336699   0 3   var isWithinPolygon   polygon containsLatLng 40  -90     Google Extention Github

User · Answer

This only works for convex shapes  but Minkowski Portal Refinement  and GJK are also great options for testing if a point is in a polygon   You  use minkowski subtraction to subtract the point from the polygon  then run those algorithms to see if the polygon contains the origin   Also  interestingly  you can describe your shapes a bit more implicitly using support functions which take a direction vector as input and spit out the farthest point along that vector   This allows you to describe any convex shape   curved  made out of polygons  or mixed   You can also do operations to combine the results of simple support functions to make more complex shapes   More info  http   xenocollide snethen com mpr2d html  Also  game programming gems 7 talks about how to do this in 3d

User · Answer

Most of the answers in this question are not handling all corner cases well  Some subtle corner cases like below   This is a javascript version with all corner cases well handled      Get relationship between a point and a polygon using ray-casting algorithm     param   x number  y number   P  point to check     param   x number  y number     polygon  the polygon     returns -1  outside  0  on edge  1  inside     function relationPP P  polygon        const between    p  a  b    gt  p  gt   a  amp  amp  p  lt   b    p  lt   a  amp  amp  p  gt   b     let inside   false     for  let i   polygon length-1  j   0  j  lt  polygon length  i   j  j              const A   polygon i          const B   polygon j             corner cases         if  P x    A x  amp  amp  P y    A y    P x    B x  amp  amp  P y    B y  return 0         if  A y    B y  amp  amp  P y    A y  amp  amp  between P x  A x  B x   return 0          if  between P y  A y  B y        if P inside the vertical range                filter out  quot ray pass vertex quot  problem by treating the line a little lower             if  P y    A y  amp  amp  B y  gt   A y    P y    B y  amp  amp  A y  gt   B y  continue                calc cross product  PA X PB   P lays on left side of AB if c  gt  0              const c    A x - P x     B y - P y  -  B x - P x     A y - P y              if  c    0  return 0             if   A y  lt  B y      c  gt  0   inside    inside                      return inside  1   -1

User · Answer

Heres a point in polygon test in C that isn t using ray-casting  And it can work for overlapping areas  self intersections   see the use holes argument      math lib  defined below     static float dot v2v2 const float a 2   const float b 2    static float angle signed v2v2 const float v1 2   const float v2 2    static void copy v2 v2 float r 2   const float a 2        intersection function    bool isect point poly v2 const float pt 2   const float verts   2   const unsigned int nr                           const bool use holes           we do the angle rule  define that all added angles should be about zero or  2   PI         float angletot   0 0      float fp1 2   fp2 2       unsigned int i      const float  p1   p2       p1   verts nr - 1           first vector        fp1 0    p1 0  - pt 0       fp1 1    p1 1  - pt 1        for  i   0  i  lt  nr  i              p2   verts i               second vector            fp2 0    p2 0  - pt 0           fp2 1    p2 1  - pt 1               dot and angle and cross            angletot    angle signed v2v2 fp1  fp2               circulate            copy v2 v2 fp1  fp2           p1   p2             angletot   fabsf angletot       if  use holes            const float nested   floorf  angletot    float  M PI   2 0     0 00001f           angletot -  nested    float  M PI   2 0           return  angletot  gt  4 0f       int nested   2             else           return  angletot  gt  4 0f               math lib     static float dot v2v2 const float a 2   const float b 2         return a 0    b 0    a 1    b 1      static float angle signed v2v2 const float v1 2   const float v2 2         const float perp dot    v1 1    v2 0   -  v1 0    v2 1        return atan2f perp dot  dot v2v2 v1  v2       static void copy v2 v2 float r 2   const float a 2         r 0    a 0       r 1    a 1       Note  this is one of the less optimal methods since it includes a lot of calls to atan2f  but it may be of interest to developers reading this thread  in my tests its  23x slower then using the line intersection method

User · Answer

C  version of nirg s answer is here  I ll just share the code  It may save someone some time   public static bool IsPointInPolygon IList lt Point gt  polygon  Point testPoint                bool result   false              int j   polygon Count   - 1              for  int i   0  i  lt  polygon Count    i                      if  polygon i  Y  lt  testPoint Y  amp  amp  polygon j  Y  gt   testPoint Y    polygon j  Y  lt  testPoint Y  amp  amp  polygon i  Y  gt   testPoint Y                        if  polygon i  X    testPoint Y - polygon i  Y     polygon j  Y - polygon i  Y     polygon j  X - polygon i  X   lt  testPoint X                            result    result                                                          j   i                            return result

User · Answer

Java Version   public class Geocode       private float latitude      private float longitude       public Geocode                public Geocode float latitude  float longitude            this latitude   latitude          this longitude   longitude             public float getLatitude             return latitude             public void setLatitude float latitude            this latitude   latitude             public float getLongitude             return longitude             public void setLongitude float longitude            this longitude   longitude           public class GeoPolygon       private ArrayList lt Geocode gt  points       public GeoPolygon             this points   new ArrayList lt Geocode gt                public GeoPolygon ArrayList lt Geocode gt  points            this points   points             public GeoPolygon add Geocode geo            points add geo           return this             public boolean inside Geocode geo            int i  j          boolean c   false          for  i   0  j   points size   - 1  i  lt  points size    j   i                  if    points get i  getLongitude    gt  geo getLongitude        points get j  getLongitude    gt  geo getLongitude      amp  amp                       geo getLatitude    lt   points get j  getLatitude   - points get i  getLatitude       geo getLongitude   - points get i  getLongitude       points get j  getLongitude   - points get i  getLongitude      points get i  getLatitude                     c    c                    return c

User · Answer

Here is golang version of  nirg answer  inspired by C  code by   m-katz   func isPointInPolygon polygon   point  testp point  bool       minX    polygon 0  X     maxX    polygon 0  X     minY    polygon 0  Y     maxY    polygon 0  Y      for    p    range polygon           minX   min p X  minX          maxX   max p X  maxX          minY   min p Y  minY          maxY   max p Y  maxY             if testp X  lt  minX    testp X  gt  maxX    testp Y  lt  minY    testp Y  gt  maxY           return false            inside    false     j    len polygon  - 1     for i    0  i  lt  len polygon   i             if  polygon i  Y  gt  testp Y      polygon j  Y  gt  testp Y   amp  amp  testp X  lt   polygon j  X-polygon i  X   testp Y-polygon i  Y   polygon j  Y-polygon i  Y  polygon i  X               inside    inside                   j   i            return inside

User · Answer

Most of the answers in this question are not handling all corner cases well  Some subtle corner cases like below   This is a javascript version with all corner cases well handled      Get relationship between a point and a polygon using ray-casting algorithm     param   x number  y number   P  point to check     param   x number  y number     polygon  the polygon     returns -1  outside  0  on edge  1  inside     function relationPP P  polygon        const between    p  a  b    gt  p  gt   a  amp  amp  p  lt   b    p  lt   a  amp  amp  p  gt   b     let inside   false     for  let i   polygon length-1  j   0  j  lt  polygon length  i   j  j              const A   polygon i          const B   polygon j             corner cases         if  P x    A x  amp  amp  P y    A y    P x    B x  amp  amp  P y    B y  return 0         if  A y    B y  amp  amp  P y    A y  amp  amp  between P x  A x  B x   return 0          if  between P y  A y  B y        if P inside the vertical range                filter out  quot ray pass vertex quot  problem by treating the line a little lower             if  P y    A y  amp  amp  B y  gt   A y    P y    B y  amp  amp  A y  gt   B y  continue                calc cross product  PA X PB   P lays on left side of AB if c  gt  0              const c    A x - P x     B y - P y  -  B x - P x     A y - P y              if  c    0  return 0             if   A y  lt  B y      c  gt  0   inside    inside                      return inside  1   -1

User · Answer

The answer depends on if you have the simple or complex polygons  Simple polygons must not have any line segment intersections  So they can have the holes but lines can t cross each other  Complex regions can have the line intersections - so they can have the overlapping regions  or regions that touch each other just by a single point   For simple polygons the best algorithm is Ray casting  Crossing number  algorithm  For complex polygons  this algorithm doesn t detect points that are inside the overlapping regions  So for complex polygons you have to use Winding number algorithm   Here is an excellent article with C implementation of both algorithms  I tried them and they work well   http   geomalgorithms com a03- inclusion html

User · Answer

For graphics  I d rather not prefer integers  Many systems use integers for UI painting  pixels are ints after all   but macOS for example uses float for everything  macOS only knows points and a point can translate to one pixel  but depending on monitor resolution  it might translate to something else  On retina screens half a point  0 5 0 5  is pixel  Still  I never noticed that macOS UIs are significantly slower than other UIs  After all 3D APIs  OpenGL or Direct3D  also works with floats and modern graphics libraries very often take advantage of GPU acceleration   Now you said speed is your main concern  okay  let s go for speed  Before you run any sophisticated algorithm  first do a simple test  Create an axis aligned bounding box around your polygon  This is very easy  fast and can already safe you a lot of calculations   How does that work  Iterate over all points of the polygon and find the min max values of X and Y    E g  you have the points  9 1    4 3    2 7    8 2    3 6   This means Xmin is 2  Xmax is 9  Ymin is 1 and Ymax is 7  A point outside of the rectangle with the two edges  2 1  and  9 7  cannot be within the polygon      p is your point  p x is the x coord  p y is the y coord if  p x  lt  Xmin    p x  gt  Xmax    p y  lt  Ymin    p y  gt  Ymax           Definitely not within the polygon      This is the first test to run for any point  As you can see  this test is ultra fast but it s also very coarse  To handle points that are within the bounding rectangle  we need a more sophisticated algorithm  There are a couple of ways how this can be calculated  Which method works also depends on the fact if the polygon can have holes or will always be solid  Here are examples of solid ones  one convex  one concave      And here s one with a hole     The green one has a hole in the middle   The easiest algorithm  that can handle all three cases above and is still pretty fast is named ray casting  The idea of the algorithm is pretty simple  Draw a virtual ray from anywhere outside the polygon to your point and count how often it hits a side of the polygon  If the number of hits is even  it s outside of the polygon  if it s odd  it s inside     The winding number algorithm would be an alternative  it is more accurate for points being very close to a polygon line but it s also much slower  Ray casting may fail for points too close to a polygon side because of limited floating point precision and rounding issues  but in reality that is hardly a problem  as if a point lies that close to a side  it s often visually not even possible for a viewer to recognize if it is already inside or still outside   You still have the bounding box of above  remember  Just pick a point outside the bounding box and use it as starting point for your ray  E g  the point  Xmin - e p y  is outside the polygon for sure    But what is e  Well  e  actually epsilon  gives the bounding box some padding  As I said  ray tracing fails if we start too close to a polygon line  Since the bounding box might equal the polygon  if the polygon is an axis aligned rectangle  the bounding box is equal to the polygon itself    we need some padding to make this safe  that s all  How big should you choose e  Not too big  It depends on the coordinate system scale you use for drawing  If your pixel step width is 1 0  then just choose 1 0  yet 0 1 would have worked as well   Now that we have the ray with its start and end coordinates  the problem shifts from  is the point within the polygon  to  how often does the ray intersects a polygon side   Therefore we can t just work with the polygon points as before  now we need the actual sides  A side is always defined by two points   side 1   X1 Y1 - X2 Y2  side 2   X2 Y2 - X3 Y3  side 3   X3 Y3 - X4 Y4      You need to test the ray against all sides  Consider the ray to be a vector and every side to be a vector  The ray has to hit each side exactly once or never at all  It can t hit the same side twice  Two lines in 2D space will always intersect exactly once  unless they are parallel  in which case they never intersect  However since vectors have a limited length  two vectors might not be parallel and still never intersect because they are too short to ever meet each other      Test the ray against all sides int intersections   0  for  side   0  side  lt  numberOfSides  side             Test if current side intersects with ray         If yes  intersections      if   intersections  amp  1     1           Inside of polygon   else          Outside of polygon     So far so well  but how do you test if two vectors intersect  Here s some C code  not tested   that should do the trick    define NO 0  define YES 1  define COLLINEAR 2  int areIntersecting      float v1x1  float v1y1  float v1x2  float v1y2      float v2x1  float v2y1  float v2x2  float v2y2         float d1  d2      float a1  a2  b1  b2  c1  c2          Convert vector 1 to a line  line 1  of infinite length         We want the line in linear equation standard form  A x   B y   C   0        See  http   en wikipedia org wiki Linear equation     a1   v1y2 - v1y1      b1   v1x1 - v1x2      c1    v1x2   v1y1  -  v1x1   v1y2           Every point  x y   that solves the equation above  is on the line         every point that does not solve it  is not  The equation will have a        positive result if it is on one side of the line and a negative one         if is on the other side of it  We insert  x1 y1  and  x2 y2  of vector        2 into the equation above      d1    a1   v2x1     b1   v2y1    c1      d2    a1   v2x2     b1   v2y2    c1          If d1 and d2 both have the same sign  they are both on the same side        of our line 1 and in that case no intersection is possible  Careful          0 is a special case  that s why we don t test   gt    and   lt             but   lt   and   gt        if  d1  gt  0  amp  amp  d2  gt  0  return NO      if  d1  lt  0  amp  amp  d2  lt  0  return NO          The fact that vector 2 intersected the infinite line 1 above doesn t         mean it also intersects the vector 1  Vector 1 is only a subset of that        infinite line 1  so it may have intersected that line before the vector        started or after it ended  To know for sure  we have to repeat the        the same test the other way round  We start by calculating the         infinite line 2 in linear equation standard form      a2   v2y2 - v2y1      b2   v2x1 - v2x2      c2    v2x2   v2y1  -  v2x1   v2y2           Calculate d1 and d2 again  this time using points of vector 1      d1    a2   v1x1     b2   v1y1    c2      d2    a2   v1x2     b2   v1y2    c2          Again  if both have the same sign  and neither one is 0          no intersection is possible      if  d1  gt  0  amp  amp  d2  gt  0  return NO      if  d1  lt  0  amp  amp  d2  lt  0  return NO          If we get here  only two possibilities are left  Either the two        vectors intersect in exactly one point or they are collinear  which        means they intersect in any number of points from zero to infinite      if   a1   b2  -  a2   b1     0 0f  return COLLINEAR          If they are not collinear  they must intersect in exactly one point      return YES      The input values are the two endpoints of vector 1  v1x1 v1y1 and v1x2 v1y2  and vector 2  v2x1 v2y1 and v2x2 v2y2   So you have 2 vectors  4 points  8 coordinates  YES and NO are clear  YES increases intersections  NO does nothing    What about COLLINEAR  It means both vectors lie on the same infinite line  depending on position and length  they don t intersect at all or they intersect in an endless number of points  I m not absolutely sure how to handle this case  I would not count it as intersection either way  Well  this case is rather rare in practice anyway because of floating point rounding errors  better code would probably not test for    0 0f but instead for something like  lt  epsilon  where epsilon is a rather small number   If you need to test a larger number of points  you can certainly speed up the whole thing a bit by keeping the linear equation standard forms of the polygon sides in memory  so you don t have to recalculate these every time  This will save you two floating point multiplications and three floating point subtractions on every test in exchange for storing three floating point values per polygon side in memory  It s a typical memory vs computation time trade off   Last but not least  If you may use 3D hardware to solve the problem  there is an interesting alternative  Just let the GPU do all the work for you  Create a painting surface that is off screen  Fill it completely with the color black  Now let OpenGL or Direct3D paint your polygon  or even all of your polygons if you just want to test if the point is within any of them  but you don t care for which one  and fill the polygon s  with a different color  e g  white  To check if a point is within the polygon  get the color of this point from the drawing surface  This is just a O 1  memory fetch   Of course this method is only usable if your drawing surface doesn t have to be huge  If it cannot fit into the GPU memory  this method is slower than doing it on the CPU  If it would have to be huge and your GPU supports modern shaders  you can still use the GPU by implementing the ray casting shown above as a GPU shader  which absolutely is possible  For a larger number of polygons or a large number of points to test  this will pay off  consider some GPUs will be able to test 64 to 256 points in parallel  Note however that transferring data from CPU to GPU and back is always expensive  so for just testing a couple of points against a couple of simple polygons  where either the points or the polygons are dynamic and will change frequently  a GPU approach will rarely pay off

User · Answer

This is a presumably slightly less optimized version of the C code from here which was sourced from this page   My C   version uses a std  vector lt std  pair lt double  double gt  gt  and two doubles as an x and y  The logic should be exactly the same as the original C code  but I find mine easier to read  I can t speak for the performance   bool point in poly std  vector lt std  pair lt double  double gt  gt  amp  verts  double point x  double point y        bool in poly   false      auto num verts   verts size        for  int i   0  j   num verts - 1  i  lt  num verts  j   i              double x1   verts i  first          double y1   verts i  second          double x2   verts j  first          double y2   verts j  second           if    y1  gt  point y      y2  gt  point y    amp  amp               point x  lt   x2 - x1     point y - y1     y2 - y1    x1               in poly    in poly            return in poly      The original C code is  int pnpoly int nvert  float  vertx  float  verty  float testx  float testy      int i  j  c   0    for  i   0  j   nvert-1  i  lt  nvert  j   i          if     verty i  gt testy      verty j  gt testy    amp  amp        testx  lt   vertx j -vertx i      testy-verty i      verty j -verty i     vertx i            c    c        return c

User · Answer

I realize this is old  but here is a ray casting algorithm implemented in Cocoa  in case anyone is interested   Not sure it is the most efficient way to do things  but it may help someone out   -  BOOL shape  NSBezierPath   path containsPoint  NSPoint point       NSBezierPath  currentPath    path bezierPathByFlatteningPath       BOOL result      float aggregateX   0    I use these to calculate the centroid of the shape     float aggregateY   0      NSPoint firstPoint 1        currentPath elementAtIndex 0 associatedPoints firstPoint       float olderX   firstPoint 0  x      float olderY   firstPoint 0  y      NSPoint interPoint      int noOfIntersections   0       for  int n   0  n  lt   currentPath elementCount   n              NSPoint points 1            currentPath elementAtIndex n associatedPoints points           aggregateX    points 0  x          aggregateY    points 0  y             for  int n   0  n  lt   currentPath elementCount   n              NSPoint points 1             currentPath elementAtIndex n associatedPoints points             line equations in Ax   By   C form         float  A FOO    aggregateY  currentPath elementCount   - point y            float  B FOO   point x -  aggregateX  currentPath elementCount            float  C FOO     A FOO   point x      B FOO   point y            float  A BAR   olderY - points 0  y          float  B BAR   points 0  x - olderX          float  C BAR     A BAR   olderX      B BAR   olderY            float det     A FOO    B BAR  -   A BAR    B FOO           if  det    0                  intersection points with the edges             float xIntersectionPoint      B BAR    C FOO  -   B FOO    C BAR     det              float yIntersectionPoint      A FOO    C BAR  -   A BAR    C FOO     det              interPoint   NSMakePoint xIntersectionPoint  yIntersectionPoint               if  olderX  lt   points 0  x                      doesn t matter in which direction the ray goes  so I send it right-ward                  if   interPoint x  gt   olderX  amp  amp  interPoint x  lt   points 0  x   amp  amp   interPoint x  gt  point x                           noOfIntersections                                    else                   if   interPoint x  gt   points 0  x  amp  amp  interPoint x  lt   olderX   amp  amp   interPoint x  gt  point x                          noOfIntersections                                                       olderX   points 0  x          olderY   points 0  y            if  noOfIntersections   2    0            result   FALSE        else           result   TRUE            return result

User · Answer

For graphics  I d rather not prefer integers  Many systems use integers for UI painting  pixels are ints after all   but macOS for example uses float for everything  macOS only knows points and a point can translate to one pixel  but depending on monitor resolution  it might translate to something else  On retina screens half a point  0 5 0 5  is pixel  Still  I never noticed that macOS UIs are significantly slower than other UIs  After all 3D APIs  OpenGL or Direct3D  also works with floats and modern graphics libraries very often take advantage of GPU acceleration   Now you said speed is your main concern  okay  let s go for speed  Before you run any sophisticated algorithm  first do a simple test  Create an axis aligned bounding box around your polygon  This is very easy  fast and can already safe you a lot of calculations   How does that work  Iterate over all points of the polygon and find the min max values of X and Y    E g  you have the points  9 1    4 3    2 7    8 2    3 6   This means Xmin is 2  Xmax is 9  Ymin is 1 and Ymax is 7  A point outside of the rectangle with the two edges  2 1  and  9 7  cannot be within the polygon      p is your point  p x is the x coord  p y is the y coord if  p x  lt  Xmin    p x  gt  Xmax    p y  lt  Ymin    p y  gt  Ymax           Definitely not within the polygon      This is the first test to run for any point  As you can see  this test is ultra fast but it s also very coarse  To handle points that are within the bounding rectangle  we need a more sophisticated algorithm  There are a couple of ways how this can be calculated  Which method works also depends on the fact if the polygon can have holes or will always be solid  Here are examples of solid ones  one convex  one concave      And here s one with a hole     The green one has a hole in the middle   The easiest algorithm  that can handle all three cases above and is still pretty fast is named ray casting  The idea of the algorithm is pretty simple  Draw a virtual ray from anywhere outside the polygon to your point and count how often it hits a side of the polygon  If the number of hits is even  it s outside of the polygon  if it s odd  it s inside     The winding number algorithm would be an alternative  it is more accurate for points being very close to a polygon line but it s also much slower  Ray casting may fail for points too close to a polygon side because of limited floating point precision and rounding issues  but in reality that is hardly a problem  as if a point lies that close to a side  it s often visually not even possible for a viewer to recognize if it is already inside or still outside   You still have the bounding box of above  remember  Just pick a point outside the bounding box and use it as starting point for your ray  E g  the point  Xmin - e p y  is outside the polygon for sure    But what is e  Well  e  actually epsilon  gives the bounding box some padding  As I said  ray tracing fails if we start too close to a polygon line  Since the bounding box might equal the polygon  if the polygon is an axis aligned rectangle  the bounding box is equal to the polygon itself    we need some padding to make this safe  that s all  How big should you choose e  Not too big  It depends on the coordinate system scale you use for drawing  If your pixel step width is 1 0  then just choose 1 0  yet 0 1 would have worked as well   Now that we have the ray with its start and end coordinates  the problem shifts from  is the point within the polygon  to  how often does the ray intersects a polygon side   Therefore we can t just work with the polygon points as before  now we need the actual sides  A side is always defined by two points   side 1   X1 Y1 - X2 Y2  side 2   X2 Y2 - X3 Y3  side 3   X3 Y3 - X4 Y4      You need to test the ray against all sides  Consider the ray to be a vector and every side to be a vector  The ray has to hit each side exactly once or never at all  It can t hit the same side twice  Two lines in 2D space will always intersect exactly once  unless they are parallel  in which case they never intersect  However since vectors have a limited length  two vectors might not be parallel and still never intersect because they are too short to ever meet each other      Test the ray against all sides int intersections   0  for  side   0  side  lt  numberOfSides  side             Test if current side intersects with ray         If yes  intersections      if   intersections  amp  1     1           Inside of polygon   else          Outside of polygon     So far so well  but how do you test if two vectors intersect  Here s some C code  not tested   that should do the trick    define NO 0  define YES 1  define COLLINEAR 2  int areIntersecting      float v1x1  float v1y1  float v1x2  float v1y2      float v2x1  float v2y1  float v2x2  float v2y2         float d1  d2      float a1  a2  b1  b2  c1  c2          Convert vector 1 to a line  line 1  of infinite length         We want the line in linear equation standard form  A x   B y   C   0        See  http   en wikipedia org wiki Linear equation     a1   v1y2 - v1y1      b1   v1x1 - v1x2      c1    v1x2   v1y1  -  v1x1   v1y2           Every point  x y   that solves the equation above  is on the line         every point that does not solve it  is not  The equation will have a        positive result if it is on one side of the line and a negative one         if is on the other side of it  We insert  x1 y1  and  x2 y2  of vector        2 into the equation above      d1    a1   v2x1     b1   v2y1    c1      d2    a1   v2x2     b1   v2y2    c1          If d1 and d2 both have the same sign  they are both on the same side        of our line 1 and in that case no intersection is possible  Careful          0 is a special case  that s why we don t test   gt    and   lt             but   lt   and   gt        if  d1  gt  0  amp  amp  d2  gt  0  return NO      if  d1  lt  0  amp  amp  d2  lt  0  return NO          The fact that vector 2 intersected the infinite line 1 above doesn t         mean it also intersects the vector 1  Vector 1 is only a subset of that        infinite line 1  so it may have intersected that line before the vector        started or after it ended  To know for sure  we have to repeat the        the same test the other way round  We start by calculating the         infinite line 2 in linear equation standard form      a2   v2y2 - v2y1      b2   v2x1 - v2x2      c2    v2x2   v2y1  -  v2x1   v2y2           Calculate d1 and d2 again  this time using points of vector 1      d1    a2   v1x1     b2   v1y1    c2      d2    a2   v1x2     b2   v1y2    c2          Again  if both have the same sign  and neither one is 0          no intersection is possible      if  d1  gt  0  amp  amp  d2  gt  0  return NO      if  d1  lt  0  amp  amp  d2  lt  0  return NO          If we get here  only two possibilities are left  Either the two        vectors intersect in exactly one point or they are collinear  which        means they intersect in any number of points from zero to infinite      if   a1   b2  -  a2   b1     0 0f  return COLLINEAR          If they are not collinear  they must intersect in exactly one point      return YES      The input values are the two endpoints of vector 1  v1x1 v1y1 and v1x2 v1y2  and vector 2  v2x1 v2y1 and v2x2 v2y2   So you have 2 vectors  4 points  8 coordinates  YES and NO are clear  YES increases intersections  NO does nothing    What about COLLINEAR  It means both vectors lie on the same infinite line  depending on position and length  they don t intersect at all or they intersect in an endless number of points  I m not absolutely sure how to handle this case  I would not count it as intersection either way  Well  this case is rather rare in practice anyway because of floating point rounding errors  better code would probably not test for    0 0f but instead for something like  lt  epsilon  where epsilon is a rather small number   If you need to test a larger number of points  you can certainly speed up the whole thing a bit by keeping the linear equation standard forms of the polygon sides in memory  so you don t have to recalculate these every time  This will save you two floating point multiplications and three floating point subtractions on every test in exchange for storing three floating point values per polygon side in memory  It s a typical memory vs computation time trade off   Last but not least  If you may use 3D hardware to solve the problem  there is an interesting alternative  Just let the GPU do all the work for you  Create a painting surface that is off screen  Fill it completely with the color black  Now let OpenGL or Direct3D paint your polygon  or even all of your polygons if you just want to test if the point is within any of them  but you don t care for which one  and fill the polygon s  with a different color  e g  white  To check if a point is within the polygon  get the color of this point from the drawing surface  This is just a O 1  memory fetch   Of course this method is only usable if your drawing surface doesn t have to be huge  If it cannot fit into the GPU memory  this method is slower than doing it on the CPU  If it would have to be huge and your GPU supports modern shaders  you can still use the GPU by implementing the ray casting shown above as a GPU shader  which absolutely is possible  For a larger number of polygons or a large number of points to test  this will pay off  consider some GPUs will be able to test 64 to 256 points in parallel  Note however that transferring data from CPU to GPU and back is always expensive  so for just testing a couple of points against a couple of simple polygons  where either the points or the polygons are dynamic and will change frequently  a GPU approach will rarely pay off

User · Answer

For graphics  I d rather not prefer integers  Many systems use integers for UI painting  pixels are ints after all   but macOS for example uses float for everything  macOS only knows points and a point can translate to one pixel  but depending on monitor resolution  it might translate to something else  On retina screens half a point  0 5 0 5  is pixel  Still  I never noticed that macOS UIs are significantly slower than other UIs  After all 3D APIs  OpenGL or Direct3D  also works with floats and modern graphics libraries very often take advantage of GPU acceleration   Now you said speed is your main concern  okay  let s go for speed  Before you run any sophisticated algorithm  first do a simple test  Create an axis aligned bounding box around your polygon  This is very easy  fast and can already safe you a lot of calculations   How does that work  Iterate over all points of the polygon and find the min max values of X and Y    E g  you have the points  9 1    4 3    2 7    8 2    3 6   This means Xmin is 2  Xmax is 9  Ymin is 1 and Ymax is 7  A point outside of the rectangle with the two edges  2 1  and  9 7  cannot be within the polygon      p is your point  p x is the x coord  p y is the y coord if  p x  lt  Xmin    p x  gt  Xmax    p y  lt  Ymin    p y  gt  Ymax           Definitely not within the polygon      This is the first test to run for any point  As you can see  this test is ultra fast but it s also very coarse  To handle points that are within the bounding rectangle  we need a more sophisticated algorithm  There are a couple of ways how this can be calculated  Which method works also depends on the fact if the polygon can have holes or will always be solid  Here are examples of solid ones  one convex  one concave      And here s one with a hole     The green one has a hole in the middle   The easiest algorithm  that can handle all three cases above and is still pretty fast is named ray casting  The idea of the algorithm is pretty simple  Draw a virtual ray from anywhere outside the polygon to your point and count how often it hits a side of the polygon  If the number of hits is even  it s outside of the polygon  if it s odd  it s inside     The winding number algorithm would be an alternative  it is more accurate for points being very close to a polygon line but it s also much slower  Ray casting may fail for points too close to a polygon side because of limited floating point precision and rounding issues  but in reality that is hardly a problem  as if a point lies that close to a side  it s often visually not even possible for a viewer to recognize if it is already inside or still outside   You still have the bounding box of above  remember  Just pick a point outside the bounding box and use it as starting point for your ray  E g  the point  Xmin - e p y  is outside the polygon for sure    But what is e  Well  e  actually epsilon  gives the bounding box some padding  As I said  ray tracing fails if we start too close to a polygon line  Since the bounding box might equal the polygon  if the polygon is an axis aligned rectangle  the bounding box is equal to the polygon itself    we need some padding to make this safe  that s all  How big should you choose e  Not too big  It depends on the coordinate system scale you use for drawing  If your pixel step width is 1 0  then just choose 1 0  yet 0 1 would have worked as well   Now that we have the ray with its start and end coordinates  the problem shifts from  is the point within the polygon  to  how often does the ray intersects a polygon side   Therefore we can t just work with the polygon points as before  now we need the actual sides  A side is always defined by two points   side 1   X1 Y1 - X2 Y2  side 2   X2 Y2 - X3 Y3  side 3   X3 Y3 - X4 Y4      You need to test the ray against all sides  Consider the ray to be a vector and every side to be a vector  The ray has to hit each side exactly once or never at all  It can t hit the same side twice  Two lines in 2D space will always intersect exactly once  unless they are parallel  in which case they never intersect  However since vectors have a limited length  two vectors might not be parallel and still never intersect because they are too short to ever meet each other      Test the ray against all sides int intersections   0  for  side   0  side  lt  numberOfSides  side             Test if current side intersects with ray         If yes  intersections      if   intersections  amp  1     1           Inside of polygon   else          Outside of polygon     So far so well  but how do you test if two vectors intersect  Here s some C code  not tested   that should do the trick    define NO 0  define YES 1  define COLLINEAR 2  int areIntersecting      float v1x1  float v1y1  float v1x2  float v1y2      float v2x1  float v2y1  float v2x2  float v2y2         float d1  d2      float a1  a2  b1  b2  c1  c2          Convert vector 1 to a line  line 1  of infinite length         We want the line in linear equation standard form  A x   B y   C   0        See  http   en wikipedia org wiki Linear equation     a1   v1y2 - v1y1      b1   v1x1 - v1x2      c1    v1x2   v1y1  -  v1x1   v1y2           Every point  x y   that solves the equation above  is on the line         every point that does not solve it  is not  The equation will have a        positive result if it is on one side of the line and a negative one         if is on the other side of it  We insert  x1 y1  and  x2 y2  of vector        2 into the equation above      d1    a1   v2x1     b1   v2y1    c1      d2    a1   v2x2     b1   v2y2    c1          If d1 and d2 both have the same sign  they are both on the same side        of our line 1 and in that case no intersection is possible  Careful          0 is a special case  that s why we don t test   gt    and   lt             but   lt   and   gt        if  d1  gt  0  amp  amp  d2  gt  0  return NO      if  d1  lt  0  amp  amp  d2  lt  0  return NO          The fact that vector 2 intersected the infinite line 1 above doesn t         mean it also intersects the vector 1  Vector 1 is only a subset of that        infinite line 1  so it may have intersected that line before the vector        started or after it ended  To know for sure  we have to repeat the        the same test the other way round  We start by calculating the         infinite line 2 in linear equation standard form      a2   v2y2 - v2y1      b2   v2x1 - v2x2      c2    v2x2   v2y1  -  v2x1   v2y2           Calculate d1 and d2 again  this time using points of vector 1      d1    a2   v1x1     b2   v1y1    c2      d2    a2   v1x2     b2   v1y2    c2          Again  if both have the same sign  and neither one is 0          no intersection is possible      if  d1  gt  0  amp  amp  d2  gt  0  return NO      if  d1  lt  0  amp  amp  d2  lt  0  return NO          If we get here  only two possibilities are left  Either the two        vectors intersect in exactly one point or they are collinear  which        means they intersect in any number of points from zero to infinite      if   a1   b2  -  a2   b1     0 0f  return COLLINEAR          If they are not collinear  they must intersect in exactly one point      return YES      The input values are the two endpoints of vector 1  v1x1 v1y1 and v1x2 v1y2  and vector 2  v2x1 v2y1 and v2x2 v2y2   So you have 2 vectors  4 points  8 coordinates  YES and NO are clear  YES increases intersections  NO does nothing    What about COLLINEAR  It means both vectors lie on the same infinite line  depending on position and length  they don t intersect at all or they intersect in an endless number of points  I m not absolutely sure how to handle this case  I would not count it as intersection either way  Well  this case is rather rare in practice anyway because of floating point rounding errors  better code would probably not test for    0 0f but instead for something like  lt  epsilon  where epsilon is a rather small number   If you need to test a larger number of points  you can certainly speed up the whole thing a bit by keeping the linear equation standard forms of the polygon sides in memory  so you don t have to recalculate these every time  This will save you two floating point multiplications and three floating point subtractions on every test in exchange for storing three floating point values per polygon side in memory  It s a typical memory vs computation time trade off   Last but not least  If you may use 3D hardware to solve the problem  there is an interesting alternative  Just let the GPU do all the work for you  Create a painting surface that is off screen  Fill it completely with the color black  Now let OpenGL or Direct3D paint your polygon  or even all of your polygons if you just want to test if the point is within any of them  but you don t care for which one  and fill the polygon s  with a different color  e g  white  To check if a point is within the polygon  get the color of this point from the drawing surface  This is just a O 1  memory fetch   Of course this method is only usable if your drawing surface doesn t have to be huge  If it cannot fit into the GPU memory  this method is slower than doing it on the CPU  If it would have to be huge and your GPU supports modern shaders  you can still use the GPU by implementing the ray casting shown above as a GPU shader  which absolutely is possible  For a larger number of polygons or a large number of points to test  this will pay off  consider some GPUs will be able to test 64 to 256 points in parallel  Note however that transferring data from CPU to GPU and back is always expensive  so for just testing a couple of points against a couple of simple polygons  where either the points or the polygons are dynamic and will change frequently  a GPU approach will rarely pay off

User · Answer

You can do this by  checking if the area formed by  connecting the desired point to the vertices of your polygon matches the area of the polygon itself    Or you could check if the sum of the inner angles from your point to each pair of two consecutive  polygon vertices to your check point sums to 360  but I have the feeling that the first option is quicker because it doesn t involve divisions nor calculations of inverse of trigonometric functions   I don t know what happens if your polygon has a hole inside it but it seems to me that the main idea can be adapted to this situation   You can as well post the question in a math community  I bet they have one million ways of doing that

User · Answer

For the completeness  here s the lua implementation of the algorithm provided by nirg and discussed by Mecki   function pnpoly area  test      local inside   false     local tx  ty   table unpack test      local j    area     for i 1   area do         local vxi  vyi   table unpack area i           local vxj  vyj   table unpack area j           if  vyi  gt  ty      vyj  gt  ty          and tx  lt   vxj - vxi   ty - vyi   vyj - vyi    vxi         then             inside   not inside         end         j   i     end     return inside end   The variable area is a table of points which are in turn stored as 2D tables  Example    gt  A     2  1    1  2    15  3    3  4    5  3    4  1 5    gt  T    2  1 1   gt  pnpoly A  T  true   The link to GitHub Gist

User · Answer

If you are looking for a java-script library there s a javascript google maps v3 extension for the Polygon class to detect whether or not a point resides within it    var polygon   new google maps Polygon       000000   1  1    336699   0 3   var isWithinPolygon   polygon containsLatLng 40  -90     Google Extention Github

User · Answer

Here is a C  version of the answer given by nirg  which comes from this RPI professor  Note that use of the code from that RPI source requires attribution   A bounding box check has been added at the top  However  as James Brown points out  the main code is almost as fast as the bounding box check itself  so the bounding box check can actually slow the overall operation  in the case that most of the points you are checking are inside the bounding box  So you could leave the bounding box check out  or an alternative would be to precompute the bounding boxes of your polygons if they don t change shape too often   public bool IsPointInPolygon  Point p  Point   polygon         double minX   polygon  0   X      double maxX   polygon  0   X      double minY   polygon  0   Y      double maxY   polygon  0   Y      for   int i   1   i  lt  polygon Length   i                   Point q   polygon  i            minX   Math Min  q X  minX            maxX   Math Max  q X  maxX            minY   Math Min  q Y  minY            maxY   Math Max  q Y  maxY               if   p X  lt  minX    p X  gt  maxX    p Y  lt  minY    p Y  gt  maxY                 return false                https   wrf ecse rpi edu Research Short Notes pnpoly html     bool inside   false      for   int i   0  j   polygon Length - 1   i  lt  polygon Length   j   i                   if     polygon  i   Y  gt  p Y        polygon  j   Y  gt  p Y    amp  amp               p X  lt    polygon  j   X - polygon  i   X       p Y - polygon  i   Y       polygon  j   Y - polygon  i   Y     polygon  i   X                         inside    inside                       return inside

User · Answer

Compute the oriented sum of angles between the point p and each of the polygon apices  If the total oriented angle is 360 degrees  the point is inside  If the total is 0  the point is outside   I like this method better because it is more robust and less dependent on numerical precision   Methods that compute evenness of number of intersections are limited because you can  hit  an apex during the computation of the number of intersections   EDIT  By The Way  this method works with concave and convex polygons   EDIT  I recently found a whole Wikipedia article on the topic

User · Answer

For the completeness  here s the lua implementation of the algorithm provided by nirg and discussed by Mecki   function pnpoly area  test      local inside   false     local tx  ty   table unpack test      local j    area     for i 1   area do         local vxi  vyi   table unpack area i           local vxj  vyj   table unpack area j           if  vyi  gt  ty      vyj  gt  ty          and tx  lt   vxj - vxi   ty - vyi   vyj - vyi    vxi         then             inside   not inside         end         j   i     end     return inside end   The variable area is a table of points which are in turn stored as 2D tables  Example    gt  A     2  1    1  2    15  3    3  4    5  3    4  1 5    gt  T    2  1 1   gt  pnpoly A  T  true   The link to GitHub Gist

User · Answer

For Detecting hit on Polygon we need to test two things    If Point is inside polygon area   can be accomplished by Ray-Casting Algorithm  If Point is on the polygon border can be accomplished by same algorithm which is used for point detection on polyline line

User · Answer

There is nothing more beutiful than an inductive definition of a problem  For the sake of completeness here you have a version in prolog which might also clarify the thoughs behind ray casting   Based on the simulation of simplicity algorithm in http   www ecse rpi edu Homepages wrf Research Short Notes pnpoly html  Some helper predicates   exor A B  -   A B A   B  in range Coordinate CA CB   - exor  CA gt Coordinate   CB gt Coordinate     inside false   inside            inside X Y   X1 Y1 X2 Y2 R    - in range Y Y1 Y2   X  gt      X2-X1   Y-Y1    Y2-Y1         X1  toggle ray  inside X Y   X2 Y2 R    inside X Y   X2 Y2 R     get line          get line  XA YA XB YB   X1 Y1 X2 Y2 R   -  XA YA XB YB   X1 Y1 X2 Y2   get line  XA YA XB YB   X2 Y2 R      The equation of a line given 2 points A and B  Line A B   is                         YB-YA             Y - YA   -------    X - XA                        XB-YB     It is important that the direction of rotation for the line is setted to clock-wise for boundaries and anti-clock-wise for holes  We are going to check whether the point  X Y   i e the tested point is at the left half-plane of our line  it is a matter of taste  it could also be the right side  but also the direction of boundaries lines has to be changed in that case   this is to project the ray from the point to the right  or left  and acknowledge the intersection with the line  We have chosen to project the ray in the horizontal direction  again it is a matter of taste  it could also be done in vertical with similar restrictions   so we have                   XB-XA             X  lt  -------    Y - YA    XA                 YB-YA     Now we need to know if the point is at the left  or right  side of the line segment only  not the entire plane  so we need to  restrict the search only to this segment  but this is easy since to be inside the segment only one point in the line can be higher than Y in the vertical axis  As this is a stronger restriction it needs to be the first to check  so we take first only those lines meeting this requirement and then check its possition  By the Jordan Curve theorem any ray projected to a polygon must intersect at an even number of lines  So we are done  we will throw the ray to the right and then everytime it intersects a line  toggle its state  However in our implementation we are goint to check the lenght of the bag of solutions meeting the given restrictions and decide the innership upon it  for each line in the polygon this have to be done   is left half plane             is left half plane X Y  XA YA XB YB     X1 Y1 X2 Y2  R   Test   -  XA YA  XB YB      X1 Y1  X2 Y2   call Test  X      XB - XA     Y - YA      YB - YA    XA                                                             is left half plane X Y   XA YA  XB YB   R  Test    in y range at poly Y  XA YA XB YB  Polygon   - get line  XA YA XB YB  Polygon    in range Y YA YB   all in range Coordinate Polygon Lines   - aggregate bag Line      in y range at poly Coordinate Line Polygon   Lines    traverses ray X Y  Lines  Count   - aggregate bag Line   is left half plane X Y  Line  Lines   lt    IntersectingLines   length IntersectingLines  Count      This is the entry point predicate inside poly X Y Polygon Answer   - all in range Y Polygon Lines   traverses ray X Y  Lines  Count    1 is mod Count 2 - gt Answer inside Answer outside

User · Answer

Obj-C version of nirg s answer with sample method for testing points  Nirg s answer worked well for me   -  BOOL isPointInPolygon  NSArray   vertices point  CGPoint test       NSUInteger nvert    vertices count       NSInteger i  j  c   0      CGPoint verti  vertj       for  i   0  j   nvert-1  i  lt  nvert  j   i              verti     NSValue    vertices objectAtIndex i  CGPointValue           vertj     NSValue    vertices objectAtIndex j  CGPointValue           if     verti y  gt  test y      vertj y  gt  test y     amp  amp            test x  lt    vertj x - verti x       test y - verti y       vertj y - verti y     verti x                c    c             return  c   YES   NO      -  void testPoint        NSArray  polygonVertices    NSArray arrayWithObjects           NSValue valueWithCGPoint CGPointMake 13 5  41 5             NSValue valueWithCGPoint CGPointMake 42 5  56 5             NSValue valueWithCGPoint CGPointMake 39 5  69 5             NSValue valueWithCGPoint CGPointMake 42 5  84 5             NSValue valueWithCGPoint CGPointMake 13 5  100 0             NSValue valueWithCGPoint CGPointMake 6 0  70 5            nil             CGPoint tappedPoint   CGPointMake 23 0  70 0        if   self isPointInPolygon polygonVertices point tappedPoint             NSLog   YES          else           NSLog   NO

User · Answer

Here is a JavaScript variant of the answer by M  Katz based on Nirg s approach   function pointIsInPoly p  polygon        var isInside   false      var minX   polygon 0  x  maxX   polygon 0  x      var minY   polygon 0  y  maxY   polygon 0  y      for  var n   1  n  lt  polygon length  n              var q   polygon n           minX   Math min q x  minX           maxX   Math max q x  maxX           minY   Math min q y  minY           maxY   Math max q y  maxY              if  p x  lt  minX    p x  gt  maxX    p y  lt  minY    p y  gt  maxY            return false             var i   0  j   polygon length - 1      for  i  j  i  lt  polygon length  j   i              if    polygon i  y  gt  p y      polygon j  y  gt  p y   amp  amp                  p x  lt   polygon j  x - polygon i  x     p y - polygon i  y     polygon j  y - polygon i  y    polygon i  x                 isInside    isInside                       return isInside

User · Answer

The Eric Haines article cited by bobobobo is really excellent  Particularly interesting are the tables comparing performance of the algorithms  the angle summation method is really bad compared to the others  Also interesting is that optimisations like using a lookup grid to further subdivide the polygon into  in  and  out  sectors can make the test incredibly fast even on polygons with   1000 sides   Anyway  it s early days but my vote goes to the  crossings  method  which is pretty much what Mecki describes I think  However I found it most succintly described and codified by David Bourke  I love that there is no real trigonometry required  and it works for convex and concave  and it performs reasonably well as the number of sides increases   By the way  here s one of the performance tables from the Eric Haines  article for interest  testing on random polygons                          number of edges per polygon                          3       4      10      100    1000 MacMartin               2 9     3 2     5 9     50 6    485 Crossings               3 1     3 4     6 8     60 0    624 Triangle Fan edge sort  1 1     1 8     6 5     77 6    787 Triangle Fan            1 2     2 1     7 3     85 4    865 Barycentric             2 1     3 8    13 8    160 7   1665 Angle Summation        56 2    70 4   153 6   1403 8  14693  Grid  100x100           1 5     1 5     1 6      2 1      9 8 Grid  20x20             1 7     1 7     1 9      5 7     42 2 Bins  100               1 8     1 9     2 7     15 1    117 Bins  20                2 1     2 2     3 7     26 3    278

User · Answer

I did some work on this back when I was a researcher under Michael Stonebraker - you know  the professor who came up with Ingres  PostgreSQL  etc   We realized that the fastest way was to first do a bounding box because it s SUPER fast  If it s outside the bounding box  it s outside  Otherwise  you do the harder work     If you want a great algorithm  look to the open source project PostgreSQL source code for the geo work     I want to point out  we never got any insight into right vs left handedness  also expressible as an  inside  vs  outside  problem       UPDATE  BKB s link provided a good number of reasonable algorithms  I was working on Earth Science problems and therefore needed a solution that works in latitude longitude  and it has the peculiar problem of handedness - is the area inside the smaller area or the bigger area  The answer is that the  direction  of the verticies matters - it s either left-handed or right handed and in this way you can indicate either area as  inside  any given polygon  As such  my work used solution three enumerated on that page    In addition  my work used separate functions for  on the line  tests      Since someone asked  we figured out that bounding box tests were best when the number of verticies went beyond some number - do a very quick test before doing the longer test if necessary    A bounding box is created by simply taking the largest x  smallest x  largest y and smallest y and putting them together to make four points of a box     Another tip for those that follow  we did all our more sophisticated and  light-dimming  computing in a grid space all in positive points on a plane and then re-projected back into  real  longitude latitude  thus avoiding possible errors of wrapping around when one crossed line 180 of longitude and when handling polar regions  Worked great

User · Answer

The Eric Haines article cited by bobobobo is really excellent  Particularly interesting are the tables comparing performance of the algorithms  the angle summation method is really bad compared to the others  Also interesting is that optimisations like using a lookup grid to further subdivide the polygon into  in  and  out  sectors can make the test incredibly fast even on polygons with   1000 sides   Anyway  it s early days but my vote goes to the  crossings  method  which is pretty much what Mecki describes I think  However I found it most succintly described and codified by David Bourke  I love that there is no real trigonometry required  and it works for convex and concave  and it performs reasonably well as the number of sides increases   By the way  here s one of the performance tables from the Eric Haines  article for interest  testing on random polygons                          number of edges per polygon                          3       4      10      100    1000 MacMartin               2 9     3 2     5 9     50 6    485 Crossings               3 1     3 4     6 8     60 0    624 Triangle Fan edge sort  1 1     1 8     6 5     77 6    787 Triangle Fan            1 2     2 1     7 3     85 4    865 Barycentric             2 1     3 8    13 8    160 7   1665 Angle Summation        56 2    70 4   153 6   1403 8  14693  Grid  100x100           1 5     1 5     1 6      2 1      9 8 Grid  20x20             1 7     1 7     1 9      5 7     42 2 Bins  100               1 8     1 9     2 7     15 1    117 Bins  20                2 1     2 2     3 7     26 3    278

User · Answer

Really like the solution posted by Nirg and edited by bobobobo  I just made it javascript friendly and a little more legible for my use   function insidePoly poly  pointx  pointy        var i  j      var inside   false      for  i   0  j   poly length - 1  i  lt  poly length  j   i              if   poly i  y  gt  pointy      poly j  y  gt  pointy    amp  amp   pointx  lt   poly j  x-poly i  x     pointy-poly i  y     poly j  y-poly i  y    poly i  x    inside    inside            return inside

User · Answer

I ve made a Python implementation of nirg s  c   code   Inputs   bounding points  nodes that make up the polygon  bounding box positions  candidate points to filter   In my implementation created from the bounding box    The inputs are lists of tuples in the format    xcord  ycord           Returns   All the points that are inside the polygon     def polygon ray casting self  bounding points  bounding box positions         Arrays containing the x- and y-coordinates of the polygon s vertices      vertx    point 0  for point in bounding points      verty    point 1  for point in bounding points        Number of vertices in the polygon     nvert   len bounding points        Points that are inside     points inside             For every candidate position within the bounding box     for idx  pos in enumerate bounding box positions           testx  testy    pos 0   pos 1           c   0         for i in range 0  nvert               j   i - 1 if i    0 else nvert - 1             if    verty i   gt  testy       verty j   gt  testy     and                      testx  lt   vertx j  - vertx i      testy - verty i      verty j  - verty i     vertx i                      c    1           If odd  that means that we are inside the polygon         if c   2    1               points inside append pos        return points inside   Again  the idea is taken from here

User · Answer

Here is a C  version of the answer given by nirg  which comes from this RPI professor  Note that use of the code from that RPI source requires attribution   A bounding box check has been added at the top  However  as James Brown points out  the main code is almost as fast as the bounding box check itself  so the bounding box check can actually slow the overall operation  in the case that most of the points you are checking are inside the bounding box  So you could leave the bounding box check out  or an alternative would be to precompute the bounding boxes of your polygons if they don t change shape too often   public bool IsPointInPolygon  Point p  Point   polygon         double minX   polygon  0   X      double maxX   polygon  0   X      double minY   polygon  0   Y      double maxY   polygon  0   Y      for   int i   1   i  lt  polygon Length   i                   Point q   polygon  i            minX   Math Min  q X  minX            maxX   Math Max  q X  maxX            minY   Math Min  q Y  minY            maxY   Math Max  q Y  maxY               if   p X  lt  minX    p X  gt  maxX    p Y  lt  minY    p Y  gt  maxY                 return false                https   wrf ecse rpi edu Research Short Notes pnpoly html     bool inside   false      for   int i   0  j   polygon Length - 1   i  lt  polygon Length   j   i                   if     polygon  i   Y  gt  p Y        polygon  j   Y  gt  p Y    amp  amp               p X  lt    polygon  j   X - polygon  i   X       p Y - polygon  i   Y       polygon  j   Y - polygon  i   Y     polygon  i   X                         inside    inside                       return inside

User · Answer

Here is a JavaScript variant of the answer by M  Katz based on Nirg s approach   function pointIsInPoly p  polygon        var isInside   false      var minX   polygon 0  x  maxX   polygon 0  x      var minY   polygon 0  y  maxY   polygon 0  y      for  var n   1  n  lt  polygon length  n              var q   polygon n           minX   Math min q x  minX           maxX   Math max q x  maxX           minY   Math min q y  minY           maxY   Math max q y  maxY              if  p x  lt  minX    p x  gt  maxX    p y  lt  minY    p y  gt  maxY            return false             var i   0  j   polygon length - 1      for  i  j  i  lt  polygon length  j   i              if    polygon i  y  gt  p y      polygon j  y  gt  p y   amp  amp                  p x  lt   polygon j  x - polygon i  x     p y - polygon i  y     polygon j  y - polygon i  y    polygon i  x                 isInside    isInside                       return isInside

User · Answer

Here is golang version of  nirg answer  inspired by C  code by   m-katz   func isPointInPolygon polygon   point  testp point  bool       minX    polygon 0  X     maxX    polygon 0  X     minY    polygon 0  Y     maxY    polygon 0  Y      for    p    range polygon           minX   min p X  minX          maxX   max p X  maxX          minY   min p Y  minY          maxY   max p Y  maxY             if testp X  lt  minX    testp X  gt  maxX    testp Y  lt  minY    testp Y  gt  maxY           return false            inside    false     j    len polygon  - 1     for i    0  i  lt  len polygon   i             if  polygon i  Y  gt  testp Y      polygon j  Y  gt  testp Y   amp  amp  testp X  lt   polygon j  X-polygon i  X   testp Y-polygon i  Y   polygon j  Y-polygon i  Y  polygon i  X               inside    inside                   j   i            return inside

User · Answer

If you re using Google Map SDK and want to check if a point is inside a polygon  you can try to use GMSGeometryContainsLocation  It works great   Here is how that works   if GMSGeometryContainsLocation point  polygon  true        print  Inside this polygon      else       print  outside this polygon       Here is the reference  https   developers google com maps documentation ios-sdk reference group   geometry utils gaba958d3776d49213404af249419d0ffd

User · Answer

The trivial solution would be to divide the polygon to triangles and hit test the triangles as explained here    If your polygon is CONVEX there might be a better approach though  Look at the polygon as a collection of infinite lines  Each line dividing space into two  for every point it s easy to say if its on the one side or the other side of the line  If a point is on the same side of all lines then it is inside the polygon

User · Answer

I did some work on this back when I was a researcher under Michael Stonebraker - you know  the professor who came up with Ingres  PostgreSQL  etc   We realized that the fastest way was to first do a bounding box because it s SUPER fast  If it s outside the bounding box  it s outside  Otherwise  you do the harder work     If you want a great algorithm  look to the open source project PostgreSQL source code for the geo work     I want to point out  we never got any insight into right vs left handedness  also expressible as an  inside  vs  outside  problem       UPDATE  BKB s link provided a good number of reasonable algorithms  I was working on Earth Science problems and therefore needed a solution that works in latitude longitude  and it has the peculiar problem of handedness - is the area inside the smaller area or the bigger area  The answer is that the  direction  of the verticies matters - it s either left-handed or right handed and in this way you can indicate either area as  inside  any given polygon  As such  my work used solution three enumerated on that page    In addition  my work used separate functions for  on the line  tests      Since someone asked  we figured out that bounding box tests were best when the number of verticies went beyond some number - do a very quick test before doing the longer test if necessary    A bounding box is created by simply taking the largest x  smallest x  largest y and smallest y and putting them together to make four points of a box     Another tip for those that follow  we did all our more sophisticated and  light-dimming  computing in a grid space all in positive points on a plane and then re-projected back into  real  longitude latitude  thus avoiding possible errors of wrapping around when one crossed line 180 of longitude and when handling polar regions  Worked great

[performance] How can I determine whether a 2D Point is within a Polygon?

Examples related to performance

Examples related to graphics

Examples related to collision-detection

Examples related to polygon

Examples related to point-in-polygon