Re: Point inside a plygon? and PointInsidePolyhedronQ

• To: mathgroup at smc.vnet.net
• Subject: [mg25375] Re: [mg25239] Point inside a plygon? and [mg24992] PointInsidePolyhedronQ
• From: Martin Kraus <Martin.Kraus at informatik.uni-stuttgart.de>
• Date: Sun, 24 Sep 2000 16:29:08 -0400 (EDT)
• Organization: Institut fuer Informatik, Universitaet Stuttgart
• References: <8qhnir\$j1p@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Hi there!

on this message.

Ingolf Dahl 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.

David Park's proposal of finding the number of intersection points
of a ray out of the polygon is probably the best (best trade-off between
work
to implement and running time) method here, also we should
improve the choice of outpoint in order to avoid degeneracies
(by adding some irrational numbers for instance).
(Or we should really deal seriously with degeneracies.)

> 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?

A good reference for this problem is Chapter 30 of the
"Handbook of Discrete and Computational Geometry" (Goodman,
O'Rourke (eds.)) by Jack Snoeyink.

> 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.

Representing an "n-dimensional polyhedron as a set of
non-intersecting simplexes" is quite difficult. Please let me know
if you know about an implementation of an algorithm for n=3!!!
(Chazelle and Palios proposed one in "Triangulating a Nonconvex
Polytope"
(Discrete Comput. Geom 5:505-526 (1990) and proved that it is optimal
in the worst case. But I am not aware of a robust and efficient
implementation.
I did not test the method recently proposed by B. Kaan Karamete,
Mark W. Beall and Mark S. Shepard (SCOREC Report #:4-1999),
but I think it is only useful for not too complicated polyhedra.)

For more references to the problem of triangulation (subdivision
into simplices) see Chapters 14 and 22 of the book mentioned above.
(It is a well-known problem in Computational Geometry *and*
Mesh Generation but there seems to be a lack of efficient and
robust implementations.)

I should also mention that there are Mathematica packages for the
triangulation of (simple and non-simple) polygons available:
http://library.wolfram.com/packages/polygontriangulation/

> The method of Andrzej Kozlowski is possible to generalize to three
> dimensions if we make a physical analogy.
> ...

I think this method is a very nice idea but I am not sure
whether it has any real-world applications.

> 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.

I guess I found a counter-example: Think of a small angle of
a convex polygon and place the point outside the polygon such
that the closest points to the two line segments is their intersection
point. For small angles it is possible to place the point such,
that is inside with respect to one line and outside with respect
to the other. What to do now? (Taking into account that the
two line segements are neighbors does not help in the case of
non-convex polygons.)

> 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.

The order of the vertices is very important.

> 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

Probably we should wait for the extensions of the
computational geometry package in the next version of Mathematica
before investing too much time here. :)
On the other hand I am increasingly interested in implementing
triangulation algorithms in 2 and 3 dimensions in Mathematica.