Как построить алгоритм классификации точек, принадлежащих различным типам фигур, при произвольном количестве экземпляров каждой фигуры?

Классификация точек по типам геометрических фигур

Это сложная задача computational geometry + machine learning. Решение зависит от того, есть ли у нас обучающий набор или нужно это делать в реальном времени.

1. Знаемая конфигурация фигур

Если мы знаем где находятся фигуры (их параметры), используем геометрическую классификацию:

from dataclasses import dataclass
from typing import List, Literal
from abc import ABC, abstractmethod
import math

@dataclass
class Point3D:
    x: float
    y: float
    z: float

class Shape(ABC):
    @abstractmethod
    def contains(self, point: Point3D) -> bool:
        pass
    
    @abstractmethod
    def distance_to(self, point: Point3D) -> float:
        pass
    
    @abstractmethod
    def get_type(self) -> str:
        pass

class Sphere(Shape):
    def __init__(self, center: Point3D, radius: float):
        self.center = center
        self.radius = radius
    
    def contains(self, point: Point3D) -> bool:
        dist_sq = (
            (point.x - self.center.x) ** 2 +
            (point.y - self.center.y) ** 2 +
            (point.z - self.center.z) ** 2
        )
        return dist_sq <= self.radius ** 2
    
    def distance_to(self, point: Point3D) -> float:
        dist = math.sqrt(
            (point.x - self.center.x) ** 2 +
            (point.y - self.center.y) ** 2 +
            (point.z - self.center.z) ** 2
        )
        return max(0, dist - self.radius)
    
    def get_type(self) -> str:
        return "sphere"

class Cube(Shape):
    def __init__(self, min_corner: Point3D, max_corner: Point3D):
        self.min = min_corner
        self.max = max_corner
    
    def contains(self, point: Point3D) -> bool:
        return (
            self.min.x <= point.x <= self.max.x and
            self.min.y <= point.y <= self.max.y and
            self.min.z <= point.z <= self.max.z
        )
    
    def distance_to(self, point: Point3D) -> float:
        dx = max(0, self.min.x - point.x, point.x - self.max.x)
        dy = max(0, self.min.y - point.y, point.y - self.max.y)
        dz = max(0, self.min.z - point.z, point.z - self.max.z)
        return math.sqrt(dx**2 + dy**2 + dz**2)
    
    def get_type(self) -> str:
        return "cube"

class Cylinder(Shape):
    def __init__(self, center: Point3D, radius: float, height: float, axis: str = 'z'):
        self.center = center
        self.radius = radius
        self.height = height
        self.axis = axis
    
    def contains(self, point: Point3D) -> bool:
        if self.axis == 'z':
            radial_dist_sq = (point.x - self.center.x)**2 + (point.y - self.center.y)**2
            height_ok = abs(point.z - self.center.z) <= self.height / 2
        else:
            raise NotImplementedError()
        
        return radial_dist_sq <= self.radius**2 and height_ok
    
    def distance_to(self, point: Point3D) -> float:
        if self.axis == 'z':
            radial_dist = math.sqrt((point.x - self.center.x)**2 + (point.y - self.center.y)**2)
            height_dist = abs(point.z - self.center.z) - self.height / 2
            
            if radial_dist <= self.radius and height_dist <= 0:
                return 0
            
            return math.sqrt(
                max(0, radial_dist - self.radius)**2 +
                max(0, height_dist)**2
            )
        return float('inf')
    
    def get_type(self) -> str:
        return "cylinder"

class PointClassifier:
    def __init__(self):
        self.shapes: List[Shape] = []
    
    def add_shape(self, shape: Shape) -> None:
        self.shapes.append(shape)
    
    def classify(self, point: Point3D) -> tuple[str, float]:
        """
        Классифицирует точку: возвращает (тип фигуры, расстояние)
        """
        best_shape = None
        best_distance = float('inf')
        
        for shape in self.shapes:
            # Сначала проверяем если точка внутри
            if shape.contains(point):
                return (shape.get_type(), 0.0)
            
            # Иначе вычисляем расстояние до ближайшей
            distance = shape.distance_to(point)
            if distance < best_distance:
                best_distance = distance
                best_shape = shape
        
        if best_shape is None:
            return ("unknown", float('inf'))
        
        return (best_shape.get_type(), best_distance)
    
    def classify_batch(self, points: List[Point3D]) -> List[tuple[str, float]]:
        """
        Классифицирует множество точек
        """
        return [self.classify(point) for point in points]

# Использование
classifier = PointClassifier()
classifier.add_shape(Sphere(center=Point3D(0, 0, 0), radius=5.0))
classifier.add_shape(Cube(min_corner=Point3D(10, 10, 10), max_corner=Point3D(20, 20, 20)))
classifier.add_shape(Cylinder(center=Point3D(30, 30, 0), radius=3.0, height=10.0))

# Классифицируем точки
test_points = [
    Point3D(2, 2, 2),      # Внутри сферы
    Point3D(15, 15, 15),   # Внутри куба
    Point3D(30, 30, 2),    # Внутри цилиндра
    Point3D(50, 50, 50),   # За пределами всех
]

for point in test_points:
    shape_type, distance = classifier.classify(point)
    print(f"Point {point} -> {shape_type} (distance: {distance:.2f})")

2. Машинное обучение (когда фигуры неизвестны)

Если параметры фигур неизвестны, используем KNN или другие ML алгоритмы:

from sklearn.neighbors import KNeighborsClassifier
from sklearn.preprocessing import StandardScaler
import numpy as np

class MLPointClassifier:
    def __init__(self, n_neighbors: int = 5):
        self.model = KNeighborsClassifier(n_neighbors=n_neighbors)
        self.scaler = StandardScaler()
        self.trained = False
    
    def train(self, points: np.ndarray, labels: np.ndarray) -> None:
        """
        Обучаем классификатор на примерах
        points: (n_samples, 3) массив координат
        labels: (n_samples,) массив типов фигур
        """
        # Нормализуем данные
        points_normalized = self.scaler.fit_transform(points)
        
        # Обучаем KNN
        self.model.fit(points_normalized, labels)
        self.trained = True
    
    def predict(self, point: Point3D) -> str:
        if not self.trained:
            raise RuntimeError("Model not trained")
        
        point_array = np.array([[point.x, point.y, point.z]])
        point_normalized = self.scaler.transform(point_array)
        
        return self.model.predict(point_normalized)[0]
    
    def predict_batch(self, points: List[Point3D]) -> List[str]:
        predictions = []
        for point in points:
            predictions.append(self.predict(point))
        return predictions

# Использование
# Генерируем обучающий набор
train_points = np.vstack([
    np.random.normal(0, 1, (100, 3)),      # 100 точек в сфере (0,0,0)
    np.random.uniform(10, 20, (100, 3)),   # 100 точек в кубе
    np.random.normal([30, 30, 0], 1, (100, 3)),  # 100 точек в цилиндре
])

train_labels = np.array(['sphere'] * 100 + ['cube'] * 100 + ['cylinder'] * 100)

# Обучаем
ml_classifier = MLPointClassifier(n_neighbors=5)
ml_classifier.train(train_points, train_labels)

# Классифицируем
test_point = Point3D(1, 1, 0)
print(ml_classifier.predict(test_point))  # "sphere"

3. Гибридный подход (лучший для реальных приложений)

class HybridPointClassifier:
    def __init__(self):
        self.geometric_classifier = PointClassifier()
        self.ml_classifier = MLPointClassifier()
        self.use_ml_fallback = False
    
    def add_known_shape(self, shape: Shape) -> None:
        """Добавляем известную геометрическую фигуру"""
        self.geometric_classifier.add_shape(shape)
    
    def train_ml_fallback(self, points: np.ndarray, labels: np.ndarray) -> None:
        """Обучаем ML для неизвестных случаев"""
        self.ml_classifier.train(points, labels)
        self.use_ml_fallback = True
    
    def classify(self, point: Point3D) -> tuple[str, float]:
        # Сначала пытаемся геометрическую классификацию
        shape_type, distance = self.geometric_classifier.classify(point)
        
        # Если точка очень близко к фигуре — уверены
        if distance < 0.1:
            return (shape_type, distance)
        
        # Иначе используем ML если доступен
        if self.use_ml_fallback and distance > 1.0:
            ml_type = self.ml_classifier.predict(point)
            return (ml_type, distance)
        
        return (shape_type, distance)

# Использование
hybrid = HybridPointClassifier()
hybrid.add_known_shape(Sphere(center=Point3D(0, 0, 0), radius=5.0))
hybrid.add_known_shape(Cube(min_corner=Point3D(10, 10, 10), max_corner=Point3D(20, 20, 20)))

# Обучаем ML на случай неизвестных фигур
train_points = np.random.randn(300, 3)
train_labels = np.array(['sphere'] * 100 + ['cube'] * 100 + ['cylinder'] * 100)
hybrid.train_ml_fallback(train_points, train_labels)

# Классифицируем
test_point = Point3D(2, 2, 2)
shape_type, distance = hybrid.classify(test_point)
print(f"Shape: {shape_type}, Distance: {distance:.2f}")

4. Оптимизация для большого количества точек

from scipy.spatial import KDTree

class OptimizedPointClassifier:
    def __init__(self):
        self.shapes: List[Shape] = []
        self.kdtree = None
        self.kdtree_data = None
    
    def add_shape(self, shape: Shape) -> None:
        self.shapes.append(shape)
    
    def build_index(self, sample_points: np.ndarray) -> None:
        """
        Строим KD-дерево для быстрого поиска
        """
        self.kdtree_data = sample_points
        self.kdtree = KDTree(sample_points)
    
    def classify_batch_optimized(self, points: List[Point3D]) -> List[str]:
        """
        Быстрая классификация множества точек
        """
        classifications = []
        
        for point in points:
            # Сначала проверяем внутри ли фигур
            found = False
            for shape in self.shapes:
                if shape.contains(point):
                    classifications.append(shape.get_type())
                    found = True
                    break
            
            if not found:
                # Используем KD-дерево для поиска ближайшей точки
                if self.kdtree is not None:
                    query_point = np.array([[point.x, point.y, point.z]])
                    distance, index = self.kdtree.query(query_point, k=1)
                    # Используем информацию о ближайшей соседней точке
                    classifications.append(f"unknown_near_{index[0][0]}")
                else:
                    classifications.append("unknown")
        
        return classifications

5. Полный пример с визуализацией

def visualize_classification(classifier: HybridPointClassifier, test_points: List[Point3D]):
    """
    Визуализирует результаты классификации
    """
    results = {}
    
    for point in test_points:
        shape_type, distance = classifier.classify(point)
        
        if shape_type not in results:
            results[shape_type] = []
        
        results[shape_type].append({
            'point': point,
            'distance': distance
        })
    
    # Выводим статистику
    for shape_type, points_list in results.items():
        print(f"\n{shape_type.upper()}:")
        print(f"  Count: {len(points_list)}")
        distances = [p['distance'] for p in points_list]
        print(f"  Avg distance: {sum(distances) / len(distances):.2f}")
        print(f"  Min/Max distance: {min(distances):.2f} / {max(distances):.2f}")

# Использование
classifier = HybridPointClassifier()
classifier.add_known_shape(Sphere(center=Point3D(0, 0, 0), radius=5.0))
classifier.add_known_shape(Cube(min_corner=Point3D(10, 10, 10), max_corner=Point3D(20, 20, 20)))

test_points = [Point3D(x, y, z) for x in [-10, 0, 10, 20, 30] for y in [-10, 0, 10] for z in [-5, 0, 5]]
visualize_classification(classifier, test_points)

Сравнение подходов

Итого

1. Если параметры фигур известны — используй геометрическую классификацию
2. Если параметры неизвестны — используй KNN или другой ML алгоритм
3. В production — комбинируй оба подхода (гибридный метод)
4. Для оптимизации — используй пространственные индексы (KD-дерево, R-дерево)
5. Для масштабирования — распараллеливай обработку на GPU через CuPy или TensorFlow