A New Ray-Tracying Acceleration Algorithm Based on Voronoi Diagram

The ray-tracing method is an effective method for indoor location, it can overcome NLOS and multi-path propagation. Because of the low computational efficiency, traditional methods are not widely used. This paper analyzes the main factors affecting the efficiency of the ray-tracing operation, and proposes a new method to improve the efficiency of indoor ray-tracing operation. This method combines ray-tracing and voronoi diagram, uses sphere of influence features and local dynamic characteristics of voronoi diagram. The geometric center of indoor objects are viewed as the growing point, indoor environment is voronoi polygon division, thereby the intersection calculation is reduced between ray and objects. The simulation results show the effectiveness of the method.