### Tags: code, constructed, determining, in3d, inpolygon, inside, matlab, oroutside, point, points, polygon, programming

# inpolygon in 3D

On Programmer » Matlab

15,232 words with 9 Comments; publish: Wed, 07 May 2008 13:26:00 GMT; (20062.01, « »)

I would like to have a code for determining if a point is inside or

outside from the 3D polygon constructed from a given set of points in

3D.

There is a function called inpolygon.m, but this is only for 2D. So

I would like to have a 3D version of that function.

Your help will be deeply appreciated.

Many thanks,

Hong.

*http://matlab.todaysummary.com/q_matlab_31290.html*

All Comments

Leave a comment...

- 9 Comments
- If it's convex polygon, then there is function "inhull" at file
exchange which can do what ever you are loking for.

********************

hong wrote:

>

> I would like to have a code for determining if a point is inside or

> outside from the 3D polygon constructed from a given set of points

> in

> 3D.

> There is a function called inpolygon.m, but this is only for 2D.

> So

> I would like to have a 3D version of that function.

> Your help will be deeply appreciated.

> Many thanks,

> Hong.

#1; Wed, 07 May 2008 13:27:00 GMT

- If it's convex polygon, then there is function "inhull" at file
- 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?

Thanks,

Gab

#2; Wed, 07 May 2008 13:28:00 GMT

- b wrote:
- In article <e1mttn$tnj$1.matlab.todaysummary.com.area.cu.mi.it>, Gabriele Bulian <ruga.matlab.todaysummary.com..REMOVENOSSSS
PAM.libero.it> wrote:

> b wrote:

> 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

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

#3; Wed, 07 May 2008 13:29:00 GMT

- In article <e1mttn$tnj$1.matlab.todaysummary.com.area.cu.mi.it>, Gabriele Bulian <ruga.matlab.todaysummary.com..REMOVENOSSSS
- John D'Errico wrote:
> In article <e1mttn$tnj$1.matlab.todaysummary.com.area.cu.mi.it>, Gabriele Bulian <ruga.matlab.todaysummary.com..REMOVENOSS

SSPAM.libero.it> wrote:

>

>

> My approach, where a tessellation exists, is to compute

> barycentric coordinates for each point in each simplex.

[...]

> If all you have is a hull, it is still possible to

> generate a tessellation, even if its not convex.

> John

Hi John,

what you said could be very useful for me...however, I have to be

honest, I did not get the method at all...may you give me some

description or some reference where I can understand how to do?

Thanks,

Gab

#4; Wed, 07 May 2008 13:30:00 GMT

- John D'Errico wrote:
- John D'Errico wrote:
> In article <e1mttn$tnj$1.matlab.todaysummary.com.area.cu.mi.it>, Gabriele Bulian <ruga.matlab.todaysummary.com..REMOVENOSS

SSPAM.libero.it> wrote:

>

>

> 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

#5; Wed, 07 May 2008 13:31:00 GMT

- John D'Errico wrote:
- In article <e2589v$s0u$1.matlab.todaysummary.com.area.cu.mi.it>, Gabriele Bulian <ruga.matlab.todaysummary.com..REMOVENOSSSS
PAM.libero.it> wrote:

> John D'Errico wrote:

> 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/Baryce...oordinates.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

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

#6; Wed, 07 May 2008 13:32:00 GMT

- In article <e2589v$s0u$1.matlab.todaysummary.com.area.cu.mi.it>, Gabriele Bulian <ruga.matlab.todaysummary.com..REMOVENOSSSS
- Hey John,
I think I follow what you're on about, but doesn't this assume that

you already have a tessellation of the 3D polygon that is boundary

conforming'

As far as I know, if you use delaunayn to give you the tessellation

for a set of points in [x,y,z] it will fill the convex hull with

tetrahedra, which is fine if the polygon is convex but leads to

unhappiness otherwise.

Do you have a cute way of getting back to the constrained delaunay

tessellation or another way around this entirely'

Darren

#7; Wed, 07 May 2008 13:33:00 GMT

- Hey John,
- Darren wrote:
>

> Hey John,

> I think I follow what you're on about, but doesn't this assume that

> you already have a tessellation of the 3D polygon that is boundary

> conforming'

> As far as I know, if you use delaunayn to give you the tessellation

> for a set of points in [x,y,z] it will fill the convex hull with

> tetrahedra, which is fine if the polygon is convex but leads to

> unhappiness otherwise.

> Do you have a cute way of getting back to the constrained delaunay

> tessellation or another way around this entirely'

> Darren

Yes, delaunayn will generate a convex tessellation,

which may often be inappropriate.

Many of the non-convex tessellations that I've used

arose from an alpha shape. Its a slick tool for

eroding a delaunay tessellation into a non-convex

object. Imagine a sphere of radius alpha, rolling

around the perimeter of a delaunay tessellation.

Do not allow any of the vertices to penetrate the

sphere, but if the sphere can touch an internal

vertex of the tessellation, then delete any simplex

that the sphere passed through to do so.

Think of an alpha shape as a tessellation with an

envelope generated by the alpha ball. The parameter

alpha is generally fixed at some user chosen value.

There is a 2-d alpha shape tool on the FEX. Yes,

its another of the tools I need to put up there, an

n-d alpha shape. I clearly need to stop answering

questions and get to work. ;-) I have seen alpha

shape codes on the internet, as well as web site

demos, although I've never seen an implementation

beyond 3-d. My own implementation was only for 2-d

and 3-d, but the extension beyond is doable.

I've also used other methods to generate non-convex

tessellations. The most common one involved a well

behaved mapping of one 3-d space to another, where

I had a simple tessellation in the first space.

Carry over the tessellation into the range space of

the mapping. (Yes, this can be dangerous, especially

when the mapping may be a slightly noisy one. An

interesting question that I solved is how to find

the smallest perturbation to a set of measurements

such that the derived mapping is indeed well behaved.)

John

#8; Wed, 07 May 2008 13:34:00 GMT

- Darren wrote:
- John D'Errico wrote:
> Darren wrote:

[...]

> interesting question that I solved is how to find

> the smallest perturbation to a set of measurements

> such that the derived mapping is indeed well behaved.)

> John

Hi john, and thanks for your message.

Now I got how it works for convex 3D object...however in my case I have

a not convex object. I know this object is closed and the patch is well

defined (I mean, no holes, apart from eps differences. As far as I have

understood, in order to erode the 4-simplices tesselation and make it

not convex, I should apply something like this alpha shape

idea...mmm...I think it is not a really simply task. Actually I think

the ways around I'm using can provide more or less what I need.

The increasing complexity in the implementation, would not give a big

improvement in the solutions...

Just as an example, in my case I have this 3D object, that is actually a

not convex and complex floating body defined by a patch on its surface.

I need to determine some geometrical quantities related to the area of

the intersection between this body and the free surface. I asked my

question because one idea is a numerical "finite points" description of

this area, i.e.:

1) generate a large number of points on a delta_x X delta_y grid on the

free surface

2) determine which points are inside the solid and delete the others

3) use the remaining points to estimate area, centroid, etc.

However, it seems this is not as easy as it was in 2D...so, actually I

have some ways around...for example,if I want to calculate the area, I

consider the function Volume(T) where T is the vertical position of the

waterplane (i.e. the object draught) or a series of draughts T close to

the draught I need, and then I obtain the area by the differential

relation dVolume/dT=Area(T)...this is quite easy for the area, becuase

volume can be computed quite easily...a little bit more complicated (but

similar) is the situation regarding the centroid and moments of

inertia...however...such ways seem much easier that the implementation

of this alpha shaping...am I wrong?

Tnks,

Gab

#9; Wed, 07 May 2008 13:35:00 GMT

- John D'Errico wrote: