[R] multidimensional point.in.polygon??

[Keith Jewell]

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