Click here to Skip to main content
14,774,409 members
Articles » General Programming » Algorithms & Recipes » Algorithms
Tip/Trick
Posted 26 Jul 2013

Tagged as

Stats

53K views
2.7K downloads
19 bookmarked

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 2013CPOL
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 

 //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.

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. 

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)

Share

About the Author


Comments and Discussions

 
GeneralThanks Pin
Member 1058266418-Apr-16 2:20
MemberMember 1058266418-Apr-16 2:20 
GeneralRe: Thanks Pin
Ravimal Bandara23-Apr-16 8:44
MemberRavimal Bandara23-Apr-16 8:44 
QuestionNice Article but not seem to work in few cases Pin
Learning WIX7-Jan-15 20:46
MemberLearning WIX7-Jan-15 20:46 
SuggestionRe: Nice Article but not seem to work in few cases Pin
Ravimal Bandara8-Jan-15 6:53
MemberRavimal Bandara8-Jan-15 6:53 
GeneralRe: Nice Article but not seem to work in few cases Pin
Learning WIX8-Jan-15 17:03
MemberLearning WIX8-Jan-15 17:03 
AnswerRe: Nice Article but not seem to work in few cases Pin
Ravimal Bandara9-Jan-15 5:42
MemberRavimal Bandara9-Jan-15 5:42 
I guess the problem is with the last point of the polygon. The final point should be the first point. Therefore at the end the polygon vector will include 4 points where the first and last points are the same. My implementation of the algorithm does not check whether the given points form a closed polygon or not hence the closing point is mandatory. You may extend the algorithm to self close the polygon or simply add the first point at the end as well.
GeneralMy vote of 5 Pin
Galatei30-Jul-13 11:10
MemberGalatei30-Jul-13 11:10 
GeneralMy vote of 1 Pin
Galatei27-Jul-13 3:48
MemberGalatei27-Jul-13 3:48 
GeneralRe: My vote of 1 Pin
Ravimal Bandara27-Jul-13 5:47
MemberRavimal Bandara27-Jul-13 5:47 
GeneralRe: My vote of 1 Pin
Galatei28-Jul-13 11:07
MemberGalatei28-Jul-13 11:07 
GeneralRe: My vote of 1 Pin
Ravimal Bandara28-Jul-13 18:00
MemberRavimal Bandara28-Jul-13 18:00 
GeneralRe: My vote of 1 Pin
Galatei29-Jul-13 11:34
MemberGalatei29-Jul-13 11:34 
GeneralRe: My vote of 1 Pin
Ravimal Bandara29-Jul-13 22:27
MemberRavimal Bandara29-Jul-13 22:27 
GeneralMy vote of 5 Pin
Amir Mohammad Nasrollahi26-Jul-13 21:33
professionalAmir Mohammad Nasrollahi26-Jul-13 21: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.