Repository: arvkevi/kneed

Issue:
KneeLocator fails if there are flat extrema
This simple example fails:

```python
from kneed import KneeLocator
x = [0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0, 17.0]
y = [1, 0.787701317715959, 0.7437774524158126, 0.6559297218155198, 0.5065885797950219, 0.36749633967789164, 0.2547584187408492, 0.16251830161054173, 0.10395314787701318, 0.06734992679355783, 0.043923865300146414, 0.027818448023426062, 0.01903367496339678, 0.013177159590043924, 0.010248901903367497, 0.007320644216691069, 0.005856515373352855, 0.004392386530014641]
k = KneeLocator(x, y, curve='convex', direction='decreasing')
```
Output:
`UserWarning: No knee/elbow found`

However, if we obtain the normalized knee plot, it is clear that there is a "flat optimum".

![knee](https://user-images.githubusercontent.com/4498106/69006397-0332df80-092f-11ea-96b3-4156ce026ea8.png)

It seems that the algorithm should be able to find that point between 0.4 and 0.5. 

I've been able to workaround this issue by modifying `knee_locator.py` in the calculation of `self.maxima_indices` and `self.minima_indices`, by using `np.greater_equal` and `np.less_equal` rather than `np.great` and `np.less`, but I'm not sure if this is a proper solution.

Thanks!

Discussion:

Patch:
diff --git a/kneed/knee_locator.py b/kneed/knee_locator.py
index 82412bc..c8c1954 100644
--- a/kneed/knee_locator.py
+++ b/kneed/knee_locator.py
@@ -81,12 +81,12 @@ class KneeLocator(object):
 
         # Step 4: Identify local maxima/minima
         # local maxima
-        self.maxima_indices = argrelextrema(self.y_difference, np.greater)[0]
+        self.maxima_indices = argrelextrema(self.y_difference, np.greater_equal)[0]
         self.x_difference_maxima = self.x_difference[self.maxima_indices]
         self.y_difference_maxima = self.y_difference[self.maxima_indices]
 
         # local minima
-        self.minima_indices = argrelextrema(self.y_difference, np.less)[0]
+        self.minima_indices = argrelextrema(self.y_difference, np.less_equal)[0]
         self.x_difference_minima = self.x_difference[self.minima_indices]
         self.y_difference_minima = self.y_difference[self.minima_indices]
 
diff --git a/kneed/version.py b/kneed/version.py
index 3d18726..dd9b22c 100644
--- a/kneed/version.py
+++ b/kneed/version.py
@@ -1,1 +1,1 @@
-__version__ = "0.5.0"
+__version__ = "0.5.1"


Test patch:
diff --git a/tests/test_sample.py b/tests/test_sample.py
index f82e9e8..8c3f160 100644
--- a/tests/test_sample.py
+++ b/tests/test_sample.py
@@ -151,3 +151,19 @@ def test_list_input():
     x, y = dg.figure2()
     kl = KneeLocator(x.tolist(), y.tolist(), S=1.0, curve='concave', interp_method='polynomial')
     assert math.isclose(kl.knee, 0.22, rel_tol=0.05)
+
+
+def test_flat_maxima():
+    """The global maxima has a sequentially equal value in the difference curve"""
+    x = [0, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, 11.0, 12.0, 13.0, 14.0, 15.0, 16.0, 17.0]
+    y = [1, 0.787701317715959, 0.7437774524158126, 0.6559297218155198, 0.5065885797950219, 0.36749633967789164,
+         0.2547584187408492, 0.16251830161054173, 0.10395314787701318, 0.06734992679355783, 0.043923865300146414,
+         0.027818448023426062, 0.01903367496339678, 0.013177159590043924, 0.010248901903367497, 0.007320644216691069,
+         0.005856515373352855, 0.004392386530014641]
+    # When S=0.0 the first local maximum is found.
+    kl = KneeLocator(x, y, curve='convex', direction='decreasing', S=0.0)
+    assert math.isclose(kl.knee, 1.0, rel_tol=0.05)
+
+    # When S=1.0 the global maximum is found.
+    kl = KneeLocator(x, y, curve='convex', direction='decreasing', S=1.0)
+    assert math.isclose(kl.knee, 8.0, rel_tol=0.05)