Click here to Skip to main content
Click here to Skip to main content

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

, 29 Jul 2013 CPOL
Rate this:
Please Sign up or sign in to vote.
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

Ravimal Bandara
Student University of Moratuwa
Sri Lanka Sri Lanka
Postgraduate research student specializing in video content analysis. Interested in Image processing, HCI and Digital music production. Computer and technology enthusiast. I love coding and sharing my knowledge.
Follow on   Twitter

Comments and Discussions

 
GeneralMy vote of 5 PinmemberGalatei30-Jul-13 11:10 
GeneralMy vote of 1 PinmemberGalatei27-Jul-13 3:48 
GeneralRe: My vote of 1 PinprofessionalRavimal Bandara27-Jul-13 5:47 
GeneralRe: My vote of 1 PinmemberGalatei28-Jul-13 11:07 
GeneralRe: My vote of 1 PinprofessionalRavimal Bandara28-Jul-13 18:00 
GeneralRe: My vote of 1 PinmemberGalatei29-Jul-13 11:34 
GeneralRe: My vote of 1 PinprofessionalRavimal Bandara29-Jul-13 22:27 
GeneralMy vote of 5 PinprofessionalAmir Mohammad Nasrollahi26-Jul-13 21:33 

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

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

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.141216.1 | Last Updated 30 Jul 2013
Article Copyright 2013 by Ravimal Bandara
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid