Coverage for src / min_circle / msk.py: 25%

1"""MOSEK implementation for finding the minimum enclosing circle. 

2 

3This module provides functions to find the minimum enclosing circle 

4using the MOSEK Fusion optimization library. 

5 

6Note: 

7 The MOSEK dependency is optional. Importing this module no longer requires 

8 MOSEK to be installed. The import happens lazily inside the solver function. 

9""" 

10 

11from typing import Any 

12 

13import numpy as np 

14 

15from .utils.circle import Circle 

16 

17 

18def min_circle_mosek(points: np.ndarray, **kwargs: Any) -> Circle: 

19 """Find the minimum enclosing circle using MOSEK Fusion. 

20 

21 Uses the MOSEK Fusion API to formulate and solve the minimum enclosing circle 

22 problem as a second-order cone program (SOCP). 

23 

24 Args: 

25 points: Array of 2D points with shape (n, 2) 

26 **kwargs: Additional keyword arguments to pass to the solver 

27 

28 Returns: 

29 Circle object containing the center and radius of the minimum enclosing circle 

30 

31 Raises: 

32 ImportError: If the `mosek` package is not installed. Install with 

33 `pip install 'min_circle[solvers]'` or add the `solvers` extra. 

34 

35 Notes: 

36 Implementation based on MOSEK's minimum ellipsoid tutorial: 

37 https://github.com/MOSEK/Tutorials/blob/master/minimum-ellipsoid/minimum-ellipsoid.ipynb 

38 """ 

39 try: 

40 import mosek.fusion as mf # type: ignore 

41 except Exception as exc: # pragma: no cover - only hit when MOSEK is missing 

42 raise ImportError( 

43 "MOSEK is required for min_circle_mosek(). Install with `pip install 'min_circle[solvers]'` " 

44 "or install the `mosek` package manually." 

45 ) from exc 

46 

47 with mf.Model() as model: 

48 # Create variables for radius and center 

49 r = model.variable("Radius", 1) 

50 x = model.variable("Midpoint", [1, points.shape[1]]) 

51 

52 # Number of points 

53 k = points.shape[0] 

54 

55 # Repeat the radius and center variables for each point 

56 r0 = mf.Var.repeat(r, k) 

57 x0 = mf.Var.repeat(x, k) 

58 

59 # Create second-order cone constraints ensuring all points are within the circle 

60 model.constraint(mf.Expr.hstack(r0, mf.Expr.sub(x0, points)), mf.Domain.inQCone()) 

61 

62 # Set the objective to minimize the radius 

63 model.objective("obj", mf.ObjectiveSense.Minimize, r) 

64 

65 # Solve the optimization problem 

66 model.solve(**kwargs) 

67 

68 # Return the circle with the optimal center and radius 

69 return Circle(radius=r.level(), center=x.level())