Here A* algorithm of path planning is used for generating optimum path for a given 3d Point cloud.
Here pyvista is used for 3d point cloud visualization.
So, install the required python modules:
- Numpy
- pyvista
- odm_georeferenced_model.csv contains point cloud information - X,Y,Z values of about 22 lakhs points
- astar_algo_lib.py contains the A* algorithm code
- 3d_with_sphere_widget.py is the main file that combines all other files.
First clone the repository:
git clone https://github.com/pongthang/astar_path_planning_3d_pc.git
Then run it.
cd astar_path_planning_3d_pc
python3 3d_with_sphere_widget.py
The output of the above should be something like this.
- There will two shperes - green one is for starting point and red one is the endpoint.
- Move the two shperes apart such that they both touch the points in the point cloud.
- Click the checkbox and it will start the path finding.
- Wait for sometimes and you will get the generated path. Then you will see the generated path.
Astar is an algorithm that finds points when connected gives the minimum distance from the source and the destination. It works well for 2d map where there is binary map. Binary map means obstacle and free path can be represented as 0 and 1. So astar alogrithm will apply only in free path.
** Point cloud data is not in matrix form so to apply astar algorithm we need to convert the point cloud data to matrix form first. So the pre-processing of point cloud data is done by "pc_accessories.py".
The above astart algorithm will not work with 3d data points as you can decide a point is obstacle or not according to its height. It should depends on slope. If the slope of a path is steady - not steep then it should be considered as free path. So A new definitions of obstacle and cost are implemented.
In the above diagram , Node means a point in 3d point cloud. So, Node has three properties - position coordinates x,y and height.
MIT LICENSE
Copyright (c)
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.