Re: Point inside a plygon? and PointInsidePolyhedronQ
- To: mathgroup at smc.vnet.net
- Subject: [mg25340] Re: [mg25239] Point inside a plygon? and [mg24992] PointInsidePolyhedronQ
- From: Andrzej Kozlowski <andrzej at bekkoame.ne.jp>
- Date: Sat, 23 Sep 2000 03:36:05 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
Below are a few comments that came to my mind on reading the message below. I think one problem here is that it is not clear exactly which initial data you are assuming. Consider just the two dimensional case: the situation is rather different if we start with a polygon (basically just an ordered list of points) from the one in which the starting data consist of a polygon with an already given triangulation. If we are in the first situation (as appears from the actual question sent to the mathgroup) than to use David Park's method we would have to triangulate the polygon first. More, we would need a general procedure that would produce a canonical triangulation of any polygon. While I can prove that any polygon can be triangulated I do not know of an algorithm that will triangulate and arbitrary polygon. My speciality is algebraic not combinatorial topology so I am not prepared to assert that such an algorithm does not exist, but at least it's existence is not obvious to me. Even if there is such an algorithm, its complexity would most likely not be very good. Besides, David's method would require checking every triangle in a triangulation. In the three dimensional case not only a triangulation but also directed normals to the simplexes were given. Again they would be difficult to compute if they were not provided as part of the initial data. So it seems to me that rather than having three methods to solve the same problem you are talking about three methods to solve three different (of decreasing generality) problems. There is indeed a higher dimensional analogue of the integration method. But since Mathematica can't integrate differential forms or functions over surfaces in R^3 (not to mention higher dimensions) somebody would have to to develop virtually from scratch. This seems to be a highly non-trivial task. So does the rest of your proposal, c.f. Mathematica's Computational Geometry package which contains some of the things you mention but only in two dimensions. Andrzej Kozlowski on 00.9.20 8:38 PM, Ingolf Dahl at f9aid at fy.chalmers.se wrote: > Message history: > Will Self in [mg24992] asks for a test to find if a point is inside a > polyhedron. > Adriano Moreira in [mg25239] asks for a test to find if a point is inside a > polygon. > Andrzej Kozlowski in [mg25299] suggests that we place the polygon in the > complex plane, with a pole in the point, and find if the point is inside the > polygon by evaluating a contour integral around the polygon. > David Park in [mg25279] suggests that we should divide the polygon in > triangles. For each triangle we should, calculate the area, and compare this > to the sums of the areas we get if we form triangles from our point and two > corners of our triangle. He also says that it would be interesting to learn > if there are other methods to > find if a point is inside a polygon. > Wouter Meeussen in [mg26261] has supplied a notebook, that evaluates if a > point is inside a torus. > > In the spirit of Stephen Wolfram, we maybe should reformulate these > questions in the most general way. > How should we find if a point is inside or outside a generalized > n-dimensional polyhedron? > > I think that there are at least three different approaches to solve this > problem. > > The method of David Park evidently is possible to generalize to n > dimensions. We could represent the n-dimensional polyhedron as a set of > non-intersecting simplexes. A n-dimensional simplex is a body with n+1 > vertices (corners), all joined, see > http://mathworld.wolfram.com/Simplex.html. In one dimension we get a line > segment, in two dimensions we get a triangle, in three dimensions we get a > tetrahedron. It should be possible to calculate the content (n-D volume) of > each simplex, and compare that to the sum of all contents we achieve if we > form new simplexes from our point and n of the vertices of the simplex. > > The method of Andrzej Kozlowski is possible to generalize to three > dimensions if we make a physical analogy. Suppose that we place a positive > charge in our test point. This gives a radial electric field, with a > strength that decays as one over distance squared. According to Gauss > theorem, we could integrate the component of the electric field that is > parallel to the outward surface normal over the surface of the polyhedron. > Then we get a positive contribution if the point is inside the polyhedron, > and zero otherwise. In the two-dimensional case, we could also use a > physical analogy: let the point be the intersection between a plane and a > charge-carrying wire, and calculate the circulation of the magnetic field > around the polygon. Alternatively, using liquid crystal physics, we could > place a nematic disclination line through the point, and find the winding > number of the nematic director along the polygon. These methods are probably > possible to generalize to n dimensions, but that is beyond my mathematical > competence. > > There should also be a third method. Our polygon is bounded by line > segments, and our polyhedron is bounded by polygons. We could scan the > boundary for the closest boundary point to our test point. Then we could > easily check how the surface normal is directed there, and from that > conclude if our test point is inside or outside the generalized polyhedron. > > Maybe someone could write a package, using one of the methods... I think it > is a good idea to represent the generalized polyhedron as a set of > simplexes, where each simplex easily can be specified by giving a list of > the vertices. Such a package could of course also contain other interesting > things: a function to calculate the content and generalized surface area of > a simplex or a generalized polyhedron (see > http://mathworld.wolfram.com/Cayley-MengerDeterminant.html), a function to > relate the corner angles to the edge angles for a tetrahedron etc. The > distance between a point and a simplex is also of interest in itself, as > well as the location and nature of the closest boundary point. > > Ingolf Dahl > Chalmers University, Göteborg, Sweden > f9aid at fy.chalmers.se > > > -- Andrzej Kozlowski Yokohama, JAPAN http://platon.c.u-tokyo.ac.jp/andrzej/ http://sigma.tuins.ac.jp/