spacer1
spacer2 1_1 1_2
2_1
 Subscribe
 The MP2K Update!
 
 
 
 Magazine
Front Cover
What's New
Articles
News
Sample Data
Gallery
Advertise
About
 Features
MapPoint 2013
Press Releases
MapPoint Forums
Companies
Link to MP2Kmag
Wish List
MapPoint Trial
Authors
 Earlier Content
Past News Items
Past What's New Announcements
 Sponsors
 Order

MapPoint 2013

Programming MapPoint in .NET

MapPoint Book

  Spatial Community
SVG Tutorials
MapPoint

Map Visitors

  ARTICLES  


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)mestdagh.biz
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.



Google
 
MP2Kmag Internet


 Recent Discussion
-Mappoint or powermap buying?
-Mappoint or 365 powermap
-Problem Mapping and Splitting Territories across the U.S and Canada
-Problem Mapping and Splitting Territories across the U.S and Canada
-where to find the Maps downloader for Bing
-Maps Downloader For Bing Map
-Pushpins can't be set in AutoRoute 2013 and MapPoint 2013
-How to extract data based on DEM elevation contour lines generated
-MapPoint discontinued! - any alternatives?
-MapPoint discontinued by 12-31-14
-Database developer new to MapPoint and this forum
-Mapoint 2013 North American cannot search for Canadian Address
-Utility File: Drawing Circles Around LatLons...xls appears different recently...Windows 8.1 related?
-MPExporter v1.0 Released!
-Showing many Point-to-Point lines between cities
 Resources
Browse GIS books and periodicals
Find a MapPoint Partner or Consultant
Real Estate Columbia, MO Real Estate


Want Your Site To Appear Here?

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