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; (200183.59, « »)

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.

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
    • 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
    • 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
    • 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:

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

      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

      #6; Wed, 07 May 2008 13:32:00 GMT
    • 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
    • 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
    • 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