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
-AutoColor
-SolidThinking Inspire v2016.1.5559 x64-BEAN (17/8)
-Auto FX PhotoGraphic Edges Ultimate Bundle Gen2 v9.6.0 (17/8)
-Mentor Graphics FloEFD 14.2-SSQ (17/8)
-Dlubal RFEM 5.06 (x64) Multilanguage (17/8)
-Bluebeam Revu eXtreme 2018.1 v18.x Multilingual (17/8)
-Autodesk Maya 2018.4 (17/8)
-Adobe Bridge CC 2018 (v8.1) x86-x64 Multilingual Update 2 (17/8)
-Simufact.Welding 4.0.1 (17/8)
-ANSYS Discovery Enterprise 19.1.1 (17/8)
-Aurora SPARK3D v2018
-ANSYS Electromagnetics Suite 17.1 (17/8)
-Solidthinking Inspire v2018.3.0.10526 Multilingual (x64) (17/8)
-Adobe Acrobat Pro DC 2018.011.20058 Multilingual (17/8)
-ANSYS Electromagnetics Suite 17.0 (x64) (17/8)
-GibbsCAM 12.0.29.0 (x64) Multilingual (17/8)
-Autodesk Autocad Mechanical 2019.1 by m0nkrus (17/8)
-Adobe Bridge CC 2018 v8.1 (x86/x64) Update 2 Multilingual (17/8)
-Autodesk AutoCAD Electrical 2019.1 (17/8)
-DS V5R22 CATIA-DELMIA-ENOVIA last hotfixes for all SP (17/8)
-VMware Fusion Pro 10.1.3 Build 9472307 (17/8)
-MAGIX Fotostory easy 2.0.0.35 Germany + English (17/8)
-Ds Simulia Abaqus v6.14-4 (17/8)
-Paragon Drive Copy 15 Professional 10.1.25.779 (x86/x64) (17/8)
-ARCHICAD 21 Build 3005 with Addons
 Resources
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: website@mp2kmag.com
  Microsoft and MapPoint 2002/2004/2006/2009/2010/2011/2013 are either trademarks or registered trademarks of Microsoft.