[R] multidimensional point.in.polygon??
Keith Jewell
k.jewell at campden.co.uk
Thu Dec 10 11:15:19 CET 2009
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.auguie at googlemail.com> wrote in message
news:de4e29f50912040550m71fbffafnfa1ed6e0f4451604 at 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.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.
>
More information about the R-help
mailing list