Как вычислить оптимальный охватывающий сегмент круга из набора двумерных точек? ⇐ Python

[Anonymous]

Мне нужен совет о том, как подогнать круговой сегмент к набору 2D-точек. Мой набор данных выглядит следующим образом: 2D-данные для соответствия сегменту
Для ясности, мое определение «оптимального» сегмента — это раздел с наименьшей площадью, который ограничивает все (или потенциально высокий процент) моих точек. Этот круговой сегмент может иметь переменный радиус, а также переменный угол поворота (в примере 90 градусов). Я бы определил ответ так: 2D-данные с оптимальным сегментом
Я хотел бы знать, существуют ли какие-либо существующие алгоритмы, которые могут соответствовать круговому сегменту. Вот мои текущие мысли о том, как это можно сделать:
Вычислите 2D-ориентированную ограничивающую рамку (OBB) вокруг набора точек. Отсюда я должен знать, что одна из двух осей ОББ должна быть ориентирована по радиусу. В частности, центральная точка сегмента должна лежать на линии, образованной центром этого OBB, указывающим в направлении одной из его осей. Вероятно, я мог бы написать несколько тестов, чтобы проработать все остальное (ищите симметрию выпуклой оболочки вдоль любой оси, радиус будет лежать на лучшей).
Пример (радиус будет лежать вдоль одной из линий): 2d-данные с OBB и осями
Основная причина, по которой я не хочу идти по этому пути, заключается в том, что он кажется подвержен проблемам в тех случаях, когда мои точки имеют небольшой шум или иным образом неточны. Интересно, что думают другие.
Вот код Python, который может генерировать образец набора 2D-точек, аналогичный моему примеру. Будем признательны за любые советы или существующие реализации (может быть на любом языке), заранее спасибо!
import numpy as np
import matplotlib.pyplot as plt

def generate_sector_points(origin, radius, degree_start, degree_end, n_points=500):
"""Generate random points uniformly distributed in a circular sector."""
theta_start = np.radians(degree_start)
theta_end = np.radians(degree_end)

# generate random points in polar coordinates
r = radius * np.sqrt(np.random.uniform(0, 1, n_points))
theta = np.random.uniform(theta_start, theta_end, n_points)

x = origin[0] + r * np.cos(theta)
y = origin[1] + r * np.sin(theta)

return x, y, theta_start, theta_end

origin = (0, 0)
radius = 5.0
degree_start = 15
degree_end = 85

x, y, theta_start, theta_end = generate_sector_points(origin, radius, degree_start, degree_end)

fig, ax = plt.subplots(figsize=(8, 8))
ax.scatter(x, y, c='blue', alpha=0.6, s=30)
ax.plot(origin[0], origin[1], 'ro', markersize=8, label='Origin')

# draw sector boundary
theta_range = np.linspace(theta_start, theta_end, 100)
arc_x = origin[0] + radius * np.cos(theta_range)
arc_y = origin[1] + radius * np.sin(theta_range)
ax.plot(arc_x, arc_y, 'r--', linewidth=2, label='Sector boundary')

# draw radial lines
for theta in [theta_start, theta_end]:
ax.plot([origin[0], origin[0] + radius * np.cos(theta)],
[origin[1], origin[1] + radius * np.sin(theta)], 'r--', linewidth=2)

ax.set_aspect('equal')
ax.grid(True, alpha=0.3)
ax.legend()
ax.set_title(f'50 Random Points in Sector ({degree_start}° - {degree_end}°)')
plt.show()


Подробнее здесь: https://stackoverflow.com/questions/798 ... -point-set