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.jew...@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.aug...@googlemail.com> wrote in message > news:de4e29f50912040550m71fbffafnfa1ed6e0f4451...@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.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. > ______________________________________________ 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.