A point-cloud spiral-sorting algorithm
Project description
SpiralSort
A point-cloud spiral-sorting algorithm
requirements | optional | os |
---|---|---|
python3 | matplotlib >= 3.1.3 | GNU/Linux |
click>=7.0 | ffmpeg>=4.1.4 | Windows |
numpy >= 1.18.0 | ||
pandas >= 1.0.1 |
How to use
- command line
$ spiralsort <file_name> <master_node_id>
- inside a python script
from spiralsort.core import spiralsort
point_cloud_sorted = spiralsort(point_cloud, master_node_id)
How to istall
$ pip install spiralsort
Input/Output file (or DataFrame) format
supported formats: csv, json
node_id | x | y | z |
---|---|---|---|
N000 | 1.12 | 2.32 | 12.24 |
N001 | 1.28 | 2.64 | 13.04 |
... |
- node_ids have to be unique
- In case of 2D data, just use a constant value for the 3rd dimension.
How it works
Starting from the master_node the algorithm evaluates a cost for each node and
moves to the
node with the minimum cost (cost for nodei+1 is
the distance from nodei plus the distance from
the
master_node).
Optimizing the process, a methodology of slicing is applied on the point-cloud,
described by the
following steps:
- Sort the point cloud with respect to the distance from the master node
- Segment it into slices and take the first slice
- Take a SPIRAL_WINDOW (slice further)
Spiral windows for the 1st slice consist of 400 nodes, starting from the last sorted node
(the master_node for the 1st window) - Iteretively pop 15 nodes (a STRIDE), by the minimum cost. Namely, a
SPIRAL_WINDOW is
sliced to spiralsort a STRIDE of nodes, before moving to the next SPIRAL_WINDOW.
(cost = |node - master_node| + |node - prev_node|)
At each iterative step, a filter is applied, keeping only nodes from the counterclockwise side
of the vector that starts from the master node and ends at the previous node, in order to
force the algorithm to move on a constant rotating direction. - Take the next SPIRAL_WINDOW and pop the next STRIDE.
- Continue until the remainder of the nodes reaches the size of the
half slice (1000 nodes for
the 1st slice). - Merge the remaining nodes with the next slice
This overlap of the slices ensures that there is a continuity while selecting the next nodes,
when the algorithm reaches the last nodes of the slice. - For the next slices, while moving away from the master_node, the
SPIRAL_WINDOW is
selected differently. Specifically, before each STRIDE, the counterclockwise filter is applied,
then the remaining nodes are cost-sorted (with respect to their cost) from the last
spiralsorted node and, finally, a SPIRAL_WINDOW is sliced, to start the iterative spiralsorting
of the nodes in the next STRIDE. - Keep moving by SPIRAL_WINDOWs, counterclockwise
filtering at each stride, popping
STRIDEs of nodes until the half slice thresshold. - Upon reaching the last slice, remove the half_slice threshold, to pop all the remaining nodes.
Options
--output-format=<format >
(suported: csv, json, xlsx; defaults to the format of the input
file)
--save-animation/--no-save-animation
(defaults to false)
How to create an animation of the process
- command line
$ spiralsort <file_name> <master_node_id> --save-animation
- inside a python script
from spiralsort.spiralsort_post import save_animation
save_animation(point_cloud_sorted, path_to_input_file)
(C) 2020, Thanasis Mattas
atmattas@physics.auth.gr
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for spiralsort-0.1.0-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 78b0598fe02aba323bb1dd261a4b49083f389adcc1d10afdd352523b4d08d3c6 |
|
MD5 | dd254f9ad21839ec7ee9b3938429c634 |
|
BLAKE2b-256 | e1de1f6ab5116169932db205513362e625f165ca30c1a44e13ffd78d27272bec |