A comparison of two radiological path length algorithms

Most radiation therapy dose calculation methods require the determination of the effective path length of the primary radiation from the radiation source to the point at which the dose is calculated. This usually involves representing the patient anatomy as a set of polygons (contours) as approximations to plane curves. Several algorithms are known for determining the length of a segment or segments on a ray through a planar contour, that are interior to the contour. We have implemented two of these algorithms in a test program to benchmark their relative efficiency. One algorithm uses a linear search over all the contour segments, and the other method represents the contour as a binary tree of "strips," of successively increasing resolution. In general, the tree search should give times proportional to log(n) where n is the number of contour segments, and the linear search time should be proportional to n. Thus, one might expect the tree search to run faster once the number of segments reaches some sufficiently large value. We found that this value is a number of contour points far in excess of that typical for contours representing radiation therapy patient anatomy. Therefore, for this application the linear search method is more efficient.