CFD Online Discussion Forums

CFD Online Discussion Forums (http://www.cfd-online.com/Forums/)
-   Main CFD Forum (http://www.cfd-online.com/Forums/main/)
-   -   point inside a hexahedron (http://www.cfd-online.com/Forums/main/11884-point-inside-hexahedron.html)

gama July 27, 2006 05:08

point inside a hexahedron
 
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

Gerrit July 27, 2006 07:40

Re: point inside a hexahedron
 
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.


gama July 27, 2006 08:54

Re: point inside a hexahedron
 
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.

Gerrit July 27, 2006 09:19

Re: point inside a hexahedron
 
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.

Mani July 27, 2006 15:21

Re: point inside a hexahedron
 
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. :)

Dr.Nick July 28, 2006 00:43

Re: point inside a hexahedron
 
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.

Arambatzis George July 28, 2006 09:06

Re: point inside a hexahedron
 
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.


All times are GMT -4. The time now is 01:24.