MathGroup Archive 2000

[Date Index] [Thread Index] [Author Index]

Search the Archive

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





  • 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