Skip to main content

A point-cloud spiral-sorting algorithm

Project description

SpiralSort

PyPI Build Status codecov

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

How to use

  1. command line
$ spiralsort <file_name> <start_node_id>
  1. inside a python script
from spiralsort.core import spiralsorted

point_cloud_spiralsorted = spiralsorted(point_cloud, start_node_id)
  1. docker container   Docker Cloud Build Status

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>

How to install

$ pip install spiralsort
$ conda install -c mattasa 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 start_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 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.

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

  1. command line
$ spiralsort <file_name> <start_node_id> --save-animation
  1. inside a python script
from spiralsort.spiralsort_post import animate

animate(point_cloud_sorted, path_to_input_file)

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

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

spiralsort-0.3.0.tar.gz (17.4 kB view details)

Uploaded Source

Built Distribution

spiralsort-0.3.0-py3-none-any.whl (33.3 kB view details)

Uploaded Python 3

File details

Details for the file spiralsort-0.3.0.tar.gz.

File metadata

  • Download URL: spiralsort-0.3.0.tar.gz
  • Upload date:
  • Size: 17.4 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.2.0 pkginfo/1.6.1 requests/2.24.0 setuptools/46.1.3.post20200330 requests-toolbelt/0.9.1 tqdm/4.52.0 CPython/3.8.2

File hashes

Hashes for spiralsort-0.3.0.tar.gz
Algorithm Hash digest
SHA256 24ed75e6647c59fa791b87d61aeef7aa806065150f51f6e41baca9d5b557daa9
MD5 7b1b4f10f85cdda1d4d1aaefeee69ab2
BLAKE2b-256 6b3702e5d51389550125d18740e481c11f413fe9aa85224d9966681e3ebc6ad1

See more details on using hashes here.

File details

Details for the file spiralsort-0.3.0-py3-none-any.whl.

File metadata

  • Download URL: spiralsort-0.3.0-py3-none-any.whl
  • Upload date:
  • Size: 33.3 kB
  • Tags: Python 3
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/3.2.0 pkginfo/1.6.1 requests/2.24.0 setuptools/46.1.3.post20200330 requests-toolbelt/0.9.1 tqdm/4.52.0 CPython/3.8.2

File hashes

Hashes for spiralsort-0.3.0-py3-none-any.whl
Algorithm Hash digest
SHA256 76ff2e30618374819c9caa8883fbd82dc1c308f452ddc4c7d1e5a94aa38d0a18
MD5 c1bb602fb8dc7a3e539331ab879a2771
BLAKE2b-256 d245917edf3cd42840c301577449a079b81bfebef4e734bbaebd12277ab18d3f

See more details on using hashes here.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Pingdom Monitoring Sentry Error logging StatusPage Status page