Basic geometric algorithms for template based inverse planning

K. Karouzakis and M. Lahanas

* Algorithm that determines whether a point is inside a triangle or rectangle

Given the coordinates (x1,y1,z1), (x2,y2,z2), (x3,y3,z3) of three points P1, P2 and P3, we want to determine whether a given fourth point P0(x0,y0,z0), which lies on the same plane with the other three, is inside the triangle formed by them.

First, we calculate the vectors a = P0 - P1, b = P0 - P2, c =P0 - P3 and after that, the vectors , , . The sum of the above vectors is . We define q1=Q×Q1, q2= Q×Q2, q3= Q×Q3 ÎÂ. The point P0 is inside the triangle (P1, P2, P3) iff q1, q2 and q3 are all positive (q1>0, q2>0 and q3>0). If one of them is zero, P0 is probably on the boundary.



If we have a rectangle instead of a triangle, the method is quite simple: we could divide the rectangle area into two triangles, and apply the point-is-triangle algorithm to both of them. If P0 is on the boundary of both triangles, it must be either inside the rectangle, or on one of the rectangle’s vertices.

* Minimum distance between a point and a linear segment in three-dimensional space



Given the coordinates (x1,y1,z1), (x2,y2,z2) of two points P1 and P2, which define a linear segment, we want to calculate the minimum distance between it and a given point P0(x0,y0,z0). Both P1 and P2 are on the line E defined by P1 and . The projection of point P0 on E is = P1 + t , where . The point is part of P1P2 if and only if , . In this case, the minimum distance is . If is not part of P1P2, the minimum distance is min .

* Minimum distance between a point and a polygon in three-dimensional space

Given the coordinates (x1,y1,z1), (x2,y2,z2),… (xN,yN,zN) of N points P1, P2, .., PN, which lie on the same plane forming a polygon, we want to calculate the minimum distance between the above polygon and a given point P0(x0,y0,z0).

Since in our case the polygon is an organ contour, we assume that all contour points have the same z coordinate, zp=zi, i=1, 2,…, N. The projection of point P0 on the plane z=zp is the point PP0(x0,y0,zp). Now, there are two possibilities: the point PP0 is either inside or outside of the polygon (P1, P2, .., PN). In the first case, the minimum distance between the polygon and P0 is .

In the second case, more calculations have to be done. The minimum distance between the polygon and P0 is equal to the minimum distance between P0 and the closest edge of the polygon, , i=1, 2,…, N.



* Minimum distance between a point and a triangle in three-dimensional space

Given the coordinates (x1,y1,z1), (x2,y2,z2), (x3,y3,z3) of three points P1, P2 and P3, we want to calculate the minimum distance between the triangle formed by them and a given fourth point P0(x0,y0,z0).

The points P1, P2 and P3 define a plane Ax+By+Cz+D=0, where

A=, B=, C=,

and D=-(Ax0+By0+Cz0). The vector ={A,B,C} is perpendicular to that plane.

The projection of P0 on that plane is = P0 + t , where t= If is inside the triangle, the minimum distance between the point P0 and the triangle { P1, P2, P3} is equal to the minimum distance between the point P0 and the plane {A, B, C, D}, that is , or

If is not inside the triangle, the minimum distance is equal to the minimum distance from the closest of the three edges , , of the triangle.

BACK