# Path: spyce/analysis.py
# def golden_section_search(f, a, b, tolerance=0):
#     """Golden section search
# 
#     Look for a minima of unimodal function `f` within `(a, b)`"""
#     # golden_ratio = (math.sqrt(5) + 1) / 2
#     golden_ratio = 1.618033988749895
# 
#     old_a, old_b = a, b
#     for _ in range(54):
#         c = b - (b - a) / golden_ratio
#         d = a + (b - a) / golden_ratio
#         fc = f(c)
#         if abs(fc) < tolerance:
#             return c
#         if fc < f(d):
#             b = d
#         else:
#             a = c
# 
#     if a == old_a or b == old_b:
#         return None
#     return (b + a) / 2
# 
# def bisection_method(f, a, b):
#     """Bisection method
# 
#     Look for a root of `f` in [a, b]"""
#     fa = f(a)
#     for _ in range(54):
#         c = (a + b) / 2
#         fc = f(c)
#         if fa*fc >= 0:
#             # f(a) and f(c) have the same sign
#             a, fa = c, fc
#         else:
#             # f(a) and f(c) have opposite signs
#             b = c
#     return a


import math
from spyce.analysis import golden_section_search, bisection_method
                return None
        if target.eccentricity < 1:
            if self.periapsis - target.apoapsis > tolerance:
                return None

        def f(t):
            """Distance between the two objects at given time"""
            return (target.position_at_time(t)-self.position_at_time(t)).norm()
        # Although the distance is not strictly unimodal on a half-period,
        # golden section search works because f has at most one real local
        # minimum on a half-period.
        time = golden_section_search(f, t, t+self.period/2, tolerance)
        if time is None or f(time) > tolerance:
            return None
        return time

    def time_at_next_encounter(self, target, t, encounter_radius):
        """Search for an encounter for half a period"""
        # first, find near approach with just enough precision
        next_approach = self.time_at_next_approach(target, t, encounter_radius)
        if next_approach is None:
            return math.inf

        # second, search for time of encounter
        def f(t):
            """Distance before encounter"""
            # distance between the two objects at given time
            d = (target.position_at_time(t)-self.position_at_time(t)).norm()
            # distance to encounter
            return d - encounter_radius

# Path: spyce/analysis.py
# def golden_section_search(f, a, b, tolerance=0):
#     """Golden section search
# 
#     Look for a minima of unimodal function `f` within `(a, b)`"""
#     # golden_ratio = (math.sqrt(5) + 1) / 2
#     golden_ratio = 1.618033988749895
# 
#     old_a, old_b = a, b
#     for _ in range(54):
#         c = b - (b - a) / golden_ratio
#         d = a + (b - a) / golden_ratio
#         fc = f(c)
#         if abs(fc) < tolerance:
#             return c
#         if fc < f(d):
#             b = d
#         else:
#             a = c
# 
#     if a == old_a or b == old_b:
#         return None
#     return (b + a) / 2
# 
# def bisection_method(f, a, b):
#     """Bisection method
# 
#     Look for a root of `f` in [a, b]"""
#     fa = f(a)
#     for _ in range(54):
#         c = (a + b) / 2
#         fc = f(c)
#         if fa*fc >= 0:
#             # f(a) and f(c) have the same sign
#             a, fa = c, fc
#         else:
#             # f(a) and f(c) have opposite signs
#             b = c
#     return a


# Path: spyce/orbit_target.py
import math
from spyce.analysis import golden_section_search, bisection_method

                return None
        if target.eccentricity < 1:
            if self.periapsis - target.apoapsis > tolerance:
                return None

        def f(t):
            """Distance between the two objects at given time"""
            return (target.position_at_time(t)-self.position_at_time(t)).norm()
        # Although the distance is not strictly unimodal on a half-period,
        # golden section search works because f has at most one real local
        # minimum on a half-period.
        time = golden_section_search(f, t, t+self.period/2, tolerance)
        if time is None or f(time) > tolerance:
            return None
        return time

    def time_at_next_encounter(self, target, t, encounter_radius):
        """Search for an encounter for half a period"""
        # first, find near approach with just enough precision
        next_approach = self.time_at_next_approach(target, t, encounter_radius)
        if next_approach is None:
            return math.inf

        # second, search for time of encounter
        def f(t):
            """Distance before encounter"""
            # distance between the two objects at given time
            d = (target.position_at_time(t)-self.position_at_time(t)).norm()
            # distance to encounter
            return d - encounter_radius

        return bisection_method(f, t, next_approach)