
[Sponsors] 
November 13, 2008, 07:11 
Inside Outside Test

#1 
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 pseudocode would be greatly appreciated. Thanks 

November 13, 2008, 09:36 
Re: Inside Outside Test

#2 
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 crossproducts 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 halfspace 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 kd tree approach for nearest neighboring node location. Check for papers on hierarchical data structures in computational geometry. 

November 13, 2008, 09:57 
Oops! ERROR Re: Inside Outside Test

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


November 13, 2008, 22:01 
Re: Inside Outside Test

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

November 14, 2008, 01:20 
Re: Inside Outside Test

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

November 14, 2008, 02:31 
Re: Inside Outside Test

#6 
Guest
Posts: n/a

thank you for the link.


November 18, 2008, 14:30 
Re: Inside Outside Test

#7 
Guest
Posts: n/a

RayCasting 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. 134144, 1989. 

Thread Tools  
Display Modes  


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 