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

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.

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.

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.

Hi James,

have a look at

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

Hope, this helps.

Regards, Markus

thank you for the link.

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.