CFD Online Logo CFD Online URL
www.cfd-online.com
[Sponsors]
Home > Forums > Main CFD Forum

point inside a hexahedron

Register Blogs Members List Search Today's Posts Mark Forums Read

Reply
 
LinkBack Thread Tools Display Modes
Old   July 27, 2006, 05:08
Default point inside a hexahedron
  #1
gama
Guest
 
Posts: n/a
Does anyone has an algorithm as to how to verify the presence of a point inside or on the surface of hexahedron. I have the following data 1. Coordinates of the point 2. coordinates of the vertices of hexahedron. Regards
  Reply With Quote

Old   July 27, 2006, 07:40
Default Re: point inside a hexahedron
  #2
Gerrit
Guest
 
Posts: n/a
I don't remember exactly, but maybe this helps you to find the solution.

I think you have to do that by comparing volumes.

If your hexahedron has the corners A,B,C,D, E,F,G,H (with E above A) and your point is at point P you may compute the volume of all piramides: PABCD, PCDHG, PDAEH, PABFE, PCBFG, PEFGH and sum them.

If this happens to be equal to the volume of the hexahedron, P must be inside, if it happens to be bigger than the volume of the hexa P must be outside.

Maybe someone can give you a more general formula with vector products that actually compute the same. These must then be made from P to some triangular surface, like ABC, BCD, etc.

Anyway, it may not be the exact general solution, but I think it can be done in this way.

  Reply With Quote

Old   July 27, 2006, 08:54
Default Re: point inside a hexahedron
  #3
gama
Guest
 
Posts: n/a
The problem would be calculating the volume of irregular hexahedron. First place i need to map that to a regular geometry and then calculate the volume, which will not give me an exact volume but an approximate volume. I guess this idea will work for a regular shaped geometry like cube or so but becomes complicated for irregular shaped geometries.
  Reply With Quote

Old   July 27, 2006, 09:19
Default Re: point inside a hexahedron
  #4
Gerrit
Guest
 
Posts: n/a
No, it should work for ANY geometry and you don't need to do any strange mapping or whasoever (if not I would never do it)

If you divide every side of your hexa into two triangles and calculate the volume of the paralelpiped shape, the volume of the pyramide, with a triangular shape, should be something like (1/6)*det(matrix(v1,v2,v3)) (see wolfram web page) where v1, v2 and v3 go from p to point 1,2 and 3 from your triangle. Actually with the determinant you're doing a dot and a vector product.

So you could even do this for a whole aeroplane.
  Reply With Quote

Old   July 27, 2006, 15:21
Default Re: point inside a hexahedron
  #5
Mani
Guest
 
Posts: n/a
I guess gama's point was that the tetrahedron method is not necessarily exact. If you triangulate an arbitrary quadrilateral side A-B-C-D of the hexahedron, you are assuming it is piece-wise planar (consisting of two triangles), which doesn't have to be the case.

Anyway, that method will be good enough for most applications (i.e. if the hexahedron is not too irregular). Accuracy will be a concern if the point is very close to a surface or right on the surface.

Then again, you can always define your element as having a piece-wise planar surface (a quadrilateral surface is not uniquely described by four points). Just make sure the surface definition is consistent between neighboring elements. So, triangulation may well be exact, if you define it that way.
  Reply With Quote

Old   July 28, 2006, 00:43
Default Re: point inside a hexahedron
  #6
Dr.Nick
Guest
 
Posts: n/a
Calculate 2 volumes of tetrahedron: Vol1=det|v1,v2,v3|. Then calculate vilumes of tetrahedron through the desired point (Vol2) and other points. CMP. If Vol1<Vol2, then it's outside.
  Reply With Quote

Old   July 28, 2006, 09:06
Default Re: point inside a hexahedron
  #7
Arambatzis George
Guest
 
Posts: n/a
I have a different idea. You can transform the general hexahedron to a standard hex ( e.g. -1<=x,y,z<=1 ). Then apply this transformation to the point. If its transformed coordinates are between -1 and 1 then the point belongs to the hexahedron.

I hope I helped.
  Reply With Quote

Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


Similar Threads
Thread Thread Starter Forum Replies Last Post
SnappyHexMesh Point is not inside Mesh but it is wolle1982 OpenFOAM Mesh Utilities 6 September 3, 2010 08:59
Point inside Cell bobatpurdue OpenFOAM Meshing & Mesh Conversion 7 November 11, 2008 20:32
BlockMeshmergePatchPairs hjasak OpenFOAM Native Meshers: blockMesh 11 August 15, 2008 07:36
How to mesh the 1st grid point? Daniel Main CFD Forum 1 October 8, 2007 02:27
How to determine a point is inside a tetrahedral? G.P. Xia Main CFD Forum 16 January 12, 2000 11:15


All times are GMT -4. The time now is 09:35.