Click here to Skip to main content
16,018,442 members
Articles / General Programming / Algorithms
Tip/Trick

Check if a Point is Inside the Polygon Using Ray-Casting Algorithm

Rate me:
Please Sign up or sign in to vote.
4.79/5 (11 votes)
29 Jul 2013CPOL2 min read 67K   2.8K   19   14
An implementation of ray-casting algorithm to check if a given point is inside or outside the polygon.

Introduction 

There are many applications that require to know if a given point is inside or outside the polygon. For an example, if we need to select a polygon by clicking on it then we will need a way to know whether the user click inside or outside the polygon. Ray casting algorithm is one popular way to do it. In this trick I included an implementation of raycasting algorithm for a polygon selection in a canvas.

Background  

In this section I briefly explain how the ray casting algorithm can be used for check whether a point is inside or outside the polygon. When a point is given then we virtually draw a line from a point far away outside from the polygon to the given point. then we calculate the number of intersection of the virtual line with the edges of the polygon. if the number of intersections is odd then according to the ray casting theory we can conclude that the point is inside the polygon. Otherwise the point is outside the polygon. You can find more about ray casting algorithm from here.

Using the code

In this code there are two main functionalities. One is drawing of a polygon inside a usercontrol and second is select of deselect the polygon. I am not going to explain the drawing part of the polygon since the every line in the code is explained with a comment.   

The following code is used for check the intersections 

C#
 //check the intersections
if (((polyK.Y > currentPoint.Y) != (polyJ.Y > currentPoint.Y)) &&
     (currentPoint.X < (polyJ.X - polyK.X) * (currentPoint.Y - polyK.Y) / (polyJ.Y - polyK.Y) + polyK.X)) 

polyK and polyJ are adjacent points from the polygon.   

According to the algorithm all what we need to know is whether the number of intersections is odd or even hence we use a flag that switches between odd and even as in the following code line.

C#
oddNodes = !oddNodes; 

After testing the each and every edge of the polygon for the intersection we can check whether the number of intersection is odd or even. If it is odd then the point should be inside the polygon so we flag it as selected as in the following code. 

C#
if (oddNodes)
{
   //mouse point is inside the polygon
   isSelected = true;
}
else //if even number of intersections
{
   //mouse point is outside the polygon so deselect the polygon
   isSelected = false;
}

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



Comments and Discussions

 
GeneralThanks Pin
Member 1058266418-Apr-16 1:20
Member 1058266418-Apr-16 1:20 
GeneralRe: Thanks Pin
Ravimal Bandara23-Apr-16 7:44
Ravimal Bandara23-Apr-16 7:44 
QuestionNice Article but not seem to work in few cases Pin
Learning WIX7-Jan-15 19:46
Learning WIX7-Jan-15 19:46 
SuggestionRe: Nice Article but not seem to work in few cases Pin
Ravimal Bandara8-Jan-15 5:53
Ravimal Bandara8-Jan-15 5:53 
GeneralRe: Nice Article but not seem to work in few cases Pin
Learning WIX8-Jan-15 16:03
Learning WIX8-Jan-15 16:03 
AnswerRe: Nice Article but not seem to work in few cases Pin
Ravimal Bandara9-Jan-15 4:42
Ravimal Bandara9-Jan-15 4:42 
GeneralMy vote of 5 Pin
Galatei30-Jul-13 10:10
Galatei30-Jul-13 10:10 
GeneralMy vote of 1 Pin
Galatei27-Jul-13 2:48
Galatei27-Jul-13 2:48 
GeneralRe: My vote of 1 Pin
Ravimal Bandara27-Jul-13 4:47
Ravimal Bandara27-Jul-13 4:47 
GeneralRe: My vote of 1 Pin
Galatei28-Jul-13 10:07
Galatei28-Jul-13 10:07 
GeneralRe: My vote of 1 Pin
Ravimal Bandara28-Jul-13 17:00
Ravimal Bandara28-Jul-13 17:00 
GeneralRe: My vote of 1 Pin
Galatei29-Jul-13 10:34
Galatei29-Jul-13 10:34 
GeneralRe: My vote of 1 Pin
Ravimal Bandara29-Jul-13 21:27
Ravimal Bandara29-Jul-13 21:27 
GeneralMy vote of 5 Pin
Amir Mohammad Nasrollahi26-Jul-13 20:33
professionalAmir Mohammad Nasrollahi26-Jul-13 20:33 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.