R help - Dec 2009 - multidimensional point.in.polygon??

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

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