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

Algorithm to find cell no. in O-grid for a point

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

Reply
 
LinkBack Thread Tools Display Modes
Old   June 21, 2007, 00:57
Default Algorithm to find cell no. in O-grid for a point
  #1
Ben
Guest
 
Posts: n/a
Hi,

I am looking for an effective algorithm which can determine the i,j cell number of a point on an O-grid.

Can someone enlighten me?

Thanks
  Reply With Quote

Old   June 21, 2007, 08:50
Default Re: Algorithm to find cell no. in O-grid for a poi
  #2
Mani
Guest
 
Posts: n/a
How is the point defined? By physical coordinates?

The (in)efficiency of any search algorithm will depend on how general it needs to be. Your question implies a 2D grid. Are there any other conditions that may help to specify the problem?
  Reply With Quote

Old   June 21, 2007, 09:49
Default Re: Algorithm to find cell no. in O-grid for a poi
  #3
Ben
Guest
 
Posts: n/a
Hi,

put it simply, I have a pt with coordinates (x,y). I also have an O-grid, in a 2D array xx(i,j), yy(i,j). There's no transformation and they'r all physical coordinates.

So I want to find the i,j cell on the O-grid where the pt (x,y) lies in. I am now looping through the O-grid cells, and check if the pt lies inside the cell (quadrilateral).

I am using overset grids so I'm trying to find the interpolation stencil for the cartesian pt on the O-grid.

Thanks
  Reply With Quote

Old   June 21, 2007, 13:37
Default Re: Algorithm to find cell no. in O-grid for a poi
  #4
TG
Guest
 
Posts: n/a
What you need to do to speed up the process is create a set of zones covering the extent of the mesh, place each cell into a the zone (or zones) it falls into geometrically and then only search the cells in the zone that your point falls in to see if its in or out. You can experiment, but a 10x10 covering the 2-d mesh will probably speed you up a couple of orders of magnitude.
  Reply With Quote

Old   June 21, 2007, 13:54
Default Re: Algorithm to find cell no. in O-grid for a poi
  #5
Mani
Guest
 
Posts: n/a
Ok, I assume you are looping in some arbitrary order through the whole grid, and check each cell until you've found the right one. One way to speed it up (a lot) is to use a quad search. Split your grid into four equal parts. Then check each of the four subgrids for inclusion of your point. You do this with a simplified definition of the subgrid boundaries, e.g. in the simplest case you would define a subgrid only by its 4 vertices (as if the whole grid consisted of 4 huge cells). Once you found the right quad, you divide it into 4 parts again, and keep going in this way until you have arrived at the grid cell level and found the right cell. It's hard to describe but I think you get the idea. It's somewhat analogous to the "multigrid" idea. Start with the coarsest grid and work your way down to the actual resolution. In the general case, this will speed up your search enormously. For example, for a grid size of 512*512 cells, the simple search will take up to 262144 evaluations. The quad search will take at most 36 evaluations! One thing to keep in mind though: You'll need to be a little careful with the evaluations on the coarse grids. They will not be exact if you only use 4 vertices and assume straight cell faces. However, even with some extra care, the quad search is a lot faster than the simple approach. It can be elegantly programmed as a recursive procedure. It's ideal if your grid size is in powers of 2, but you can make it work on any grid (the four parts don't have to be of equal size).

Once you've got that working you may also think about successful strategies to optimize your starting position. For example, if you have already found one point, the next node of your overset grid is not going to be far away. Search in the vicinity!

  Reply With Quote

Old   June 22, 2007, 11:23
Default Re: Algorithm to find cell no. in O-grid for a poi
  #6
Ben
Guest
 
Posts: n/a
Thank you TG & Mani for the suggestions!
  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
LES- first grid point in boundary layer, y+ sina Main CFD Forum 0 February 3, 2011 10:26
how to calculate flow properties along the first grid point near to the wall kiran OpenFOAM Post-Processing 2 September 12, 2010 12:59
UDF to define source term at every grid point Ralf Schmidt FLUENT 0 September 21, 2006 11:32
select grid cell Domi FLUENT 0 October 26, 2004 11:01
CFX4.3 -build analysis form Chie Min CFX 5 July 12, 2001 23:19


All times are GMT -4. The time now is 06:29.