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

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

Страницы: 1 2 3
#30
16:10, 18 дек 2020

AlexeyLarin
Найди ближайшую точку к A и B, а также точку на серединном перпендикуляре, ближайшую к центру.
Среди этих трех будет искомая. Даже на прямоугольники резать не надо.


#31
16:50, 18 дек 2020

}:+()___ [Smile]
> Даже на прямоугольники резать не надо.

Т.е. это все сделать на полигоне? Тогда ближайшая точка к A это A, к B это B т.к. они лежат на этом полигоне. А серединный перпендекуляр к какому отрезку?

#32
18:16, 18 дек 2020

AlexeyLarin
> Вот для этого случая искомая точка будет в центре прямоугольника.
хм. ну да, сначала надо проверить тривиальный вариант - точку в середине отрезка AB. Если она в многоугольнике то дальше считать ничего не надо.
А вот если она в дырке, то искомая точка может быть только на одном из отрезков, не внутри.
---
Но в первом пункте что-то не сходится. Если у нас равносторонний треугольник без всяких дырок, то две самые удаленные точки будут две вершины, а центр окружности очевидно не на них. Так что к двум точка алгоритм не сводится, надо рассматривать остальные тоже.

#33
20:31, 18 дек 2020

kipar
> Если у нас равносторонний треугольник без всяких дырок, то две самые удаленные
> точки будут две вершины, а центр окружности очевидно не на них
Центр окружности получится на середине стороны этих вершин, но это тоже не верно. Придется просматривать все вершины

#34
22:33, 18 дек 2020

https://en.wikipedia.org/wiki/Smallest_circle_problem
Если не внутри - тогда лежит на границе.

#35
22:54, 18 дек 2020

FordPerfect
> Если не внутри - тогда лежит на границе.
Центр полученной окружности будет лежать на границе? Почему?

#36
6:01, 19 дек 2020

AlexeyLarin
Центр smallest bounding circle, конечно же, может быть строго снаружи (представить букву С). Но в этом случае, насколько я понимаю, ответ на твою задачу - окружность с центром на границе. Её, походу, можно найти перебором (для вершин - прямо перебором, для рёбер - ещё бинпоиск положения точки на ребре).

#37
14:05, 19 дек 2020

AlexeyLarin
> Т.е. это все сделать на полигоне?
А не, вру. Надо резать.

> А серединный перпендекуляр к какому отрезку?
К AB.

В общем, режешь всю свою фигуру серединным перпендикуляром к AB на два куска, в одном ищешь ближайшую к A точку, в другом — ближайшую к B. Еще можно попробовать извращенное разбиение Вороного: в обычном выделяются области, ближайшие к точкам, а тебе надо наоборот — самые дальние. Не факт, правда, что это можно сделать эффективно.

#38
19:58, 19 дек 2020

}:+()___ [Smile]
Тоесть еще и мемори баджет считать? Уууу, инжененры...

#39
20:25, 19 дек 2020

}:+()___ [Smile]
По новым данным AB недостаточно, нужно все вершины (входящие в выпуклую оболочку) проверять.

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

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