Нужен совет по модели, Ночь в тоскливом октябре
    |
Нужен совет по модели, Ночь в тоскливом октябре
Jolaf |
Root
Jul 21 2011, 07:33 PM
Отправлено
#1
|
[информация] |
Нужно сделать модельку а ля Игра из "Ночи в тоскливом октябре" Желязны.
Задачка формулируется так. На карте полигона (и на самом полигоне) есть N точек (порядка 5-30). Нужно придумать алгоритм, позволяющий раcчитать местонахождение на карте (и на полигоне) точки "центра". Ключевые требования к алгоритму следующие: - Для любого заданного расположения точек решение должно существовать и быть единственным. - Решение должно быть устойчиво к малым отклонениям положения исходных точек. То есть, если исходные точки смещаются незначительно, или при расчёте допускаются незначительные геометрические или численные ошибки, отклонение полученного решения от правильного тоже должно быть незначительным. - Расчёт решения по алгоритму с использованием карты должен быть выполним человеком без помощи компьютера за время от десятков минут до нескольких часов. Крайне желательные свойства алгоритма: - Алгоритм должен быть геометрическим. Расчёт должен проводиться на карте с помощью карандаша и линейки без делений, может быть циркуля. - Алгоритм должен быть НЕ устойчив к добавлению новых исходных точек или удалению с карты существующих исходных точек. То есть, при добавлении новой точки в любое место или удалении любой из существующих, решение должно меняться существенно. - Перерасчёт при удалении или добавлении новых точек должен занимать существенное время. - Расчёт должен быть выполним с помощью компьютерной программы (с заранее вбитыми исходными данными) не более чем за несколько минут. Желательные свойства алгоритма: - Расчёт должен быть хотя бы теоретически выполним на полигоне без помощи карты при хорошем глазомере и пространственном воображении за время от часов до десятков часов. Замеченные проблемы: - Учитывая потенциально большое количество исходных точек, напрашивается идея использовать рекурсию, то есть, посчитать по N исходных точек M < N новых точек (центры каких-нибудь отрезков или треугольников и т. п.), после чего повторить расчёт для этих M и так далее, пока их не останется 2 или 3 и ответ не станет очевидным. К сожалению, все алгоритмы, которые я придумал и запрограммировал к данному моменту, при N > 6 дают не уменьшение, а увеличение числа точек с каждой итерацией. В общем, нужны свежие оригинальные идеи, сколь угодно безумные. Сообщение отредактировано: Jolaf, Jul 21 2011, 07:36 PM |
Юра |
Отправлено
#2
|
[информация] |
Я правильно понял, что все простые геометрические алгоритмы тебя не устраивают именно в силу того, что простые алгоритмы достаточно устойчивы к добавлению новых точек?
Т.е. если игрок найдет 29 точек из 30, то его рассчетный "центр" будет очень близко к "центру" карты, построенной по всем 30 точкам? А по сути модели, он конечно должен очень сильно ошибиться в такой ситуации. Если это основная причина, по которой тебя не устраивают геометрические алгоритмы, то можно сделать несколько видов точек. Например: точки типа А имеют "вес", по которому находится "центр" полигона. точки типа Б "веса" не имеют; зато они "выключают" все точки типа А на опредленном расстоянии от себя. Т.е. точка А не имеет веса, если в радиусе R от нее есть точка типа Б. В такой ситуации единственная пропущенная точка Б, которая выключает сразу несколько точек типа А, значительно влияет на итоговый результат. Это тупо пример, можно сделать больше видов точек, так, чтобы они влияли друг на друга: изменяли веса соседей, включали и выключали веса соседей в определенных комбинациях и т.п. в зависимости от твоих потребностей. Это конечно если я правильно понял всю совокупность причин, по которой тебя не устраивает простая геометрическая модель, в которой нужно найти "центр тяжести" точек на полигоне. Сообщение отредактировано: elraen, Jul 21 2011, 09:02 PM |
pasha |
Отправлено
#3
|
[информация] |
QUOTE(Jolaf @ Jul 21 2011, 10:33 PM) - Алгоритм должен быть НЕ устойчив к добавлению новых исходных точек или удалению с карты существующих исходных точек. То есть, при добавлении новой точки в любое место или удалении любой из существующих, решение должно меняться существенно. Общего алгоритма не предложу, но вот именно это свойство я бы моделировал заданием двух разных алгоритмов - для четного и нечетного числа точек. |
Jolaf |
Отправлено
#4
|
[информация] |
QUOTE(pasha @ Jul 22 2011, 09:55 AM) Общего алгоритма не предложу, но вот именно это свойство я бы моделировал заданием двух разных алгоритмов - для четного и нечетного числа точек. О, крутая мысль, спасибо! |
Фёдор |
Отправлено
#5
|
[информация] |
Ещё к предложению Юры можно добавить, что вес точки может быть как положительным, так и отрицательным.
А четность количества точек, например, меняет все знаки для определённого набора точек. -------------------- |
Jolaf |
Отправлено
#6
|
[информация] |
QUOTE(elraen @ Jul 22 2011, 12:02 AM) Я правильно понял, что все простые геометрические алгоритмы тебя не устраивают именно в силу того, что простые алгоритмы достаточно устойчивы к добавлению новых точек? Да, это одна из причин. Вторая - большое количество операций и накапливающаяся ошибка при ручном расчёте. QUOTE(elraen @ Jul 22 2011, 12:02 AM) можно сделать несколько видов точек Идея крутая, спасибо, подумаю её. Пока вижу две проблемы. Во-первых, по условию задачи (сейчас допишу) выключать точки из расчёта нельзя, каждая должна влиять на результат. Во-вторых: QUOTE(elraen @ Jul 22 2011, 12:02 AM) Это конечно если я правильно понял всю совокупность причин, по которой тебя не устраивает простая геометрическая модель, в которой нужно найти "центр тяжести" точек на полигоне. Найти "центр тяжести" тоже непросто без компьютера, тем более геометрически. |
Jolaf |
Отправлено
#7
|
[информация] |
QUOTE(lotren @ Jul 22 2011, 11:05 AM) Ещё к предложению Юры можно добавить, что вес точки может быть как положительным, так и отрицательным. А четность количества точек, например, меняет все знаки для определённого набора точек. Ага, тоже круто. Вопрос в том, что дальше делать с этими весами? На компе-то, понятно, можно посчитать физический центр тяжести и всё. А на бумаге, карандашом и линейкой? |
Юра |
Отправлено
#8
|
[информация] |
Ну про выключение точек - это была просто одна из мыслей, как можно реализовать идею нескольких видов точек. Основная идея - это именно несколько видов точек.
Центр тяжести геометрически как раз ищется не очень сложно, но при большом количестве точек ошибка конечно будет накапливаться очень заметно. Но как раз разными видами точек по идее можно бороться с накапливающейся ошибкой - т.к. алгоритм фактически бьется на несколько частей, в каждой из которых точек меньше. |
Юра |
Отправлено
#9
|
[информация] |
С циркулем центр тяжести ищется легко. Только с линейкой - тоже, но точность будет существенно ниже.
Сообщение отредактировано: elraen, Jul 22 2011, 08:40 AM |
Jolaf |
Отправлено
#10
|
[информация] |
QUOTE(elraen @ Jul 22 2011, 11:39 AM) Центр тяжести геометрически как раз ищется не очень сложно Например как? (вдруг я не вижу чего-то очевидного) |
Юра |
Отправлено
#11
|
[информация] |
При равных весах точек:
Центр тяжести отрезка - его середина. Центр тяжести треугольника - пересечение медиан. Это значит, если количество точек - степень двойки, тройки или их комбинации (2*3^2 например) решаются вообще не особенно задумываясь. При другом количестве точек тоже, в общем, ищется. В конце концов, всегда можно лишние точки (больше, чем ближайшая комбинация степеней двойки и тройки) учитывать, находя центр тяжести отрезка с центром тяжести между всей остальной системой и конкретной лишней точкой - просто у центра тяжести всей остальной системы считать как точку с весом всех тех точек, чьим центром тяжести она является. Короче, с циркулем, линейкой и ровной поверхностью за 20 минут можно посчитать центр тяжести любого разумного количества (штук до 50 точно) точек. Сообщение отредактировано: elraen, Jul 22 2011, 08:53 AM |
Jolaf |
Отправлено
#12
|
[информация] |
QUOTE(elraen @ Jul 22 2011, 11:51 AM) можно лишние точки (больше, чем ближайшая комбинация степеней двойки и тройки) учитывать, находя центр тяжести отрезка с центром тяжести между всей остальной системой и конкретной лишней точкой Окей, вот у тебя есть центр тяжести остальной системы с весом, скажем, 28. И есть ещё одна точка, с весом, очевидно, 1. Как будем искать центр тяжести? Сообщение отредактировано: Jolaf, Jul 22 2011, 08:58 AM |
Юра |
Отправлено
#13
|
[информация] |
Делим отрезок на 29 равных частей и берем ближайшую часть к тяжелой точке.
Да, на 29 частей циркулем и линейкой делить невесело, но это нужно сделать один раз. Кроме того, тебе нужны не все 29 одинаковых отрезков, а только первый с нужной стороны, так что все вообще не так плохо. Более того, если точек 30, то ты сначала ищешь центр тяжести двух оставшихся точек, а потому отрезок между ним и цетром масс остальной системы делится уже не на 29 частей, а на 15, что уже лучше. Сообщение отредактировано: elraen, Jul 22 2011, 09:04 AM |
Фёдор |
Root
Jul 22 2011, 09:20 AM
Отправлено
#14
|
[информация] |
на бумаге это делается элементарно например, на миллиметровке -
ставим точки с весами по координатам. по каждой координате берём сумму (координата точки * вес точки) делим на общее кол-во точек получаем координаты центра масс на обычной бумаге - сложнее, но тоже можно упростить, введя координаты(просто нарисовав оси) без бумаги/ручки, а в уме - тяжело, да. -------------------- |
Юра |
Отправлено
#15
|
[информация] |
Как я понял, Йолаф хочет делать это прямо на карте, так что миллиметровка вроде не очень подходит. Хотя, в общем, тоже можно перенести с карты на миллиметровку.
|
Фёдор |
Отправлено
#16
|
[информация] |
для примерного подсчёта достаточно срисовать путём налоожения с карты на клетчатую (5 мм) бумагу и проделать то же самое. Точность - +- 5 мм на карте, что конечно немало, но зависит от масштаба.
-------------------- |
Jolaf |
Отправлено
#17
|
[информация] |
QUOTE(elraen @ Jul 22 2011, 12:03 PM) Да, на 29 частей циркулем и линейкой делить невесело То-то и оно. Очень громоздко получается, и занудно. Хочется элегантного решения. Грубо говоря, больше думать и меньше считать. Я вот сейчас думаю в сторону алгоритма, в котором нужно правильно (анализ может занять приличное время, но требует смотреть и измерять, а не рисовать) выбрать первую точку, потом вторую, как первую из оставшихся, и из этой последовательности потом как-то высчитывать центр... |
Askold |
Отправлено
#18
|
[информация] |
Может быть, скажу бред, но тем не менее, такая идея:
1. Найти самую внешнюю и самую внутреннюю ломанную фигуру, т.е. внешний и внутренний "круги силы" 2. Найти их центры тяжестей. 3. Искомый центр системы находится на прямой, соединяющей центры тяжестей внутренней и внешней фигур, его расположение зависит от количества внутренних фигур - "кругов силы" и количества точек во внешней и внутренней. |
Флоран |
Отправлено
#19
|
[информация] |
Идея прикольная -- вся сложность в том, как эти круги провести однозначно.
|
Юра |
Отправлено
#20
|
[информация] |
С учетом того, что такое занудство - разовое, это не так уж и плохо.
QUOTE Я вот сейчас думаю в сторону алгоритма, в котором нужно правильно (анализ может занять приличное время, но требует смотреть и измерять, а не рисовать) выбрать первую точку, потом вторую, как первую из оставшихся, и из этой последовательности потом как-то высчитывать центр... Это довольно хорошая мысль. Тебе это для "Ночи в тоскливом октябре" или ты это просто в качестве примера привел? Есть вот какие идеи, которые могут подойти, а могут и не подойти: 1. Учитывать возраст точки. Скажем, нужно идти от старых точек к новым, или у старых точек могут быть какие-то дополнительные свойства (другой тип точек для самых старых точек?). 2. Добавить к точкам связи. Скажем, у каждой точки есть направленные связи. Дальше считаем направленные связи как векторную сумму и получаем финальную точку. А как точку начала отсчета, от которой будет откладываться векторная сумма, можно взять центр тяжести точек другого типа, которых будет немного. Такие дополнительные свойства точек могут добавить интереса игре, так как нужно не только локализовать точки, но и проанализировать разное. Например данные о том, как строятся связи между точками, могут быть размазаны по командам (открывающих и закрывающих, если мы все еще о НвТО), что потребует какой-то дополнительной кооперации, нельзя будет в одиночку установить все доп. данные о точках. |
     |
Упрощённая версия | Сейчас: 19th April 2024 - 02:33 AM |