[R] multidimensional point.in.polygon??

[baptiste auguie]

Hi,

Regarding your proposed algorithm (looks like it is indeed the correct
way to do it), there seem to be a somewhat similar Matlab
implementation,

http://www.mathworks.com/matlabcentral/fileexchange/10226-inhull

It should be possible to port this to R (you might want to check what
to do with the author's license, eventually). Also, you might have
better luck on this list if you provide a small example for people to
play with.

Best,

baptiste


2009/12/10 Keith Jewell <k.jewell at campden.co.uk>:
> Hi,
>
> Doing some more reading, I think the problem is easier because the hull is
> convex. Then an algorithm for testing points might be:
>
> a) Define the convex hull as a set of planes (simplexes).
>    [as returned by convhulln!!]
>
> b) Define one point, i, known to be interior
>    [e.g. mean of all the points defining the hull]
>
> c) If point x is
>    i) for every plane, on the same side as i; x is interior
>   ii) for every plane, on the same side as i or in the plane; x is in the
> surface
>  iii) else x is exterior
>
> So now I need to find the directions of points from multidimensional
> planes.Perhaps I can find the vectors of the perpendiculars from the points
> to the planes (possibly extended) and test for parallel/anti-parallel?
>
> I feel that I'm in the right direction because this uses the structure of a
> convex hull returned by convhulln. But, I still feel I'm re-inventing the
> wheel. Surely this has been done before? Isn't a (the?) major purpose of a
> convex hull to test other points for inclusion?
>
> Perhaps when I get the geometry sorted this will be so easy I'll understand
> why noone has pointed me to an existing R function, but currently I feel I
> and Baptiste are wandering in the dark :-(
>
> Any hints?
>
> Thanks in advance,
>
> Keith Jewell
> -----------------------------------------------------------------
> "baptiste auguie" <baptiste.auguie at googlemail.com> wrote in message
> news:de4e29f50912040550m71fbffafnfa1ed6e0f4451604 at mail.gmail.com...
> Hi,
>
> Yet another one of my very naive ideas on the subject: maybe you can
> first evaluate the circumscribed and inscribed spheres of the base set
> of points (maximum and minimum of their distances to the center of
> gravity). Any points within a distance smaller than the infimum is
> good, any point further than the supremum is not good. This should be
> faster than the calculation of a convex hull for each point. Of course
> the usefulness of this first test really depends on how aspherical is
> your base convex hull.
>
> I do hope to read a real answer from someone who knows this stuff!
>
> HTH,
>
> baptiste
>
>
> 2009/12/4 Keith Jewell <k.jewell at campden.co.uk>:
>> Hi,
>>
>> I seek to identify those points in/outside a multidimensional convex hull
>> (geometry::convhulln). Any suggestions?
>>
>> Background just in case I'm going down a really wrong road:
>>
>> Given an observed data set with one dependent/observed variable (Y) and
>> multiple (3 to 10) independent/design variables (X1, X2, ...) I want to
>> increase the number of points by interpolating. I'm using expand.grid(X)
>> to
>> generate the X points and locfit::predict.locfit to interpolate the Y
>> values. No problem so far.
>>
>> BUT my observed X data set is very far from rectangular, so the set of
>> points produced by expand.grid includes many "extrapolations" which I'd
>> want to remove. I'm aware of the problems of defining extrapolation in
>> multiple dimensions and am minded to define it as "outside the convex
>> hull",
>> hence my question.
>>
>> In searching r-project.org I came across a thread in which baptiste auguie
>> said "one general way to do this would be to compute the convex hull
>> (?chull) of the augmented set of points and test if the point belongs to
>> it"; an approach I'd considered generalising to multiple points thus
>> (pseudo
>> R code)...
>> ----------------
>> baseHull <- convhulln(baseSet)
>> augHull <- convhulln(augSet)
>> while (augHull != baseHull)
>> { augSet <- augSet [-(augHull !%in% baseHull)]
>> augHull <- convhulln(augSet)
>> }
>> --------------------
>> ... but this has that horrible loop including a convhulln!
>>
>> In the (real, typical) test data set I'm using for development baseSet is
>> 5
>> columns by 2637 rows while baseHull has only 42 distinct points. If
>> augHull
>> has a similarly simple hull, then each time round the loop will remove
>> only
>> a few dozen points; I need to remove many thousands.
>>
>> And (in my naivete) I think there must be a better way of testing for a
>> point inside a polygon, I'd have thought convhulln must need to do that
>> often!
>>
>> Thanks in advance for any pointers,
>>
>> Keith Jewell
>>
>> ______________________________________________
>> 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.
>>
>
> ______________________________________________
> 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.
>