Re: [R] multidimensional point.in.polygon??
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.
Re: [R] multidimensional point.in.polygon??
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
Re: [R] multidimensional point.in.polygon??
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 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
Re: [R] multidimensional point.in.polygon??
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.