scikit-image

1
#cython: cdivision=True
2
#cython: boundscheck=False
3
#cython: nonecheck=False
4
#cython: wraparound=False
5
import numpy as np
6

7
cimport numpy as cnp
8
cnp.import_array()
9

10

11
def possible_hull(cnp.uint8_t[:, ::1] img):
12
    """Return positions of pixels that possibly belong to the convex hull.
13

14
    Parameters
15
    ----------
16
    img : ndarray of bool
17
        Binary input image.
18

19
    Returns
20
    -------
21
    coords : ndarray (cols, 2)
22
       The ``(row, column)`` coordinates of all pixels that possibly belong to
23
       the convex hull.
24

25
    """
26
    cdef Py_ssize_t r, c
27
    cdef Py_ssize_t rows = img.shape[0]
28
    cdef Py_ssize_t cols = img.shape[1]
29

30
    # Output: rows storage slots for left boundary pixels
31
    #         cols storage slots for top boundary pixels
32
    #         rows storage slots for right boundary pixels
33
    #         cols storage slots for bottom boundary pixels
34
    coords = np.ones((2 * (rows + cols), 2), dtype=np.intp)
35
    coords *= -1
36

37
    cdef Py_ssize_t[:, ::1] nonzero = coords
38
    cdef Py_ssize_t rows_cols = rows + cols
39
    cdef Py_ssize_t rows_2_cols = 2 * rows + cols
40
    cdef Py_ssize_t rows_cols_r, rows_c
41

42
    with nogil:
43
        for r in range(rows):
44

45
            rows_cols_r = rows_cols + r
46

47
            for c in range(cols):
48

49
                if img[r, c] != 0:
50

51
                    rows_c = rows + c
52
                    rows_2_cols_c = rows_2_cols + c
53

54
                    # Left check
55
                    if nonzero[r, 1] == -1:
56
                        nonzero[r, 0] = r
57
                        nonzero[r, 1] = c
58

59
                    # Right check
60
                    elif nonzero[rows_cols_r, 1] < c:
61
                        nonzero[rows_cols_r, 0] = r
62
                        nonzero[rows_cols_r, 1] = c
63

64
                    # Top check
65
                    if nonzero[rows_c, 1] == -1:
66
                        nonzero[rows_c, 0] = r
67
                        nonzero[rows_c, 1] = c
68

69
                    # Bottom check
70
                    elif nonzero[rows_2_cols_c, 0] < r:
71
                        nonzero[rows_2_cols_c, 0] = r
72
                        nonzero[rows_2_cols_c, 1] = c
73

74
    return coords[coords[:, 0] != -1]
75