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.

```

• Prev by Date: RE: Point inside a plygon? and PointInsidePolyhedronQ
• Next by Date: Re: Point inside a plygon? and PointInsidePolyhedronQ
• Previous by thread: RE: Point inside a plygon? and PointInsidePolyhedronQ
• Next by thread: Re: Point inside a plygon? and PointInsidePolyhedronQ