[R] points with-in boundaries of a map

[Frede Aakmann Tøgersen]

Hi guys

Just to follow up on Ted's comments.

See http://erich.realtimerendering.com/ptinpoly/ for other points in polygon algorithms. Eric Haines has made some performance evaluation of the methods. I quote here Eric:

The worst algorithm in the world for testing points is the angle summation method. It's simple to describe: sum the signed angles formed at the point by each edge's endpoints. If the sum is near zero, the point is outside; if not, it's inside (Figure 2).

The point.in.polygon function in package sp is referencing:

References:

     Uses the C function InPoly().  InPoly is Copyright (c) 1998 by
     Joseph O'Rourke.  It may be freely redistributed in its entirety
     provided that this copyright notice is not removed.

(see e.g. ftp://ftp.ecs.umass.edu/pub/fshill/ece660/triangulate/inpoly.c)

It seems that this corresponds to the edge/ray crossing method in Eric's wording. The performance is between the best as shown by Eric.

I know there are other implementations in R in other packages but I do not have the full overview of all methods.


Yours sincerely / Med venlig hilsen


Frede Aakmann Tøgersen
Specialist, M.Sc., Ph.D.
Plant Performance & Modeling

Technology & Service Solutions
T +45 9730 5135
M +45 2547 6050
frtog at vestas.com
http://www.vestas.com

Company reg. name: Vestas Wind Systems A/S
This e-mail is subject to our e-mail disclaimer statement.
Please refer to www.vestas.com/legal/notice
If you have received this e-mail in error please contact the sender. 


> -----Original Message-----
> From: r-help-bounces at r-project.org [mailto:r-help-bounces at r-project.org]
> On Behalf Of Ted Harding
> Sent: 24. marts 2014 09:06
> To: r-help at r-project.org
> Subject: Re: [R] points with-in boundaries of a map
> 
> Apologies (red-faced)!! In my reply below I wrote "pi" and "-pi" where
> it should have been "2*pi" and "-2*pi". See at [***] below.
> Sorry for the noise,
> Ted.
> 
> On 23-Mar-2014 22:50:50 Jim Lemon wrote:
> > On 03/23/2014 10:29 PM, eliza botto wrote:
> >> Thankyou very much jim. it worked! but regarding second part of my
> >> question, isn't there a way to read the coordinates of intersecting
> >> lines with the premises of the map?
> >
> > Hi Eliza,
> > I think you want the "locator" function, which will return the
> > coordinates to the accuracy that you can click on a point in the plot.
> >
> > Jim
> 
> There is a possible analytical approach to this. If the boundary of
> a simple closed region is given as a series of straight lines which
> join successive points as one proceeds continuously round the boundary
> of theregion, and one has the data of the (x,y) coordinates of the points
> in that order (with the last point the same as the first), then one
> can proceed as follows:
> 
> Let the points be P1=(x1,y1), P2=(x2,y2), ... , PN=(xN,yN)=P1
> in the order specified above.
> 
> Since the grid lines have been drawn at specified intervals, you
> can work through every point (x0,y0) which is an intersection.
> 
> Let (x0,y0) be a point of intersection of the grid of lines. Now you
> know the coordinates of (x0,y0) already, so the question is whether
> this point is inside or outside the region.
> 
> Consider a line jpoining (x0,y0) to (x1,y1). Now work out the angle
> through which the line rotates when it is moved so that it joins
> (x0,y0) to (x2,y2); say this is phi2 (clockwise positive, anticlockise
> negative). Similarly work out phi3, the angle through which the line
> next rotates when it is further moved so that it joins (x0,y0) to (x2,y2);
> and so on.
> 
> Now add up phi2 + phi3 + ... + phiN
> 
> If the point (x0,y0) is inside the region, and you have proceeded
> consecutively along the boundary, then this sum of angles will be
> [***]pi or -pi. [***Should be] 2*pi or -2*pi.
> If (x0,y0) is outside the region, then this sum will be zero.
> 
> So you can work through all the intersections of the grid lines,
> and for each intersection you can determine whether it is inside
> or outside; and, if it is inside, you already know its coordinates.
> 
> It can get more complicated if the region is not simply-connected.
> E.g. if you do not want to count points (x0,y0) which are within
> the boundary coastline but also are within the boundary of an
> inland lake; or, further, you do want to count points which are
> on an island in the lake; and so on.
> 
> The essential for following a procedure of this kind is that you
> can extract from the data from which the map is drawn the coordinates
> of a series of points which are in consecutive order as one proceeds
> along the boundar of a region. Not all geographic data have the
> coordinates in such an order -- one can find datasets such that the
> boundary is drawn as a set of separate partial boundaries which
> are in no particular order as a whole; and in some datasets the
> different separate parts of the boundary do not exactly match up
> at the points where they should exactly join.
> 
> Hoping this helps,
> Ted.
> 
> -------------------------------------------------
> E-Mail: (Ted Harding) <Ted.Harding at wlandres.net>
> Date: 23-Mar-2014  Time: 23:47:15
> This message was sent by XFMail
> 
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-
> guide.html
> and provide commented, minimal, self-contained, reproducible code.
> 
> -------------------------------------------------
> E-Mail: (Ted Harding) <Ted.Harding at wlandres.net>
> Date: 24-Mar-2014  Time: 08:06:23
> This message was sent by XFMail
> 
> ______________________________________________
> R-help at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/posting-
> guide.html
> and provide commented, minimal, self-contained, reproducible code.