Welcome to MapForums!

Register, sign in, or use Facebook Connect above to join in and participate in the forum.

When you are signed in, this message, the ads in this row, and the red-underlined link ads all go away.

Subscribe to receive our newsletter.
Subscribe Unsubscribe
Results 1 to 7 of 7

Determing Whether A Point Is Located Inside Polygon

This is a discussion on Determing Whether A Point Is Located Inside Polygon within the MP2K Magazine Articles forums, part of the Map Forums category; Wilfried Mestdagh wrote this article on determing whether a vehicle is located inside or outside a convex polygon. "Simplify the ...

  1. #1
    Eric Frost's Avatar
    Eric Frost is offline Administrator Black Belt
    Join Date
    Jul 1992
    Posts
    5,088
    Blog Entries
    4

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

    Article at -- Determing Whether A Point Is Located Inside Polygon

  2. #2
    adirat is offline Junior Member Yellow Belt
    Join Date
    Sep 2005
    Posts
    16

    Re: Determing Whether A Point Is Located Inside Polygon

    Lot of polygon in GIS ARE NOT convex , so , what do you do in this case ?

  3. #3
    Eric Frost's Avatar
    Eric Frost is offline Administrator Black Belt
    Join Date
    Jul 1992
    Posts
    5,088
    Blog Entries
    4

    Re: Determing Whether A Point Is Located Inside Polygon

    Personally I would be tempted to use a GIS engine such as MapInfo's MapX in the background instead of reinventing the wheel. Last time I checked, MapX starting prices were not very cheap however, maybe you can find an open source or cheaper engine to run in the background. (UMN MapServer?).

    Eric

  4. #4
    Winwaed's Avatar
    Winwaed is offline Mapping-Tools.com Black Belt
    Join Date
    Feb 2004
    Location
    Irving,Texas
    Posts
    1,827
    Blog Entries
    55

    Re: Determing Whether A Point Is Located Inside Polygon

    There is also a "ray" algorithm, where you project a line from your point to infinity. Count the number of times the line crosses the boundary of the polygon. If it is odd, then the point is in the polygon.

    For a sphere then you probably want to project along a line of latitude or longitude, and make assumptions about the shape not including the international date line, north pole, or something similar (eg. project to 180deg).

    Sedgwick's "Algorithms" has a nice optimisation of the above algorithm (for a plane).

    I'm probably going to be coding it up in C# for MapPoint in the next few months, so if Eric is interested then I might be persuaded to write an article about it...

    Richard
    Winwaed Software Technology LLC
    http://www.winwaed.com
    See http://www.mapping-tools.com for MapPoint Tools

  5. #5
    Eric Frost's Avatar
    Eric Frost is offline Administrator Black Belt
    Join Date
    Jul 1992
    Posts
    5,088
    Blog Entries
    4

    Re: Determing Whether A Point Is Located Inside Polygon

    Sorry I forgot to reply earlier.

    This actually came up at a job site a couple weeks ago, a person started to describe it so I said "yes of course the ray algorithm" having read your post. I actually have C code for it although I won't pretend to understand how it all works yet..

    To answer your question - yes I think it would be a terrific topic for an article, very practical for MapPoint developers.

    Eric

  6. #6
    Winwaed's Avatar
    Winwaed is offline Mapping-Tools.com Black Belt
    Join Date
    Feb 2004
    Location
    Irving,Texas
    Posts
    1,827
    Blog Entries
    55

    Re: Determing Whether A Point Is Located Inside Polygon

    I'm getting close to implementing something.
    I have found a reference to extending Wilfried's to work with concave polygons.
    Basically, you have to check all triangles and count the number that contain the point. If the number is odd, then the point is in the shape.

    It is from a review of different strategies and speeds in Graphics Gems IV.
    Chapter 1.4 "Point in Polygon Strategies" pp 24-46. This further quotes Berlin 1985 "Efficiency considerations in image synthesis", SIGGRAPH '85 State of the Art in Image Synthesis seminar notes, July 1985.

    It looks like the triangle method using pre-stored half planes is the fastest option for polygons with small numbers of vertices.

    There's an interesting angle method (ch 1.3 in Gems IV) which doesn't even involve trigonometry because it can be optimized to simple quadrant classification. The benchmarks suggest it is slightly slower than the "ray" ("Crossings" they call it) algorithm, but should be pretty close with a good optimizing compiler.

    Of course, all these standard discussions are for 2d Euclidean Space. We need something for a sphere. A polygon on a sphere has two "sides" - as I see it, the only difference between the inside and the outside is the size. The area of the inside is smaller than the area of outside.
    I think we'll need trigonometry for the spherical coordinates.

    I'll see what I come up with. C# and on a sphere. I'll be using my own objects, rather than MapPoint Locations.


    Richard
    Winwaed Software Technology LLC
    http://www.winwaed.com
    See http://www.mapping-tools.com for MapPoint Tools

  7. #7
    Eric Frost's Avatar
    Eric Frost is offline Administrator Black Belt
    Join Date
    Jul 1992
    Posts
    5,088
    Blog Entries
    4

    Re: Determing Whether A Point Is Located Inside Polygon

    I know at least from experience, a lot of times lat/lon are converted to UTM zones for calculations, that might be an approach.

    Eric

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Similar Threads

  1. Determing the Time Zone in MapPoint
    By Anonymous in forum MP2K Magazine Articles
    Replies: 1
    Last Post: 09-21-2009, 01:51 PM
  2. How can I get the territory code that a pushipin is located
    By paf33 in forum MapPoint Desktop Discussion
    Replies: 7
    Last Post: 06-08-2006, 04:45 AM
  3. Which Territory is a Pushpin located?
    By johnweidauer in forum MapPoint Desktop Discussion
    Replies: 1
    Last Post: 07-31-2005, 10:46 AM
  4. How to programatically tell if an address is located?
    By jharbaugh in forum MapPoint Desktop Discussion
    Replies: 5
    Last Post: 01-06-2005, 09:26 PM
  5. gettign teh area inside a polygon or territory
    By Anonymous in forum MapPoint Desktop Discussion
    Replies: 1
    Last Post: 10-18-2003, 05:21 PM

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81