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