Войти
ПрограммированиеФорумОбщее

Геометрическая задача (2 стр)

Страницы: 1 2 3 Следующая »
#15
23:03, 17 дек 2020

lookid
Вроде похоже на то, что нужно. Т.е. нам нужно найти полюс недоступности (wiki)


#16
23:35, 17 дек 2020

AlexeyLarin
https://neerc.ifmo.ru/wiki/index.php?title=Straight_skeleton вот еще близкое

#17
7:05, 18 дек 2020

Я слабо себе представляю центральную точку внутри многоугольника снизу справа.
Изображение
Где она должны быть? Нарисуй какие кружочки, по твоему мнению, которые должны быть на каждом твоего многоугольнике?

#18
11:23, 18 дек 2020

Kripto289
Примерно так. Линии это самое длинное расстояние для выбранной точки.
Изображение

#19
11:26, 18 дек 2020

AlexeyLarin
Хм, вороной, полюс недоступности, скелет не будет соответствовать твоим изначальным условиям
"...центр для этой окружности, чтобы ее радиус был минимально возможным."

#20
11:32, 18 дек 2020

rcsim
Ага.
https://blog.mapbox.com/a-new-algorithm-for-finding-a-visual-cent… -7c77e6492fbc
Вот этот алгоритм ищет окружность максимального радиуса которую можно вписать в полигон. А мне нужна окружность минимального радиуса которая покроет все точки этого полигона + центр внутри полигона. Мне кажется его можно адаптировать под мою задачу.

#21
11:59, 18 дек 2020

А для чего тебе вообще это надо?

#22
12:22, 18 дек 2020

Kripto289
Нужно покрыть полигон окружностью :D

#23
12:24, 18 дек 2020

Kripto289
Может на интерью спросили задачу на смекалку по геметрии. Такие может быть в каких-нибудь збраше, 3дмаксе или блендере.

#24
12:46, 18 дек 2020

Придумал как можно сделать проще (или нет):

Перебираем бинпоиском радиус. Проводим из каждой вершины окружность этого радиуса. На каждой итерации бинпоиска проверяем что у нас есть область которая лежит внутри каждой окружности и внутри полигона. В зависимости есть такая область или нет двигаем границы бинпоиска.

И можно упростить до следующего. Нам не нужны все окружности, а нужны только те которые лежат в двух самых удаленных точках. Т.е. находим две самые удаленные друг от друга точки в полигоне. Далее перебираем бинпоиском радиус и смотрим чтобы была общая площадь у этих двух окружностей и исходного полигона. Соответственно точка из этой площади и есть искомый центр.

#25
12:49, 18 дек 2020

lookid
Для своего прототипа делаю. Я был бы не очень рад если бы у меня такое на интервью спросили)

#26
12:57, 18 дек 2020

AlexeyLarin
> Придумал как можно сделать проще (или нет):
По сравнению с той жестью которая в статье по-моему в разы проще.
Ну и если представить фигуру "пересечение двух окружностей из крайних точек" аналитически, то можно и без поиска найти. Хотя не факт что будет быстрее (смотря как полигон задан, линиями или областями).

---
хотя если подумать, без поиска всегда быстрее будет. Просто мы определяем "близость точки" таким образом: если есть две макс.удаленные точки А и B, то для точки лежащей со стороны точки А близость - это расстояние до B, а для точки лежащей со стороны B это расстояние до A. Ну и дальше надо найти "ближайшую" в этом смысле точку, просто пройдясь по всем отрезкам (или прямоугольникам).

#27
13:55, 18 дек 2020

kipar
Т.е. можно разбить исходный полигон на прямоугольники и для каждого прямоугольника искать точку ближайшую к этим двум точкам. И потом выбрать лучшую.

А как найти точку внутри прямоугольника ближайшую к двум заданным?

#28
15:04, 18 дек 2020

AlexeyLarin
для отрезка это либо один из концов, либо высота опущенная из более дальней точки. Наверное, есть случай когда надо рассмотреть высоту из обеих точек.
Для прямоугольника - у нас есть 4 отрезка, какие-то можно откинуть как более далекие (т.к. прямоугольник может "смотреть" на центр только двумя сторонами).

#29
15:57, 18 дек 2020

kipar
Но искомая точка может быть не только на границе прямоугольника, но и внутри. Вот для этого случая искомая точка будет в центре прямоугольника.
Изображение

Страницы: 1 2 3 Следующая »
ПрограммированиеФорумОбщее

Тема в архиве.