Re: [R] mutlidimensional in.convex.hull (was multidimensional point.in.polygon??)
2009/12/10 Charles C. Berry cbe...@tajo.ucsd.edu: [snipped] Many? set.seed(1234) ps - matrix(rnorm(4000),ncol=4) phull - convhulln(ps) xs - matrix(rnorm(1200),ncol=4) phull2 - convhulln(rbind(ps,xs)) nrp - nrow(ps) nrx - nrow(xs) outside - unique(phull2[phull2nrp])-nrp done - FALSE while(!done){ + phull3 - convhulln(rbind(ps,xs[-(outside),])) + also.outside - (1:nrx)[-outside][unique(phull3[phull3nrp])-nrp] + print(length(also.outside)) + outside - c(outside,also.outside) + done - length(also.outside)==0 + } [1] 3 [1] 0 phull2 was evaluated once, phull3 twice. Any point that is in the convex hull of rbind(ps,xs) is either in or outside the convex hull of ps. Right? So, just recursively eliminate points that are in the convex hull of the larger set. If I'm not mistaken this method is efficient only because the two point distributions are very similar (drawn from rnorm, so they look like two concentric balls). If one of the convex hulls is very distorted along one axis, say, I believe the method will involve many more iterations and in the limit will require computing a convex hull for each test point as Duncan suggested. Such a pathological of test points example might be, xs - matrix(0,ncol=4,nrow=100) xs[,1] - seq(1,100) Or did I completely miss something? (quite possible) Regarding the inhull Matlab code, I came to the opposite conclusion: it should be easily ported to R. 1) it is a very short piece of code (even more so if one disregards the various checks and handling of special cases), with no Matlab-specific objects (only integers, booleans, matrices and vectors). 2) The core of the program relies on the qhull library, and the same applies to R I think. 3) Matlab and R use very similar indexing for matrices and similar linear algebra in general. That said, I'm a bit short on time to give it a go myself. I think the open-source Octave could run this code too, so it might help in checking the code step-by-step. All the best, baptiste __ 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] mutlidimensional in.convex.hull (was multidimensional point.in.polygon??)
Hi All (especially Duncan and Baptiste), Summary (of lengthy bits below): I will have a convex hull in multiple (3 to 10) dimensions derived from many (thousands) of points by geometry::convhulln. I will need to categorise other 'test' points as inside/outside that convex hull . e.g. given: -- require(geometry) ps - matrix(rnorm(4000),ncol=4) # 'calibration' set phull - convhulln(ps) # convex hull xs - matrix(rnorm(1200),ncol=4)# 'test' set - How do I categorise each point (row) in xs as inside/outside(/on) phull??? There is tripack::in.convex.hull but that doesn't handle my dimensionality. Thanks to Duncan Murdoch for the suggestion (just a few lines down, previously made by Baptiste Auguie): of testing a single point thus: i) add the test point to the set of points defining the convex hull, ii) recalculate the convex hull iii) if the test point is part of the new convex hull, then it was outside the original BUT I have many (thousands) of test points, so this would involve very many convex hull calculations. My suggestion, immediately below, requires finding the signs of perpendicular distances from each test point to each multidimensional 'plane' defining the convex hull (NB: phull is a matrix in which each row defines such a 'plane'). Baptiste has found a Matlab implementation http://www.mathworks.com/matlabcentral/fileexchange/10226-inhull of (what looks like) my algorithm. I don't speak Matlab, but this looks non-trivial to code in R. I'll do it if I have to, but if it already exists it would be nice. If I do have to code it, I'd really appreciate an expression in algebra rather than Matlab! Any pointers will be much appreciated, Keith Jewell Duncan Murdoch murd...@stats.uwo.ca wrote in message news:4b20e1ea.3030...@stats.uwo.ca... On 10/12/2009 5:15 AM, Keith Jewell wrote: 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 That looks like it would work, but wouldn't it be easier to do the following: Compute the convex hull with the new point added. If the point is exterior, the new point will be part of the hull. If interior, it won't be. If it is on the boundary, it's probably unpredictable, but due to rounding error, that's probably true even with a perfect algorithm. I didn't notice that you said how your original polygon is defined, but if it is defined as a convex hull or in terms of its vertices, the above method would work. If it's defined some other way, it might be hard. Duncan Murdoch 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
Re: [R] mutlidimensional in.convex.hull (was multidimensional point.in.polygon??)
On Thu, 10 Dec 2009, Keith Jewell wrote: Hi All (especially Duncan and Baptiste), Summary (of lengthy bits below): I will have a convex hull in multiple (3 to 10) dimensions derived from many (thousands) of points by geometry::convhulln. I will need to categorise other 'test' points as inside/outside that convex hull . e.g. given: -- require(geometry) ps - matrix(rnorm(4000),ncol=4) # 'calibration' set phull - convhulln(ps) # convex hull xs - matrix(rnorm(1200),ncol=4)# 'test' set - How do I categorise each point (row) in xs as inside/outside(/on) phull??? There is tripack::in.convex.hull but that doesn't handle my dimensionality. Thanks to Duncan Murdoch for the suggestion (just a few lines down, previously made by Baptiste Auguie): of testing a single point thus: i) add the test point to the set of points defining the convex hull, ii) recalculate the convex hull iii) if the test point is part of the new convex hull, then it was outside the original BUT I have many (thousands) of test points, so this would involve very many convex hull calculations. My suggestion, immediately below, requires finding the signs of perpendicular distances from each test point to each multidimensional 'plane' defining the convex hull (NB: phull is a matrix in which each row defines such a 'plane'). Many? set.seed(1234) ps - matrix(rnorm(4000),ncol=4) phull - convhulln(ps) xs - matrix(rnorm(1200),ncol=4) phull2 - convhulln(rbind(ps,xs)) nrp - nrow(ps) nrx - nrow(xs) outside - unique(phull2[phull2nrp])-nrp done - FALSE while(!done){ + phull3 - convhulln(rbind(ps,xs[-(outside),])) + also.outside - (1:nrx)[-outside][unique(phull3[phull3nrp])-nrp] + print(length(also.outside)) + outside - c(outside,also.outside) + done - length(also.outside)==0 + } [1] 3 [1] 0 phull2 was evaluated once, phull3 twice. Any point that is in the convex hull of rbind(ps,xs) is either in or outside the convex hull of ps. Right? So, just recursively eliminate points that are in the convex hull of the larger set. Chuck p.s. for xs - matrix(rnorm(12),ncol=4) it required about a dozen iterations Baptiste has found a Matlab implementation http://www.mathworks.com/matlabcentral/fileexchange/10226-inhull of (what looks like) my algorithm. I don't speak Matlab, but this looks non-trivial to code in R. I'll do it if I have to, but if it already exists it would be nice. If I do have to code it, I'd really appreciate an expression in algebra rather than Matlab! Any pointers will be much appreciated, Keith Jewell Duncan Murdoch murd...@stats.uwo.ca wrote in message news:4b20e1ea.3030...@stats.uwo.ca... On 10/12/2009 5:15 AM, Keith Jewell wrote: 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 That looks like it would work, but wouldn't it be easier to do the following: Compute the convex hull with the new point added. If the point is exterior, the new point will be part of the hull. If interior, it won't be. If it is on the boundary, it's probably unpredictable, but due to rounding error, that's probably true even with a perfect algorithm. I didn't notice that you said how your original polygon is defined, but if it is defined as a convex hull or in terms of its vertices, the above method would work. If it's defined some other way, it might be hard. Duncan Murdoch 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