spacer2 1_1 1_2
 The MP2K Update!
Front Cover
What's New
Sample Data
MapPoint 2013
Press Releases
MapPoint Forums
Link to MP2Kmag
Wish List
MapPoint Trial
 Earlier Content
Past News Items
Past What's New Announcements

MapPoint 2013

Programming MapPoint in .NET

MapPoint Book

  Spatial Community
SVG Tutorials

Map Visitors


Determing Whether A Point Is Located Inside Polygon

Wilfried Mestdagh wrote this article on determing whether a vehicle is located inside or outside a convex polygon. "Simplify the polygon by make triangles from it one by one, until we have a triangle where the point is inside. At the end we only have to verify if the point is in the last triangle."

Download code for this article.

This article explains a method to calculate if a position is in or outside a convex polygon. It does not make use of floating point numbers to optimize for speed as much as possible. To transform Latitude / Longitude pairs into X/Y coordiantes, just multiply them with a given factor, for example 100000. 1/100000 of a degree gives precision of around 1 meter which is already better than any GPS receiver.
If you just want to download the complete project, included with demo executable and source code then click here.
To make the calculations easy we will reduce the polygon to triangles by replacing each time two successive sides by a new one, provided that the triangle formed by the two polygon sides and the new side does not contain the point.
Simplify the polygon by make triangles from it one by one, until we have a triangle where the point is inside.
At the end we only have to verify if the point is in the last triangle.
The last triangle.
So we reduce the whole problem to a simple problem if a certain triangle a certain point has in itself. Now, to move the triangle and also the point in such a way that the point is on the origin of the coordinate axis (0,0) we again simplify the calculations.
Moving the polygon to the origin 0,0 of coordinates.
We search the sides intercepting the Y axis. If we don't find them then the zero point is certainly not in the triangle. The 2 intercept points have to each be on another side of the X axis or on the X axis itself. The calculation of a straight line going through the points X1, Y1 and X2, Y2 is:
z (x) = (y2 - y1) / (x2 - x1) x - (y2 - y1) / (x2 - x1) + y1
Now we have to see if the side is intercepting the Y axis. If x1 = x2 then this cannot be, so we can drop the case. To find the intercept point of a straight line with the Y axis we find to compute z(0):
z(0) = (y1 - y2) / (x2 - x1) + y1
This intercept point is on the side and not on the straight line past the side if sng(x1 <> sng(x2).
Finally we have to find out if the side is intercepting the Y axis above or below the X axis. We call the intercept point z(0) (see above). So we have to find the sign of x(0). So z(0) >= 0.
(y1 - y2) / (x2 - x1) * x1 + y1 >= 0
If x2 < x2, then x2 - x1 > 0 and then:
(y1 - y2) * x1 >= y1( - y2)  [E1]
If x1 > x2, then x2 - x1 < 0, and then:
(y1 - y2) * x1 <= y1(x1 - x2) [E2]
So the intercept point is above the X axis if E1 or E2 is true.
Below is the complete code written in Delphi. You can translate it into the programming language of your choice and if you do so please post in the discussion thread for this article.

Discuss this story in the forum.

Author: Wilfried Mestdagh
Email: wilfried(AT)
Wilfried Mestdagh works as software engineer at the company Sonal in Mortsel, Belgium. His main work is writing software for fleet management and onboard computers. Fleet management is mainly written in Delphi and C# while the onboard computers are mostly programmed in C. His department started years ago for specializing in tracking and tracing security and dangerous transport vehicles, but it is grown to satisfy a very wide of vehicle / truck fleet customers.

MP2Kmag Internet

 Recent Discussion
Browse GIS books and periodicals
Find a MapPoint Partner or Consultant
Real Estate Thornbrook Subdivision

Want Your Site To Appear Here?

   © 1999-2012 MP2K. Questions and comments to:
  Microsoft and MapPoint 2002/2004/2006/2009/2010/2011/2013 are either trademarks or registered trademarks of Microsoft.