4321(А то ить троек то ~ 10**9, как White Owl , задолбаишься просто перебирать в лоб)
Это почему это их вдруг 10**9? Откуда вдруг такое гигантское и жесткое число вылезло? :)

mikhail_n
Пока что, на мой взгляд, перспективу имеет только то, что предлагает 4321, всё остальное - детский лепет.
Ну-ну... Опубликуй свой алгоритм сначала.

4321далее, немного комбинаторики, 10**3*(10**3 - 1)*(10**3-2)/("семь-восемь"=6) - с точностью минус 0.6 порядка упираемся в 10**9 (кстати, в зависимости от методики составления троек мы можем получить и 10**3*(10**3 - 1)*(10**3-2) без "/("семь-восемь")=6").
Вообще-то из 1000 точек можно составить 166,167,000 не совпадающих комбинаций. Это вовсе не 10**9, хотя и чуть побольше чем 10**8. :)

4321Или вы предлагаете выборочную "триангуляцию". Опишите, как и что мы будем натягивать.
Нет, выборочную сделать будет сложно. Для самой выборки все равно прийдется все тройки перебирать. Так что для 1000 точек прийдется сделать 166,167,000 расчетов.
Вот только работающей альтернативы все равно нет :)

Я не понял... ну че замолчали то? Варианты решения где?
Мое с тысячью точек на P4 1.2GHz/W2K/Ansi C/MS VC 2003 справилось за пять минут. А ваше? :)

4321 White Owl выборочную сделать будет сложно. Для самой выборки все равно прийдется все тройки перебирать. Так что для 1000 точек прийдется сделать 166,167,000 расчетов.
ну хотя бы разрешили себе отбрасывать тройки, содержащие внутри натянутых на них треугольников другие проколы? (т.е. не проверять, что и окружность будет содержать как минимум те же проколы?)
То есть ты предлагаешь сначала проверить есть ли проколы внутри треугольника а потом проверять уже полную окружность? Тебе не кажется, что это будет двойная работа? :)

4321Если да - попробуйте придумать "отсечение" скажем вида ~ "взяв первую тройку с некоторыми 2-мя заданными проколами (и перебирая 3-и), для всех точек (из N) заведомо не составляем тройки с теми, которые включают 3-ю точку взятой тройки..."
Э? Расшифруй.

4321(с трудом представляю себе алгоритм (не переборный!!!) такого "отсечения", но он, возможно, спасет вас от зависимости ~N**3. Важно, чтобы алгоритм отбрасывал множества так, чтобы их даже не надо было проверять (иначе просто "уцениться" шаг перебора, но шагов останется столько же, и зависимсоть - той же степени).
Перебор будет в любом случае. Можно частично сократить перебор если суметь отсортировать элементы множества, а потом выделять "подходящий кусок" из отсортированного массива и уже в нем делать перебор. Но вот как для этой конкретной задачи сделать сортировку я с ходу не вижу.

4321 White OwlВот только работающей альтернативы все равно нет :)
Ну, не все же торопятся реализовывать лобовые алгоритмы с хреновой сходимостью. Некоторым достаточно обосновать приемлемость алгоритма со скоростью сходимости ~N и "с достаточно хорошей наперед заданной точностью". А кодировать - и без нас любителей дохера. какгрицца - "пусть трактор пашет - он железный"
Лучше признайся, что на поверку твой метод сеток не заработал :)

4321 White OwlЛучше признайся, что на поверку твой метод сеток не заработал :)
"а ты азартный, Парамоша"
Лучше признайся, что в логике "нне очинь". Пока ручками не налажаишь
Лома, ж объяснял уже много раз. А на слабО пусть мОлодежь и пОдростки фихней маица.
Немножко азартности есть, не буду отрицать. А вот наезд на логику - не угадал... А если тебе "лома" доказать свою точку зрения... Ну извините....


4321По поводу "перебирать" - "и ничего больше не дано" - (в твоем алгоритме "перебора всех возможных") я думаю ты все таки упорствуешь и врёшь, как всякий упорствующий.
В чем я вру? Ты считаешь что я вру когда говорю что не знаю как отсортировать точки чтобы не делать полного или частичного перебора? :)


4321- Положим, в порядке бреда: взяли 2 направления (от прямой) и 2 "по возможности" ближайшие к паре (искать перебором среди всех не надо, достаточно неким быстрым поиском по упорядоченному набору находить входящие в некий квадрат, усекая размер квадрата вдвое. Пока не останется по ~1 точки.
эээээ..... Квадрат говоришь? В общем, я не очень понял твое предложение... Тем более что напрямую по трем точкам его построить не получится. А вот после того как окружность уже найдена..... Ну-ка, попробуем.... ..... .... .... Есть эффект! Итого 1000 точек я сейчас обсчитываю за 3:15.

Так, еще бы придумать как сокращать количество троек на которых строятся окружности...


4321Нужны только 2 ближайшие справа и слева. Любая другая тройка даст окружность, вмещающую ближайший прокол. Как видим, наметки избавиться от 3-го N в зависимости вида N*N*N появляются.
Не годится. Ближайшие справа и слева не гарантируют что окружность построенная на них будет больше чем окружность построенная на основе более удаленых точек. При этом обе эти окружности могут даже вообще не пересекаться, а только соприкасаться в базовой точке.

mikhail_nОтносительно Вашего метода беру свои слова обратно. Он работает. Единственное чтобы поменял - на третьем шаге вместо перебора всех возможных троек (N**3) делал бы триангуляцию Деланэ (есть алгоритмы N**2).
нууууууу... можно попробовать. Делане здесь действительно подойдет лучше чем лобовая триангуляция. Ладно, ушел думать дальше :)

White Owl mikhail_n- на третьем шаге вместо перебора всех возможных троек (N**3) делал бы триангуляцию Деланэ (есть алгоритмы N**2).
нууууууу... можно попробовать. Делоне здесь действительно подойдет лучше чем лобовая триангуляция. Ладно, ушел думать дальше :)
Подумал... Не годится. Для триангуляции Делоне требуется делать перебор всех оставшихся точек, и проверять расстояние до них. Плюс хранить еще список ребер а не только список точек. В итоге получаем N^2 расчетных блоков по Tt секунд каждый для триангуляции. А потом еще N расчетных блоков по Tc секунд каждый на расчет описаных окуржностей для каждого найденого треугольника. Причем Tt как минимум в N раз больше чем Tc.
А лобовой перебор треугольников это "всего-лишь" N^3*Tc :)
Вот если бы у нас с самого начала была задана сетка ребер триангуляции - тогда да, получилось бы намного быстрее. Но нам, к сожалению, приходится строить ее самим.
В общем, интуиция меня не подвела с самого начала - триангуляция это ненужное в данном случае усложнение.

ValerПластину 3000 * 3000 можно представить
в виде решетки 3000 * 3000 или 30000 * 30000 .
( бумажный эквивалент - милиметровка )
.....

А если есть три точки с совпадающими координатами? :) К тому же точность этого метода очень уж низкая. А вообще, это все сильно смахивает на построение диаграммы Вороного методом перебора :) Есть более простые и точные методы рисования той же картинки.

Valer3 методы в студию
А в яндексе поискать по словам "диаграмма Вороного" не догадался?