SpiralSort

A point-cloud spiral-sorting algorithm

requirements	optional	os
python3	pillow>=7.0.0	GNU/Linux
click>=7.0	matplotlib>=3.1.3	Windows
numba>=0.48.0	ffmpeg>=4.1.4
numpy>=1.18.0	pytest>=5.4.2
pandas>=1.0.1

Install

$ pip install spiralsort

$ conda install -c mattasa spiralsort

Usage

1. command line

$ spiralsort <file_name> <start_node_id>

2. inside a python script

from spiralsort.core import spiralsorted

point_cloud_spiralsorted = spiralsorted(point_cloud, start_node_id)

3. docker container  

Insert input_file and take the output, using a shared volume between the host and the container.

$ docker pull thanasismatt/spiralsort:latest
$ docker run -it --rm -v ${PWD}:<container_dir> thanasismatt/spiralsort bin/bash
root@<container_id>:/# spiralsort <container_dir>/<file_name> <start_node_id>

Options

-f/--output-format=<format >
(suported: csv, json, xlsx; defaults to the format of the input file)
-a/--save-animation
save an animation of the spiralsorting process (.mp4)

Input/Output format

node_id	x	y	z
N000	1.12	2.32	12.24
N001	1.28	2.64	13.04
...

• File (csv, json) or DataFrame
• node_ids have to be unique
• In case of 2D data, just use a constant value for the 3rd dimension.

Test

$ pytest spiralsort

Under the hood

Starting from the start_node the algorithm evaluates a cost for each node and moves to the
node with the minimum cost (cost for nodeⁱ⁺¹ is the distance from nodeⁱ plus the distance from
the start_node). At each step, a counterclockwise filter is applied, in order to force a constant
rotational direction.

Optimizing the process, a methodology of slicing is applied on the point-cloud, described by the
following steps:

1. Sort the point cloud with respect to the distance from the start node
2. Segment it into slices and take the first slice
3. Take a SPIRAL_WINDOW (slice further)
   Spiral windows for the 1st slice consist of 400 nodes, starting from the last sorted node
   (the start_node for the 1st window)
4. 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 - start_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 start node and ends at the previous node, in order to
   force the algorithm to move on a constant rotating direction.
5. Take the next SPIRAL_WINDOW and pop the next STRIDE.
   
6. Continue until the remainder of the nodes reaches the size of the half slice (1000 nodes for
   the 1st slice).
7. 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.
8. For the next slices, while moving away from the start_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.
9. Keep moving by SPIRAL_WINDOWs, counterclockwise filtering at each stride, popping
   STRIDEs of nodes until the half slice thresshold.
10. Upon reaching the last slice, remove the half_slice threshold, to pop all the remaining nodes.

Animate the process

1. command line

$ spiralsort <file_name> <start_node_id> --save-animation

2. inside a python script

from spiralsort.spiralsort_post import animate

animate(point_cloud_sorted, path_to_input_file)

License

GNU General Public License v3.0

(C) 2020, Athanasios Mattas
thanasismatt@gmail.com