Re: inpolygon in 3D

In article <e2589v$s0u$1@xxxxxxxxxxxxx>, Gabriele Bulian <ruga@.REMOVENOSSSSPAM.libero.it> wrote:

John D'Errico wrote:
In article <e1mttn$tnj$1@xxxxxxxxxxxxx>, Gabriele Bulian
<ruga@.REMOVENOSSSSPAM.libero.it> wrote:

b wrote:
If it's convex polygon, then there is function "inhull" at file
exchange which can do what ever you are loking for.
Is there something for the case of a closed 3D solid (not necessarily
convex) defined by a patch a for which, at each face, the outer normal
is known?


My approach, where a tessellation exists, is to compute
barycentric coordinates for each point in each simplex.

Its easier than it seems, since it only takes a single
massive matrix multiply. You can be careful here and
block it as I do so the problem does not exceed the
available memory.

If the coordinates are all in the interval [0,1],
then a point is inside that simplex. Clearly this is
insensitive to convexity of the overall object. And
as a bonus, it even provides a simple way to allow a
tolerance. A second bonus is it works in n-dimensions.
The objects I've tended to work with were often not
convex, so these factors were all importance.

If all you have is a hull, it is still possible to
generate a tessellation, even if its not convex.

John

MMM...I'm keeping on reading your message, but:
1) I don't understand how do you form simplex
2) what do u mean with baricentric
3) why the final check is in the interval [0,1]
Regarding tessellation, I think that a closed 3D patch could be
considered a tessellation...isn't it?

Sorry for double reply,
Gab

This might be a long one. I'll propose some terminology
that I might need along the way.

A simplex is defined by its vertices, typically as
references into a list of points. This is what convhulln
and delaunayn return. A k-simplex is defined by its k+1
vertices. Thus a tetrahedron, as delaunayn would return
for 3-d data is a 3-simplex. The convex hull of that
data is composed of 2-simplexes, more commonly known as
triangles.

For example,

xyz = rand(5,3)
xyz =
0.81372 0.73083 0.94524
0.46623 0.64967 0.61327
0.72229 0.68134 0.78293
0.99487 0.0076119 0.0031535
0.3625 0.65415 0.79696

tess= delaunayn(xyz)
tess =
3 1 4 5
3 2 4 5
3 2 1 5

tri = convhulln(xyz)
tri =
1 4 5
4 2 5
2 1 5
1 3 4
3 2 4
2 3 1

The integers in tri and tess are references into rows
of xyz, defining the corners of the respective triangles
and tetrahedrae built by those tools.

We can also describe the convex surface represented in
tri as a 2-manifold, embedded in the 3-d space of our
data.

The triangulation generated by a convex hull is a
simplicial complex, but I would tend not to call it a
tessellation, reserving that term for a volume filling
complex.

http://mathworld.wolfram.com/SimplicialComplex.html

Given any 4-simplex (tetrahedron) in the 3-d space, we
can represent any other point as a linear combination
of its 4 vertices as long as the simplex is not degenerate.
A degenerate simplex might have all 4 points coplanar,
or a pair of replicated points, or 3 of its vertices
collinear.

As long as the simplex is not degenerate, we can derive
this unique linear combination. Consider the general set
of vertices:

XYZ = [x1 y1 z1;x2 y2 z2;x3 y3 z3;x4 y4 z4];

and the single tetrahedron defined by those 4 vertices:

tess = [1 2 3 4];

Now, consider any point (x,y,z) in the 3-d space. How
can we represent it as a linear combination of those
4 vertices? I'll write out the equations:

x1*w1 + x2*w2 + x3*w3 + x4*w4 = x
y1*w1 + y2*w2 + y3*w3 + y4*w4 = y
z1*w1 + z2*w2 + z3*w3 + z4*w4 = z

These are 3 equations in the 4 unknowns (w1,w2,w3,w4).
A fourth equation comes from a requirement that the 4
weights must sum to 1. Thus

w1 + w2 + w3 + w4 = 1

Its easy enough to show that as long as the points
in XYZ represent a non-degenerate simplex, then this
system of equations is non-singular, so it must result
in a unique solution for the unknowns.

I'll name these linear coefficients (w1,w2,w3,w4) the
barycentric coordinates of the point (x,y,z) with
respect to our simplex. (Actually, given the unit sum
constraint, they would be called homogeneous barycentric
coordinates.) The name barycentric comes from an
interpretation of the coordinates as relative areas
in the 2-d case (or volumes in higher dimensions.)

http://mathworld.wolfram.com/BarycentricCoordinates.html

http://www.cut-the-knot.org/triangle/barycenter.shtml

What properties do these coordinates have? You can
easily enough convince yourself that if (x,y,z) =
(x1,y1,z1), then its coordinates must be (w1,w2,w3,w4)
= (1, 0, 0, 0), the other vertices will behave
similarly. A point along an edge of the tetrahedron
will have two zero coordinates and the other two
coordinates non-zero.

Likewise if the point (x,y,z) lies strictly inside
of the tetrahedron, then all four of its coordinates
will be positive and less than 1.

It is this property that we can exploit to determine
if a point is inside. Any negative weights or weights
greater than unity indicate the point is outside.

I hope this answers some of your questions. A good
reference for many of the terms above can be found at
http://mathworld.wolfram.com/

HTH,
John D'Errico


--
The best material model of a cat is another, or preferably the same, cat.
A. Rosenblueth, Philosophy of Science, 1945

Those who can't laugh at themselves leave the job to others.
Anonymous
.

Relevant Pages

  • Re: Winternitz Theorem
    ... On the union of convex bodies with no interior point in common. ... nonsimplicial set cut from a fixed $d$-simplex by one of the hyperplanes ... through the center of gravity of the simplex and parallel to a facet of ...
    (sci.math.research)
  • Re: inpolygon in 3D
    ... Is there something for the case of a closed 3D solid (not necessarily convex) defined by a patch a for which, at each face, the outer normal is known? ... My approach, where a tessellation exists, is to compute ... barycentric coordinates for each point in each simplex. ... A second bonus is it works in n-dimensions. ...
    (comp.soft-sys.matlab)
  • Re: inpolygon in 3D
    ... barycentric coordinates for each point in each simplex. ... A second bonus is it works in n-dimensions. ... convex, so these factors were all importance. ... The best material model of a cat is another, or preferably the same, cat. ...
    (comp.soft-sys.matlab)
  • Re: hahn banach
    ... I'm searching an example of two convex sets A and B ... A closed hyperplane (ie one defined by a _continuous_ ... A and B are disjoint, convex, and if L is any linear ...
    (sci.math)
  • Re: Insphere of a tetrahedron
    ... >Given an irregular tetrahedron as 4 space point coordinates. ... A, B, C of the triangle ABC and let O be the triangle's incenter. ... Let a, b, c, d be the areas of the faces opposite to vertices ... This, too, gives O as a convex combination of the vertices. ...
    (sci.math)