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/

```

• 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