kneeliverse.menger

 1# coding: utf-8
 2
 3'''
 4The following module provides knee detection method
 5based on menger curvature.
 6'''
 7
 8__author__ = 'Mário Antunes'
 9__version__ = '1.0'
10__email__ = 'mario.antunes@ua.pt'
11__status__ = 'Development'
12__license__ = 'MIT'
13__copyright__ = '''
14Copyright (c) 2021-2023 Stony Brook University
15Copyright (c) 2021-2023 The Research Foundation of SUNY
16'''
17
18import math
19import logging
20import numpy as np
21import kneeliverse.multi_knee as mk
22
23
24logger = logging.getLogger(__name__)
25
26
27def menger_curvature(f:np.ndarray, g:np.ndarray, h:np.ndarray) -> float:
28    """
29    Computes the menger curvature based on three points.
30
31    Args:
32        f (np.ndarray): first point
33        g (np.ndarray): second point
34        h (np.ndarray): third point
35
36    Returns:
37        float: menger curvature
38    """
39    x1 = f[0]
40    y1 = f[1]
41    x2 = g[0]
42    y2 = g[1]
43    x3 = h[0]
44    y3 = h[1]
45
46    nom = 2.0 * math.fabs((x2-x1)*(y3-y2))-((y2-y1)*(x3-x2))
47    temp = math.fabs((x2-x1)**2.0 + (y2-y1)**2.0)*math.fabs((x3-x2)
48    ** 2.0 + (y3-y2)**2.0) * math.fabs((x1-x3)**2.0 + (y1-y3)**2.0)
49    dem = math.sqrt(temp)
50
51    return nom/dem
52
53
54def knee(points: np.ndarray) -> int:
55    """
56    Returns the index of the knee point based on the menger curvature.
57
58    Args:
59        points (np.ndarray): numpy array with the points (x, y)
60
61    Returns:
62        int: the index of the knee point
63    """
64
65    curvature = [0]
66
67    for i in range(1, len(points)-1):
68        f = points[i]
69        g = points[i-1]
70        h = points[i+1]
71
72        curvature.append(menger_curvature(f, g, h))
73
74    curvature.append(0)
75    curvature = np.array(curvature)
76    return np.argmax(curvature)
77
78
79def multi_knee(points: np.ndarray, t1: float = 0.001, t2: int = 4) -> np.ndarray:
80    """Recursive knee point detection based on the menger curvature.
81
82    It returns the knee points on the curve.
83
84    Args:
85        points (np.ndarray): numpy array with the points (x, y)
86        t1 (float): coefficient of determination threshold (default 0.01)
87        t2 (int): number of points threshold (default 4)
88
89    Returns:
90        np.ndarray: knee points on the curve
91    """
92    return mk.multi_knee(knee, points, t1, t2)