Quick robust code for point in polygon problem

[bobsta]

Hi,

First apologies for the very general nature of this topic. I am trying to develop a quick robust graphics engine and need to determine whether a point lies inside or outside of a polygon. I typically have 10 or so geometric structures each comprising about 10 or more polygons where each polygon has between 50 and 250 (x,y,z) points per polygon, i.e. maximum of 25000 (float) points(x,y,z) in total. The geometric structures are closed but the individual polygons may be either convex or concave and as such the code must be robust. Additionally the code needs to be fast and easily implemented.

I have done some background reading into this well known problem, and while I can generate my own code to achieve this I don't want to re-invent the wheel unnecessarily.

Is it more efficient to use a ray tracing algorithm with 200x400 points defining the raster of the rays x 25000 points? Or is it better to calculate the sum of internal angles using dot and cross products of vectors between test point q and all polygon vertices.

Thank you in advance. I would really appreciate some guidance with this!

[bobsta]

Okay. I had a stab at the second method based on the psuedo code found here http://www.devmaster.net/forums/showthread.php?t=6483. This does not currently work but hopefully you can see what I am trying to do.

Plane.cpp

bool Plane::insidePolygon(const Point &q, Plane &pPolygon)const{
  int i;
   Vector *vP,*vQ;
   Vector *v0,*vLast,*vI,*vNext;

   float sumDotProduct;
   sumDotProduct=0.0;
   
   // First determine cross product vP between test point q and first and last vertex of Polygon
   
   v0=&(pointToVector(q,pPolygon.pPoint[0]));
   vLast=&(pointToVector(q,pPolygon.pPoint[numPoints-1]));

   vP=&(v0 cross vK);
   
   //Next determine dot product of vP with vQ (cross product of v
   for (i=0;i<numPoints-1;i++){

       vI=&( pointToVector(q,pPolygon.pPoint[i]));

       vNext=&(pointToVector(q,pPolygon.pPoint[i+1]));
   	vQ =&(v cross (vNext));
       
 // Finally check if sum < 0 if yes then outside(false), if not then inside(true)
   	sumDotProduct+=vP dot(vQ);
   }
   
   if (sumDotProduct < 0) return false;
   else return true;
}

Vector.cpp (pointToVector member function returns Vector p2-p1)

Vector Vector::pointToVector(const Point &p1, const Point &p2){ //p1 = (x1,y1,z1) pPoint[k1] and p2 = (x2,y2,z2) pPoint[k2] (next point)

	x=p2.x - p1.x;
	y=p2.y - p1.y;
	z=p2.z - p1.z;

	return Vector(x,y,z);
}

Vector Vector::cross (const Vector *pV)const{
 return Vector (y*pV.z - z*pV.y, x*pV.z - z*pV.x, x*pV.z - z*pV.x);
}

//dot product form p dot(q)
float Vector::dot(const Vector &pV1)const{
	return x*pV1.x +y*pV1.y + z*pV1.z;
}

I need to assign a number of Vector pointers (v0,vI,vLast,vNext,vP and vQ). Is my syntax correct (ll. 11,12,14,19,21 and 22)?

Here are the error messages I receive when trying to compile the static library:

In member function ‘bool Plane::insidePolygon(const Point&, Plane&) const’:
/home/.../Plane.cpp:11: error: ‘pointToVector’ was not declared in this scope
/home/.../Plane.cpp:14: error: expected `)' before ‘cross’
/home/.../Plane.cpp:14: error: cannot convert ‘Vector**’ to ‘Vector*’ in assignment
/home/.../Plane.cpp:22: error: expected `)' before ‘cross’
/home/.../Plane.cpp:22: error: cannot convert ‘Vector**’ to ‘Vector*’ in assignment
/home/.../Plane.cpp:25: error: invalid operands of types ‘float’ and ‘Vector*’ to binary ‘operator+’
/home/.../Plane.cpp:25: error: in evaluation of ‘operator+=(float, class Vector*)’
/home/.../Plane.cpp:25: error: expected `;' before ‘dot’

/home/.../Vector.cpp: In member function ‘float Vector::dot(const Vector*) const’:
/home/.../Vector.cpp:3: error: request for member ‘x’ in ‘pV’, which is of non-class type ‘const Vector*’
/home/.../Vector.cpp:3: error: request for member ‘y’ in ‘pV’, which is of non-class type ‘const Vector*’
/home/.../Vector.cpp:3: error: request for member ‘z’ in ‘pV’, which is of non-class type ‘const Vector*’

/home/.../Vector.cpp: In member function ‘Vector Vector::cross(const Vector*) const’:
/home/.../Vector.cpp:2: error: request for member ‘z’ in ‘pV’, which is of non-class type ‘const Vector*’
/home/.../Vector.cpp:2: error: request for member ‘y’ in ‘pV’, which is of non-class type ‘const Vector*’
/home/.../Vector.cpp:2: error: request for member ‘z’ in ‘pV’, which is of non-class type ‘const Vector*’
/home/.../Vector.cpp:2: error: request for member ‘x’ in ‘pV’, which is of non-class type ‘const Vector*’
/home/.../Vector.cpp:2: error: request for member ‘z’ in ‘pV’, which is of non-class type ‘const Vector*’
/home/.../Vector.cpp:2: error: request for member ‘x’ in ‘pV’, which is of non-class type ‘const Vector*’