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

Inside Outside Test

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

Reply
 
LinkBack Thread Tools Display Modes
Old   November 13, 2008, 07:11
Default Inside Outside Test
  #1
James
Guest
 
Posts: n/a
Hi there,

Could you please tell me, what is the most efficient method of determining if a given point (xp, yp) lies inside a given cell or not. The cell is a four sided polygon. The x, y coordinates of the four corners of the polygon are known. A method that is easily expandable to 3D at a later date would be preferable.

Any snippets of pseudo-code would be greatly appreciated.

Thanks
  Reply With Quote

Old   November 13, 2008, 09:36
Default Re: Inside Outside Test
  #2
Ananda Himansu
Guest
 
Posts: n/a
I assume that the quadrilateral is geometric and not just topological, so that the sides are straight. Curved sides introduce a much higher level of complexity.

(1) It helps if you can be sure from the provenance of the cell that it is convex. If not, split the cell into simplices (triangles), which are guaranteed to be convex in any number of dimensions. You have to split the quadrilateral along the correct diagonal, so that both resulting triangles contribute areas of the same sign to the total area of the quadrilateral. This will involve cross-products of the vectors formed by the sides of the cell, keeping a consistent ordering of vertices. At the end of this step you will have a partition of the quad into two triangles, each of which contains only points that are contained in the quad.

(2) Next, all that remains is to check if your given point (xp, yp) lies in either of the two trianles from step (1). If it does not lie in either of them, then it is exterior to the quad.

An alternative to steps (1) and (2) above is the following. Split the quad along one diagonal to obtain two triangles A and B. Split the quad along the other diagonal to obtain two more triangles C and D. Now you have four overlapping triangles A, B, C and D. Check whether your given point (xp, yp) belongs to each of A, B, C, D. If it is contained in two of the triangles, then it is contained in the quad. If on the other hand, it is contained in one or none of the four triangles, then it is exterior to the quad. I have not thought through this alternative method very carefully, so you had better make sure it is watertight before using.

Now all that remains is the question of how you determine whether (xp, yp) lies inside or outside a triangle under consideration. Examine each of the three sides in a loop. For each side form a normal vector. Using the sign of inner (dot) products with this normal vector, check whether (xp, yp) and the vertex opposite to the side are on the same or opposite sides of the current side. This is the same as the half-space concept in computational geometry and computer graphics. If the two points are on opposite sides of the current side, exit the loop because (xp, yp) is exterior to the triangle. Note that your test should account for the case when (xp, yp) is actually on the current side. If (xp, yp) is on the same side as the opposite vertex for all three sides (i.e., the loop is normally completed), then it is contained in the triangle.

As further remarks, if you have to scan through a few million quads to determine whether (xp, yp) lies in any of them, or even worse, if you have many candidate points (xp, yp) to locate in a mesh of millions of quads, then you do not want to repeat the above procedure for every single quad and every single (xp, yp). If the mesh is static, then you should use a hierarchical indexing of the triangles (you only have to index once) to efficiently locate the triangle containing the given point (xp, yp). This will give you an algorithm which has a run time of O(log nc) rather than O(nc), where nc is the number of triangles. The hierarchical approach is similar to the k-d tree approach for nearest neighboring node location. Check for papers on hierarchical data structures in computational geometry.
  Reply With Quote

Old   November 13, 2008, 09:57
Default Oops! ERROR Re: Inside Outside Test
  #3
Ananda Himansu
Guest
 
Posts: n/a
Disregard the paragraph about the "alternative" method mentioned after steps (1) and (2), involving the four triangles A, B, C, D. I just thought of a simple counterexample where an exterior point is contained in two of the triangles. The rest of the post is correct, I coded this up (except for the hierarchical search tree) a few years ago. When using dot products with the normal vector to a given side, you can use the vertex at either end of the side as the local origin to form vectors. The entire algorithm sounds complex, but in practice it can be distilled down to very few lines of code.
  Reply With Quote

Old   November 13, 2008, 22:01
Default Re: Inside Outside Test
  #4
inside-out
Guest
 
Posts: n/a
i have been thinking about this issue, and this is one method i am leaning towards.

take the point in question, calculate its signed distance from all the sides of this polygon. If the point is inside all the signs of this signed distances will match. If this condision does not hold than it is outside of polygon.

(this method shall work well with normal polygons, i am not sure how it will work with distorted polygons.

  Reply With Quote

Old   November 14, 2008, 01:20
Default Re: Inside Outside Test
  #5
Markus Lummer
Guest
 
Posts: n/a
Hi James,

have a look at

http://www.ecse.rpi.edu/Homepages/wr...es/pnpoly.html

Hope, this helps.

Regards, Markus
  Reply With Quote

Old   November 14, 2008, 02:31
Default Re: Inside Outside Test
  #6
inside-out
Guest
 
Posts: n/a
thank you for the link.
  Reply With Quote

Old   November 18, 2008, 14:30
Default Re: Inside Outside Test
  #7
Munikrishna Nagaram
Guest
 
Posts: n/a
Ray-Casting Algorithm is widely used for inside/outside problem. Have a look at the paper:

Milgram M.S., "Does a point lie inside a polygon?", Journal of Computational Physics, Volume 84, pp. 134-144, 1989.

  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
critical error during installation of openfoam Fabio88 OpenFOAM Installation 21 June 2, 2010 03:01
OF 1.6 | Ubuntu 9.10 (64bit) | GLIBCXX_3.4.11 not found piprus OpenFOAM Installation 22 February 25, 2010 14:43
OpenFOAM on MinGW crosscompiler hosted on Linux allenzhao OpenFOAM Installation 127 January 30, 2009 20:08
Modelling the Heat flow inside the curing oven Marios Vlad CFX 1 February 6, 2008 08:11
meshing F1 front wing Steve FLUENT 0 April 17, 2003 12:37


All times are GMT -4. The time now is 14:25.