Generating_Convex_Polytopes

Generate collision-free convex polyhedrons in Point Cloud Map：

IRIS

Figure 1 shows a partial demonstration of the IRIS algorithm. (R. Deits and R. Tedrake 2015).

• Need multiple iterations

Safe Flight Corridors

Figure 2 shows a partial demonstration of the SFC algorithm. (S. Liu, M. Watterson, K. Mohta, K. Sun, S. Bhattacharya, C.J. Taylor, and Vijay Kumar 2017).

• Need two points

Stereographic Projection method

Figure 3 shows a partial demonstration of the algorithm. (S. Savin 2017).

• Need to calculate the convex hull algorithm (the smallest convex shape enclosing a given shape)
• The size of the Star polyhedron depends heavily on the point chosen at the beginning.

Sphere Flipping method

Figure 4 shows a partial demonstration of the algorithm. (Xingguang Zhong, Yuwei Wu, Dong Wang, Qianhao Wang, Chao Xu, and Fei Gao 2020).

• Need to calculate the convex hull algorithm (the smallest convex shape enclosing a given shape)
• The size of the Star polyhedron depends heavily on the point chosen at the beginning.

---

Reference

• [1] R. Deits and R. Tedrake, "Computing large convex regions of obstacle-free space through semidefinite programming",in Algorithmic Foundations of Robotics XI. Berlin, Germany: Springer, 2015, pp. 109–124.
• [2] S. Liu, M. Watterson, K. Mohta, K. Sun, S. Bhattacharya, C.J. Taylor, et al., "Planning dynamically feasible trajectories for quadrotors using safe flight corridors in 3-d complex environments", IEEE Robotics and Automation Let- ters, vol. 2, no. 3, pp. 1688-1695, July 2017.
• [3] S. Savin, "An algorithm for generating convex obstacle-free regions based on stereographic projection,” in International Siberian Confer- ence on Control and Communications", 2017.
• [4] Xingguang Zhong, Yuwei Wu, Dong Wang, Qianhao Wang, Chao Xu, and Fei Gao, "Generating Large Convex Polytopes Directly on Point Clouds",2020