
[Sponsors] 
Need an algorithm that searches the cell that an arbitrarily given point is within 

LinkBack  Thread Tools  Display Modes 
July 14, 2015, 19:46 
Need an algorithm that searches the cell that an arbitrarily given point is within

#1 
New Member
Yidong
Join Date: Nov 2011
Posts: 23
Rep Power: 6 
Such an algorithm is common in commercial CFD postprocessing software. But I want to implement in my own CFD postprocessing code:
In finite volume or finite element mesh: [1] Specify an arbitrary point in space [2] Find a cell or element that the given point can be within [3] So that the solution value at this point can be interpolated by solution data. Thanks in advance for recommending any literature for such an algorithm 

July 14, 2015, 22:25 

#2 
Member
Join Date: Jul 2013
Posts: 49
Rep Power: 5 

July 15, 2015, 03:23 

#3 
Senior Member
Filippo Maria Denaro
Join Date: Jul 2010
Posts: 2,411
Rep Power: 31 
Many times ago I developed a simple method on unstructured grid.
It is based on the linear shape function on triangle. Whena point is outside the chosen triangle, you get alway a negative value for the shape function avaluated using it. Only when the point is inside a triangle, you get positive values. I used for Lagrangian transport, the method then searches at next time step only adjacent triangles to save computational time. 

July 15, 2015, 09:17 

#4 
Member
Join Date: Jul 2013
Posts: 49
Rep Power: 5 
I'll give my idea for a 2D triangular mesh (I don't know if it is documented, and I've never tried it myself)
For a given cell and a given point. 1 Calculate the area of the cell (or have it already calculated in a database) 2 Calculate the area of the triangle formed by every edge of the cell and the given point (this gives 3 area) If the sum of the 3 area is greater than the area of the cell, the point is outside the domain. If the point is on an edge from the considered cell, one of the triangle (from step 2) will have no area (3 colinear points). If the point is on an edge vertex of the considered cell, two of the triangle (from step 2) will have no area (3 colinear points). If the sum of areas is equal to the cell's area and all triangle have positive area, the given point is inside the given cell. Cycle through each cell to find your answer. This might be inefficient if it is done randomly, but if you have neighbors cell in your mesh database, and have a good first guess, it might be pretty quick. This idea can be carried over to 3D using volumes and faces. 

July 15, 2015, 11:02 

#5  
New Member
Yidong
Join Date: Nov 2011
Posts: 23
Rep Power: 6 
Thanks for your concise explanation of the algorithm! I totally understand it now.
Quote:


July 15, 2015, 11:25 

#6  
Senior Member
Filippo Maria Denaro
Join Date: Jul 2010
Posts: 2,411
Rep Power: 31 
Quote:
yes, this is exactly the method of linear shape function, they define nothing else that the normalized areas defined by a point in a triangle 

July 15, 2015, 11:27 

#7 
Member
Join Date: Jul 2013
Posts: 49
Rep Power: 5 
I would not describe it as 'THE' algorithm. It seems to me that it is 'one of the many' solutions. It is probably not the most efficient one, probably far from it in fact, but it has the large advantage to be pretty straight forward to program.


July 16, 2015, 03:38 

#8 
Senior Member

Usually, for convex polyhedral(polygonal) cells in 3D(2D), a much faster test is the triangle(segment)/segment intersection test between:
1) The segment connecting the given point and the cell centroid and 2) A triangular face of the cell (a face segment in 2D). For polyhedral cells, each face of the cell is usually decomposed in triangles before doing the test (this is usually needed in any case). Looping on the faces of a cell, if no intersection is detected then the point is inside the cell, otherwise you have a pretty good guess for which is the next cell to test (the one from the other side of the intersected face). You might want to find the first cell to test by first putting the cell centroids in a smart data structure like bins (i.e., a structured uniform grid) or an octree. You might also want to implement some smart heuristics so that, during the search (when your first guess is wrong), you do not end up on a boundary with no more guesses (besides the one 'the point is outside the domain'). 

July 16, 2015, 13:12 

#9  
New Member
Yidong
Join Date: Nov 2011
Posts: 23
Rep Power: 6 
I also came across this method in literature search. But thanks a lot for explaining it so clearly here.
Quote:


July 16, 2015, 14:36 

#10  
New Member
Yidong
Join Date: Nov 2011
Posts: 23
Rep Power: 6 
Is there an example algorithm for this part? (e.g., assuming we are dealing with tetrahedron). Thanks
Looping on the faces of a cell, if no intersection is detected then the point is inside the cell, otherwise you have a pretty good guess for which is the next cell to test (the one from the other side of the intersected face). Quote:


July 16, 2015, 18:30 

#11  
Senior Member
Michael Prinkey
Join Date: Mar 2009
Location: Pittsburgh PA
Posts: 257
Rep Power: 15 
Quote:
https://drive.google.com/file/d/0B4F...ew?usp=sharing This was in the context of looking for particles escaping a cell, but it is the same idea. The test line segment would extend from the current cell centroid to the target point. As others have mentioned, if it intersects the face, move to the cell that is on the other side of that face. And just keep walking across the mesh until you find a cell whose centroidtotest point line segment doesn't intersect a face. Then you know you are done. PS. I should note that this algorithm works for general planar faces directly. There is no need to decompose quad/polygon faces into triangles. I haven't seen this algorithm published anywhere, but that is probably only because I haven't looked very hard. 

July 17, 2015, 05:39 

#12  
Senior Member

Quote:
is there. The routines are trivial and with no error handling (mostly because the grid is checked before executing them), so take them just as inspiration (especially the intersection tests). Also, no attempt is made to recover from an erroneous path leading to the mesh boundary and the wrong answer. For example, if at a convex mesh corner there are cells with large differences in sizes, the algorithm, as it is, will probably fail. 

Thread Tools  
Display Modes  


Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Contribution a new utility: refine wall layer mesh based on yPlus field  lakeat  OpenFOAM Mesh Utilities  57  February 1, 2015 09:25 
Point data Or Cell data  chenxizh  ParaView  4  October 28, 2013 08:44 
FvMatrix coefficients  shrina  OpenFOAM Running, Solving & CFD  10  October 3, 2013 14:38 
Cells with t below lower limit  Purushothama  CDadapco  2  May 31, 2010 21:58 
Algorithm to find cell no. in Ogrid for a point  Ben  Main CFD Forum  5  June 22, 2007 11:23 