Member 13847946 Ответов: 3

Если программа представлена с координатами X и Y, как я могу заставить программу соединить эти точки, чтобы сформировать форму, подобную кругу?


Если программа представлена с координатами X и Y, как я могу заставить программу соединить эти точки, чтобы сформировать форму, подобную кругу? Это означает, что программа пытается создать фигуру, соединяя эти точки. Что я хочу знать: как определить, какие точки нужно соединить, чтобы сформировать круг(или форму, ближайшую к кругу).
Я не ищу никакого конкретного кода, только алгоритм. Спасибо:)

Пример:

Это визуальное представление входных данных(координат)

Программа будет использовать эти координаты для создания фигуры, соединяя их. Выходные данные должны показывать, какие точки соединены, чтобы сформировать эту фигуру. Эта фигура должна проходить через все точки и при этом быть максимально близкой(через точки) к окружности/иметь максимально возможную площадь поверхности.
визуальное представление выходных данных
Выходные данные этого примера должны быть AB,BC,CX,XY,YZ,ZA

Что я уже пробовал:

Я попытался сравнить расстояния между точками, чтобы увидеть, каков самый короткий путь через все точки, которые заканчиваются в начальной точке, и это, кажется, дает хороший результат. Однако я уверен, что существует более эффективный алгоритм.

Richard MacCutchan

Это зависит от того, сколько координат дано и в каком порядке.

3 Ответов

Рейтинг:
2

Andy Allinger

Если точки-это все точки на одной точной окружности, то путь, соединяющий их, который ближе всего к окружности, является кратчайшим путем.
Предположим в качестве гипотезы, что путь, наиболее похожий на окружность, в общем случае является кратчайшим путем. Тогда ваша проблема-это проблема коммивояжеров, самая известная в компьютерной науке. Найдите порядок посещения точек, который дает наименьшее пройденное расстояние. Не существует эффективного, точного решения, известного, но множество эвристик будет служить этой цели. Имитация отжига будет работать, смотрите Числовые Рецепты Для медленного и точного решения см. http://calgo.acm.org/750.gz


Рейтинг:
1

CPallini

Ты имеешь в виду сплайны[^]?


Рейтинг:
0

Patrice T

Ваш вопрос неясен.
Вопрос настолько расплывчатый, что я вижу 2 совершенно разные вещи, которые подходят к провлему:
- У вас есть набор точек, и вы хотите нарисовать наименьший круг, который окружает эти точки.
Проблема наименьшего круга - Википедия[^]
- У вас есть набор точек, и вы хотите нарисовать выпуклую оболочку.
Выпуклая оболочка - Википедия[^]

Для лучшего ответа: уточните свой вопрос, приведите пример ввода и результата, который вы ищете.
[Обновление]

Цитата:
Выходные данные этого примера должны быть AB,BC,CX,XY,YZ,ZA

Прямая связь с AC и удаление B будет ближе к кругу. Это то, чего ты хочешь ?