
[Sponsors] 
July 27, 2006, 05:08 
point inside a hexahedron

#1 
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


July 27, 2006, 07:40 
Re: point inside a hexahedron

#2 
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. 

July 27, 2006, 08:54 
Re: point inside a hexahedron

#3 
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.


July 27, 2006, 09:19 
Re: point inside a hexahedron

#4 
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. 

July 27, 2006, 15:21 
Re: point inside a hexahedron

#5 
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 ABCD of the hexahedron, you are assuming it is piecewise 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 piecewise 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. 

July 28, 2006, 00:43 
Re: point inside a hexahedron

#6 
Guest
Posts: n/a

Calculate 2 volumes of tetrahedron: Vol1=detv1,v2,v3. Then calculate vilumes of tetrahedron through the desired point (Vol2) and other points. CMP. If Vol1<Vol2, then it's outside.


July 28, 2006, 09:06 
Re: point inside a hexahedron

#7 
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. 

Thread Tools  
Display Modes  


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 