Abstract: We describe 5 algorithms for finding the MAT for 2D regions in this paper. There are Danielson's algorithm, Rosenfeld and Pfaltz's algorithm, interpolation/extrapolation algorithm, Newton and march algorithm and grid edge interpolation algorithm. The Rosenfeld and Pfaltz's, Danielson's, and interpolation/extrapolation methods are based on the maximal disc criterion. Whether the grid point (i,j) with distance amplitudes (a,b) to the boundary of the regions is a MA point is decided by its grid neighbors. If the discrete circle associated with the gird point (i,j) is not contained in one of the 8 discrete circles associated with its neighbors, then it is a MA point. The Newton and march and the grid edge interpolation methods are based on the equal distance criterion. Given the boundary of a region, we compute the distance transform for the discretized region as preprocessing step. With every grid point we associate the index of a nearest edge or a concave vertex, and the direction and distance to that edge or concave vertex. The main purpose of these steps is to solve the proximity problem. A system of equations will be generated and Newton method will be used to trace the MAT. If we add one more equation, such as the equation for a grid line, instead of marching MAT step by step, we can find the MA point square by square under some assumptions, this is the idea of grid interpolation method.!9
展开▼
