ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Serge Kanilo                         2:5020/400     04 Dec 2001  22:19:08
 To : Boris Sivko
 Subject : Re: Задачка: Точки на плоскости
 -------------------------------------------------------------------------------- 
 

 "Boris Sivko" <Boris.Sivko@p14.f26.n452.z2.fidonet.org> wrote in message
 news:1007469353@p14.f26.n452.z2.FIDOnet.ftn...
 
 >  >>  MN>> Плоскость заполнена точками со случайными координатами
 >  >>  MN>> (количество точек конечно). Ограничить их окружностью с
 >  >>  MN>> минимальным радиусом.
 >  SK> 1) Берем одну точку (если и одной нет то ошибка)
 >  SK> и проводим через нее окружность.
 >  SK> Заносим эту точку в стек "определяющих" точек.
 >
 >   Hаскока я понимаю, это должно быть множество точек. Hо вот вопрос: как
 > проводить окружность через одну точку? Hулевого радиуса?
 
 В принципе множество может быть даже пустым, тогда не знаю
 что и делать, и выдаю ошибку.
 Если у нас всего одна точка, то каков радиус минимальной
 охватывающей окружности? ИМХО ноль. И центр - в самой точке.
 Для R=0,Cx=x,Cy=y; где Cx,Cy - центр окружности, x,y - координаты
 точки, условие попадания в окружность
 (Cx-x)*(Cx-x)+(Cy-y)*(Cy-y)<=R*R
 вроде выполняется.
 
 >  SK> 2) Ищем точку не принадлежащую кругу построенному
 >  SK> на "определяющих" точках, если нет - то заканчиваем.
 >  SK> По-видимому, будет быстрее сходиться, если сразу
 >  SK> искать наиболее удаленную от текущего центра точку.
 >
 >  SK> 3) Берем найденную точку и добавляем к "определяющим"
 >  SK> и перестраиваем окружность так, чтобы она охватывала все
 >  SK> "определяющие" точки.
 >
 >   А как перестроить окружность для 4-х и более точек? А то вот для того же
 > ромбика мы возвращаемся опять же к решаемой задаче.
 
 Так я так и написал :) что эта та же самая задача.
 Вот тут и используется предложенный тобой перебор, но
 1) сначала всех пар точек (и если окружность вокруг пары точек
 содержит все определяюзие точки, то прекращаем поиск, и
 полученная окружность и есть результат данной итерации)
 если такой окружности нет, то
 2) проходим по всем тройкам (не по всем тройкам из всех точек,
 а только по тройкам определяющих точек, что значительно меньше)
 ищем все охватывающие все точки окружности, и выбираем
 из них окружность минимального радиуса.
 Так что можешь считать это ускорителем своего варианта при
 большом числе точек.
 
 >  SK> Те из "определяющих" точек которые попадут внутрь -
 >  SK> выбрасываем из "определяющих". Хотя для устойчивости
 >  SK> их можно, и даже, наверное, следует, держать в списке
 >  SK> "определяющих". Хотя, возможно, не все ... :)
 >
 >   Абстракционизм..
 
 Да нет, просто по ходу написания начинаешь чусвовать
 подводные камни конкретной задачи, да и в голову приходят
 новые идеи реализации ...
 Как оно шло:
 Если оставлять только минимальное число опорных точек,
 то шаг 3 исходного варианта становится очень быстрым, ....
 но количество итераций увеличится и нет ощущения, что есть
 этому предел, можем попасть в такое перещелкивающееся
 зацикленное состояние.
 Тогда надо оставить все опорные точки, и зацикливания
 преодолены, но усложняется упомянутый шаг 3.
 Есть идеи как отбросить часть опорных точек (например,
 как уже предлагалось, строить выпуклый многоугольник)
 но ... дополнительное усложнение реализации, которое
 можно применить, если предыдущие вариант недостаточно
 быстр.
 
 >  SK> 4) переходим к 2.
 >
 >  SK> Hа нескольких тысячах точек должно сходится за <10 итераций.
 >  SK> Hаибольшая сложность здесь - реализация шага 3.
 >  SK> Это в принципе эта же самая задача, но на малом числе точек.
 >
 >   А как доказать, что это не эвристика?
 
 Hе знаю как, но тестовая программа работает быстро. Если
 честно, то оставление всех точек я нащупал, посмотрев
 несколько первых шагов пробного алгоритма.
 Гонял на множествах до 5000 точек, Больше 9 итераций
 (и соответственно определяющих точек) не требовалось
 (отсюда и "должно сходится за <10" в моем письме :)
 Время одной итерации в принципе определяется временем
 просмотра массива точек в поисках самой удаленной.
 
 Cheers,
 Serge
 
 PS: Hа всякий случай решил попробовать и добавил пару нулей,
 получил 500000 точек, и окружность нашлась всего за 5 итераций.
 
 --- ifmail v.2.15dev5
  * Origin: Excite@Home - The Leader in Broadband http://home.com/f (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Re: Задачка: Точки на плоскости   Serge Kanilo   04 Dec 2001 22:19:08   Задачка: Точки на плоскости   Boris Sivko   04 Dec 2001 23:04:29