RE: Point inside a plygon? and PointInsidePolyhedronQ
- To: mathgroup at smc.vnet.net
- Subject: [mg25336] RE: [mg25239] Point inside a plygon? and [mg24992] PointInsidePolyhedronQ
- From: "Ingolf Dahl" <f9aid at fy.chalmers.se>
- Date: Sat, 23 Sep 2000 03:35:59 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
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, Goteborg, Sweden f9aid at fy.chalmers.se