Как построить параболу между точками при фиксированном интервале, если требуется не более одной точки на интервал и покрытие должно составлять 70%?

Построение параболы с интервалами и ограничениями

Это задача интерполяции: найти плавную кривую (параболу) между заданными точками с соблюдением ограничений на интервалы и покрытие.

Понимание задачи

Условия:

• Фиксированный интервал между точками (X-координата)
• Не более одной точки на интервал
• Покрытие 70% означает, что нужно покрыть 70% от всего диапазона

Пример:

Интервалы:     0-10    10-20    20-30    30-40    40-50
Точки:          ✓               ✓               ✓        (3 точки)
Покрытие:      3/5 * 100 = 60%  (нужно ≥70%)

Решение с использованием полиномиальной интерполяции

import numpy as np
from scipy.interpolate import interp1d, CubicSpline
import matplotlib.pyplot as plt
from typing import List, Tuple

class ParabolaInterpolator:
    """Построение параболы между точками с ограничениями"""
    
    def __init__(self, interval_width: float, min_coverage: float = 0.7):
        """
        Args:
            interval_width: ширина одного интервала
            min_coverage: минимальное покрытие (0.0 - 1.0)
        """
        self.interval_width = interval_width
        self.min_coverage = min_coverage
    
    def validate_coverage(self, points: List[Tuple[float, float]]) -> bool:
        """Проверить, достаточно ли точек для требуемого покрытия"""
        if not points:
            return False
        
        x_values = [p[0] for p in points]
        min_x = min(x_values)
        max_x = max(x_values)
        total_range = max_x - min_x
        
        num_intervals = int(np.ceil(total_range / self.interval_width))
        num_points = len(points)
        coverage = num_points / num_intervals if num_intervals > 0 else 0
        
        return coverage >= self.min_coverage
    
    def build_parabola(self, points: List[Tuple[float, float]]) -> callable:
        """
        Построить параболу (кубический сплайн) через точки
        
        Args:
            points: список (x, y) координат
        
        Returns:
            функция f(x) для получения Y по X
        """
        if len(points) < 3:
            raise ValueError('Нужно минимум 3 точки для построения кривой')
        
        # Проверить покрытие
        if not self.validate_coverage(points):
            raise ValueError(f'Недостаточное покрытие: требуется ≥{self.min_coverage*100}%')
        
        # Сортировать по X
        points_sorted = sorted(points, key=lambda p: p[0])
        x = np.array([p[0] for p in points_sorted])
        y = np.array([p[1] for p in points_sorted])
        
        # Использовать CubicSpline для гладкой кривой
        # (параболу по 2 точкам, кубический сплайн по 3+)
        if len(x) == 2:
            # Линейная интерполяция
            f = interp1d(x, y, kind='linear', fill_value='extrapolate')
        elif len(x) == 3:
            # Квадратичная интерполяция (парабола)
            f = interp1d(x, y, kind='quadratic', fill_value='extrapolate')
        else:
            # Кубический сплайн для 4+ точек
            f = CubicSpline(x, y)
        
        return f
    
    def get_coverage_info(self, points: List[Tuple[float, float]]) -> dict:
        """Получить информацию о покрытии"""
        if not points:
            return {'coverage': 0, 'num_intervals': 0, 'num_points': 0}
        
        x_values = [p[0] for p in points]
        min_x = min(x_values)
        max_x = max(x_values)
        total_range = max_x - min_x
        
        num_intervals = int(np.ceil(total_range / self.interval_width))
        num_points = len(points)
        coverage = num_points / num_intervals if num_intervals > 0 else 0
        
        return {
            'coverage': coverage,
            'coverage_percent': coverage * 100,
            'num_intervals': num_intervals,
            'num_points': num_points,
            'min_x': min_x,
            'max_x': max_x,
            'range': total_range,
            'meets_requirement': coverage >= self.min_coverage
        }

# Пример 1: Основное использование
if __name__ == '__main__':
    # Создать интерполятор
    interpolator = ParabolaInterpolator(
        interval_width=10,
        min_coverage=0.7  # 70%
    )
    
    # Точки (x, y)
    points = [
        (0, 10),
        (15, 25),
        (30, 18),
        (40, 35),
    ]
    
    # Проверить покрытие
    info = interpolator.get_coverage_info(points)
    print(f'Покрытие: {info["coverage_percent"]:.1f}%')
    print(f'Интервалы: {info["num_intervals"]}, Точек: {info["num_points"]}')
    print(f'Требование соблюдено: {info["meets_requirement"]}')
    
    # Построить параболу
    try:
        f = interpolator.build_parabola(points)
        
        # Вычислить значения на кривой
        x_range = np.linspace(0, 40, 100)
        y_range = f(x_range)
        
        # Визуализация
        plt.figure(figsize=(10, 6))
        plt.plot(x_range, y_range, 'b-', label='Интерполированная кривая')
        plt.plot([p[0] for p in points], [p[1] for p in points], 'ro', markersize=8, label='Исходные точки')
        plt.xlabel('X')
        plt.ylabel('Y')
        plt.title('Интерполяция параболой')
        plt.legend()
        plt.grid(True, alpha=0.3)
        plt.show()
    except ValueError as e:
        print(f'Ошибка: {e}')

Пример 2: Оптимальный выбор точек для 70% покрытия

class PointSelector:
    """Выбор оптимальных точек для достижения требуемого покрытия"""
    
    def __init__(self, interval_width: float, min_coverage: float = 0.7):
        self.interval_width = interval_width
        self.min_coverage = min_coverage
    
    def select_points_for_coverage(self, x_min: float, x_max: float) -> List[float]:
        """
        Выбрать X координаты для достижения 70% покрытия
        """
        total_range = x_max - x_min
        num_intervals = int(np.ceil(total_range / self.interval_width))
        num_points_needed = int(np.ceil(num_intervals * self.min_coverage))
        
        # Распределить точки равномерно
        points_x = np.linspace(x_min, x_max, num_points_needed)
        return points_x.tolist()
    
    def generate_synthetic_data(self, x_coords: List[float], noise_level: float = 0) -> List[Tuple[float, float]]:
        """
        Сгенерировать Y значения (например, из модели)
        """
        points = []
        for x in x_coords:
            # Пример: парабола y = 0.5*x^2 - 10*x + 50
            y = 0.5 * x**2 - 10 * x + 50
            # Добавить шум
            if noise_level > 0:
                y += np.random.normal(0, noise_level)
            points.append((x, y))
        return points

# Использование
selector = PointSelector(interval_width=10, min_coverage=0.7)

# Выбрать точки для диапазона 0-50
points_x = selector.select_points_for_coverage(0, 50)
print(f'Выбранные X координаты: {points_x}')
print(f'Количество точек: {len(points_x)}')
print(f'Покрытие: {len(points_x) / 5 * 100:.1f}%')

# Сгенерировать Y значения
points = selector.generate_synthetic_data(points_x, noise_level=2)
print(f'Точки: {points}')

Пример 3: Сравнение методов интерполяции

def compare_interpolation_methods(points: List[Tuple[float, float]]):
    """Сравнить разные методы интерполяции"""
    points_sorted = sorted(points, key=lambda p: p[0])
    x = np.array([p[0] for p in points_sorted])
    y = np.array([p[1] for p in points_sorted])
    
    x_range = np.linspace(x.min(), x.max(), 200)
    
    plt.figure(figsize=(12, 8))
    
    # 1. Линейная интерполяция
    if len(x) >= 2:
        f_linear = interp1d(x, y, kind='linear')
        y_linear = f_linear(x_range)
        plt.subplot(2, 2, 1)
        plt.plot(x_range, y_linear, 'b-', label='Linear')
        plt.plot(x, y, 'ro')
        plt.title('Linear Interpolation')
        plt.grid(True, alpha=0.3)
    
    # 2. Квадратичная интерполяция (парабола)
    if len(x) >= 3:
        f_quadratic = interp1d(x, y, kind='quadratic')
        y_quadratic = f_quadratic(x_range)
        plt.subplot(2, 2, 2)
        plt.plot(x_range, y_quadratic, 'g-', label='Quadratic')
        plt.plot(x, y, 'ro')
        plt.title('Quadratic (Parabola) Interpolation')
        plt.grid(True, alpha=0.3)
    
    # 3. Кубическая интерполяция
    if len(x) >= 4:
        f_cubic = CubicSpline(x, y)
        y_cubic = f_cubic(x_range)
        plt.subplot(2, 2, 3)
        plt.plot(x_range, y_cubic, 'r-', label='Cubic Spline')
        plt.plot(x, y, 'ro')
        plt.title('Cubic Spline Interpolation')
        plt.grid(True, alpha=0.3)
    
    # 4. Полиномиальная интерполяция
    if len(x) >= 2:
        coeffs = np.polyfit(x, y, min(len(x)-1, 5))  # До 5й степени
        poly = np.poly1d(coeffs)
        y_poly = poly(x_range)
        plt.subplot(2, 2, 4)
        plt.plot(x_range, y_poly, 'm-', label='Polynomial')
        plt.plot(x, y, 'ro')
        plt.title(f'Polynomial (degree {len(coeffs)-1})')
        plt.grid(True, alpha=0.3)
    
    plt.tight_layout()
    plt.show()

# Тестовые данные
test_points = [(0, 5), (10, 20), (20, 15), (30, 25), (40, 10)]
compare_interpolation_methods(test_points)

Пример 4: Валидация и обработка ошибок

class RobustParabolaBuilder:
    """Построение параболы с полной валидацией"""
    
    @staticmethod
    def validate_points(points: List[Tuple[float, float]], interval_width: float) -> Tuple[bool, str]:
        """Полная валидация точек"""
        if not points:
            return False, 'Список точек пуст'
        
        if len(points) < 2:
            return False, 'Нужно минимум 2 точки'
        
        # Проверить на дубликаты X координат
        x_values = [p[0] for p in points]
        if len(set(x_values)) != len(x_values):
            return False, 'Дубликаты X координат'
        
        # Проверить интервалы
        sorted_points = sorted(points, key=lambda p: p[0])
        for i in range(len(sorted_points) - 1):
            dist = sorted_points[i+1][0] - sorted_points[i][0]
            if dist < interval_width / 2:
                return False, f'Точки слишком близко: {dist} < {interval_width/2}'
        
        # Проверить Y значения (должны быть числа)
        for x, y in points:
            if not isinstance(y, (int, float)) or np.isnan(y):
                return False, f'Некорректное Y значение: {y}'
        
        return True, 'OK'
    
    @staticmethod
    def build_parabola_safe(points: List[Tuple[float, float]], interval_width: float = 10) -> Tuple[callable, dict]:
        """Безопасное построение параболы с полной диагностикой"""
        # Валидация
        valid, msg = RobustParabolaBuilder.validate_points(points, interval_width)
        if not valid:
            return None, {'error': msg}
        
        try:
            points_sorted = sorted(points, key=lambda p: p[0])
            x = np.array([p[0] for p in points_sorted])
            y = np.array([p[1] for p in points_sorted])
            
            if len(x) == 2:
                f = interp1d(x, y, kind='linear', fill_value='extrapolate')
            elif len(x) == 3:
                f = interp1d(x, y, kind='quadratic', fill_value='extrapolate')
            else:
                f = CubicSpline(x, y)
            
            return f, {'success': True, 'num_points': len(points), 'message': 'Парабола успешно построена'}
        
        except Exception as e:
            return None, {'error': f'Ошибка при построении: {str(e)}'}

# Использование
points = [(0, 10), (15, 25), (30, 20), (45, 30)]
f, info = RobustParabolaBuilder.build_parabola_safe(points, interval_width=10)

if f:
    print(f'Успех: {info}')
    print(f'f(20) = {f(20)}')
else:
    print(f'Ошибка: {info}')

Ключевые моменты

1. Покрытие: num_points / num_intervals ≥ 0.7
2. Интервалы: фиксированная ширина, одна точка максимум
3. Интерполяция: используй CubicSpline для гладких кривых
4. Валидация: проверяй дубликаты, пропуски, NaN значения
5. Экстраполяция: используй fill_value='extrapolate' для выхода за границы