test_generate_convex_hull.py

# -*- coding: utf-8 -*-

import unittest

from app.lib.geo import generate_convex_hull


class GenerateConvexHullTest(unittest.TestCase):

    def test_generate_convex_hull_with_degenerate_input(self):
        self.assertRaises(ValueError, generate_convex_hull, None)
        self.assertRaises(ValueError, generate_convex_hull, {})

    def test_generate_convex_hull_with_no_points(self):
        self.assertRaises(ValueError, generate_convex_hull, [])
        self.assertRaises(ValueError, generate_convex_hull, set([]))
        self.assertRaises(ValueError, generate_convex_hull, [None])
        self.assertRaises(ValueError, generate_convex_hull, [None, None])

    def test_generate_convex_hull_with_one_point(self):
        result = generate_convex_hull([(0, 0)])
        assert len(result) == 1 and result == [(0, 0)]
        assert generate_convex_hull([None, (0, 0), None]) == [(0, 0)]

    def test_generate_convex_hull_with_two_points(self):
        points = [(0, 0), (0, 1)]
        result = generate_convex_hull(points)
        assert len(result) == 2 and result == points

    def test_generate_convex_hull_with_more_than_two_unordered_points(self):
        """

        use case with an unordered input. the generated convex hull should be ordered by x and then y

          0 1
        0 * *
        1 *

          0 1
        0 * *
        1 * *

        """
        points = [(0, 1), (1, 0), (0, 0)]
        result = generate_convex_hull(points)
        assert len(result) == 3 and result == [(0, 0), (0, 1), (1, 0)]

        points = [(0, 1), (1, 1), (1, 0), (0, 0)]
        result = generate_convex_hull(points)
        assert len(result) == 4 and result == [(0, 0), (0, 1), (1, 0), (1, 1)]

    def test_generate_convex_hull_with_some_inner_points(self):
        """

        use case with inner points (in this case, we only need 4 points to define the convex hull)

          0 1 2 3
        0 *   * *
        1 *   *
        2     * *
        3 *

        """
        points = [
            (0, 0),         (2, 0), (3, 0),
            (0, 1),         (2, 1),
                            (2, 2), (3, 2),
            (0, 3)
        ]
        expected = [
            (0, 0),                 (3, 0),

                                    (3, 2),
            (0, 3)
        ]
        assert generate_convex_hull(points) == sorted(expected)

    def test_generate_convex_hull_with_a_full_square(self):
        """

        use case with a full square (only the 4 corners should be returned)

          0 1 2 3
        0 * * * *
        1 * * * *
        2 * * * *
        3 * * * *

        """
        points = [
            (0, 0), (1, 0), (2, 0), (3, 0),
            (0, 1), (1, 1), (2, 1), (3, 1),
            (0, 2), (1, 2), (2, 2), (3, 2),
            (0, 3), (1, 3), (2, 3), (3, 3)
        ]
        expected = [
            (0, 0),                 (3, 0),


            (0, 3),                 (3, 3),
        ]
        assert generate_convex_hull(points) == sorted(expected)