Euclidean Distance Transform on the Sea Based on Cellular Automata Modeling

Abstract

To explore the problem of distance transformations while obstacles existing, this paper presents an obstacle-avoiding Euclidean distance transform method based on cellular automata. This research took the South China Sea and its adjacent sea areas as an example, imported the data of land-sea distribution and target points, took the length of the shortest obstacle-avoiding path from current cell to the target cells as the state of a cellular, designed the state transform rule of each cellular that considering a distance operator, then simulated the propagation of obstacle-avoiding distance, and got the result raster of obstacle-avoiding distance transform. After analyzing the effect and precision of obstacle avoiding, we reached the following conclusions: first, the presented method can visually and dynamically show the process of obstacle-avoiding distance transform, and automatically calculate the shortest distance bypass the land; second, the method has auto-update mechanism and each cellular can rectify distance value according to its neighbor cellular during the simulation process; at last, it provides an approximate solution for exact obstacle-avoiding Euclidean distance transform and the proportional error is less than 1.96%. The proposed method can apply to the fields of shipping routes design, maritime search and rescue, etc.

Keywords

• |distance transform|cellular automata|obstacles avoiding|south china sea