Re: Point inside a plygon? and PointInsidePolyhedronQ
- To: mathgroup at smc.vnet.net
- Subject: [mg25344] Re: [mg25239] Point inside a plygon? and [mg24992]PointInsidePolyhedronQ
- From: Andrzej Kozlowski <andrzej at bekkoame.ne.jp>
- Date: Sat, 23 Sep 2000 03:36:08 -0400 (EDT)
- Sender: owner-wri-mathgroup at wolfram.com
on 9/21/00 12:04 PM, David Park at djmp at earthlink.net wrote: Dear David I am not quite sure what exactly you mean when you say: > The complex plane approach is a little touchy on the integration parameters. The approach certainly seems mathematically sound (based on Cauchy's Integral formula). Actually it does not really require complex integration since one could do exactly the same thing if Mathematica knew how to integrate differential forms over piecewise linear curves (and if it could do so over polygons in space one cold solve the there dimensional problem). Could you elucidate the nature of the problem you see here? Is it mathematical or is it something to with Mathematica's implementation of numerical contour integration? I have tried it in several cases and it never failed so far. It seems reasonably fast too. I have not been able to consider your attempted sketch of the triangulation of a polygon carefully as I am rather busy at he moment with preparing my lectures. I can't see just now how you intend to find out whether the triangles you are constructing actually lie within the polygon (in the non-convex case). It is clear that if you already have a method for deciding whether a point lies inside the polygon or not than indeed you can easily triangulate it. But I can't see how to do this without using something equivalent to solution of the problem we started with. There are two additional remarks I would like to make concerning your method. Firstly, instead of computing areas you can make use of the ConvexHull function of the DiscreteMath`ComputationalGeometry` package. If S is know to be a convex set of points you can check if a point P lies in S simply by comparing the ConvexHull[S] with ConvexHull[Append[S,P]]. This ought to be faster than computing areas and it works for any convex polygon. Secondly, any approach to the problem which requires a triangulation algorithm will in my opinion by impractical, because the number of triangles will tend to be very large. Instead of this one should try to solve the following problem: Given a convex polygon decompose the area contained within it as a disjoint union of the smallest possible number of (open) convex subsets. I do not know an algorithm that would do this either (without, of course, assuming that one already knows how to decide if a point lies inside or outside the polygon) but it should not be harder than finding a way to triangulate an arbitrary non-convex polygon. The number of such convex polygons will be in general much smaller than the number of triangles in a triangulation and the problem should be then solvable in reasonable time. Finally, note that when one triangulates a non-convex polygon "by hand" one is actually making use of the ability to "decide" (by just looking) which points lie inside or outside when choosing which vertices to join and which not to join. This is what one has to avoid when producing a formal algorithm that could be turned into a usable program. Andrzej on 9/21/00 12:04 PM, David Park at djmp at earthlink.net wrote: > I also posted a different method using cross products of the polygon edges > with the vector from the base of each edge to the point, and then looking > for changes in the sign of the z component. This only works for convex > polygons. > > The area approach and the complex plane approach seem to work for non-convex > polygons as well. The complex plane approach is a little touchy on the > integration parameters. The area approach requires a breaking of the polygon > into triangles. If the polygon is non-convex, I don't know an easy way to do > this, other than by inspection. > > The DiscreteMath`ComputationalGeometry` package doesn't seem to address this > problem. So what we need is an algorithm to break a polygon into triangles > even if it is nonconvex. (A nonconvex polygon may sometimes be broken into > sequential triangles.) I can see the dim outline of such an algorithm. Given > a sequential set of points which define the polygon, try to break it into > sequential triangles. But with each new triangle check to see if any of the > remaining points are within the triangle. We know how to do that. We have to > pick the point which puts all remaining points outside the triangle. Then > our polygon is going to be broken into sub-polygons and we continue until > all the points are used. It looks like a recursive routine. It would be > surprising if someone, somewhere hasn't already worked this out.