[ Древовидный ] · Стандартный · Линейный Нужен совет по модели, Ночь в тоскливом октябре

Нужно сделать модельку а ля Игра из "Ночи в тоскливом октябре" Желязны.

Задачка формулируется так. На карте полигона (и на самом полигоне) есть N точек (порядка 5-30). Нужно придумать алгоритм, позволяющий раcчитать местонахождение на карте (и на полигоне) точки "центра".

Ключевые требования к алгоритму следующие:
- Для любого заданного расположения точек решение должно существовать и быть единственным.
- Решение должно быть устойчиво к малым отклонениям положения исходных точек. То есть, если исходные точки смещаются незначительно, или при расчёте допускаются незначительные геометрические или численные ошибки, отклонение полученного решения от правильного тоже должно быть незначительным.
- Расчёт решения по алгоритму с использованием карты должен быть выполним человеком без помощи компьютера за время от десятков минут до нескольких часов.

Крайне желательные свойства алгоритма:
- Алгоритм должен быть геометрическим. Расчёт должен проводиться на карте с помощью карандаша и линейки без делений, может быть циркуля.
- Алгоритм должен быть НЕ устойчив к добавлению новых исходных точек или удалению с карты существующих исходных точек. То есть, при добавлении новой точки в любое место или удалении любой из существующих, решение должно меняться существенно.
- Перерасчёт при удалении или добавлении новых точек должен занимать существенное время.
- Расчёт должен быть выполним с помощью компьютерной программы (с заранее вбитыми исходными данными) не более чем за несколько минут.

Желательные свойства алгоритма:
- Расчёт должен быть хотя бы теоретически выполним на полигоне без помощи карты при хорошем глазомере и пространственном воображении за время от часов до десятков часов.

Замеченные проблемы:
- Учитывая потенциально большое количество исходных точек, напрашивается идея использовать рекурсию, то есть, посчитать по N исходных точек M < N новых точек (центры каких-нибудь отрезков или треугольников и т. п.), после чего повторить расчёт для этих M и так далее, пока их не останется 2 или 3 и ответ не станет очевидным. К сожалению, все алгоритмы, которые я придумал и запрограммировал к данному моменту, при N > 6 дают не уменьшение, а увеличение числа точек с каждой итерацией.

В общем, нужны свежие оригинальные идеи, сколь угодно безумные.


Сообщение отредактировано: Jolaf, Jul 21 2011, 07:36 PM

Я правильно понял, что все простые геометрические алгоритмы тебя не устраивают именно в силу того, что простые алгоритмы достаточно устойчивы к добавлению новых точек?
Т.е. если игрок найдет 29 точек из 30, то его рассчетный "центр" будет очень близко к "центру" карты, построенной по всем 30 точкам? А по сути модели, он конечно должен очень сильно ошибиться в такой ситуации.

Если это основная причина, по которой тебя не устраивают геометрические алгоритмы, то можно сделать несколько видов точек. Например:
точки типа А имеют "вес", по которому находится "центр" полигона.
точки типа Б "веса" не имеют; зато они "выключают" все точки типа А на опредленном расстоянии от себя. Т.е. точка А не имеет веса, если в радиусе R от нее есть точка типа Б.
В такой ситуации единственная пропущенная точка Б, которая выключает сразу несколько точек типа А, значительно влияет на итоговый результат.

Это тупо пример, можно сделать больше видов точек, так, чтобы они влияли друг на друга: изменяли веса соседей, включали и выключали веса соседей в определенных комбинациях и т.п. в зависимости от твоих потребностей.

Это конечно если я правильно понял всю совокупность причин, по которой тебя не устраивает простая геометрическая модель, в которой нужно найти "центр тяжести" точек на полигоне.

Сообщение отредактировано: elraen, Jul 21 2011, 09:02 PM

Я правильно понял, что все простые геометрические алгоритмы тебя не  устраивают именно в силу того, что простые алгоритмы достаточно устойчивы к добавлению новых точек?

Да, это одна из причин.

Вторая - большое количество операций и накапливающаяся ошибка при ручном расчёте.

можно сделать несколько видов точек

Идея крутая, спасибо, подумаю её. Пока вижу две проблемы.

Во-первых, по условию задачи (сейчас допишу) выключать точки из расчёта нельзя, каждая должна влиять на результат.

Во-вторых:

Это конечно если я правильно понял всю совокупность причин, по которой тебя не устраивает простая геометрическая модель, в которой нужно найти "центр тяжести" точек на полигоне.

Найти "центр тяжести" тоже непросто без компьютера, тем более геометрически.

Ну про выключение точек - это была просто одна из мыслей, как можно реализовать идею нескольких видов точек. Основная идея - это именно несколько видов точек.

Центр тяжести геометрически как раз ищется не очень сложно, но при большом количестве точек ошибка конечно будет накапливаться очень заметно.
Но как раз разными видами точек по идее можно бороться с накапливающейся ошибкой - т.к. алгоритм фактически бьется на несколько частей, в каждой из которых точек меньше.

Центр тяжести геометрически как раз ищется не очень сложно

Например как? (вдруг я не вижу чего-то очевидного)

При равных весах точек:
Центр тяжести отрезка - его середина.
Центр тяжести треугольника - пересечение медиан.

Это значит, если количество точек - степень двойки, тройки или их комбинации (2*3^2 например) решаются вообще не особенно задумываясь.
При другом количестве точек тоже, в общем, ищется. В конце концов, всегда можно лишние точки (больше, чем ближайшая комбинация степеней двойки и тройки) учитывать, находя центр тяжести отрезка с центром тяжести между всей остальной системой и конкретной лишней точкой - просто у центра тяжести всей остальной системы считать как точку с весом всех тех точек, чьим центром тяжести она является.

Короче, с циркулем, линейкой и ровной поверхностью за 20 минут можно посчитать центр тяжести любого разумного количества (штук до 50 точно) точек.

Сообщение отредактировано: elraen, Jul 22 2011, 08:53 AM

можно лишние точки (больше, чем ближайшая комбинация степеней двойки и тройки) учитывать, находя центр тяжести отрезка с центром тяжести между всей остальной системой и конкретной лишней точкой

Окей, вот у тебя есть центр тяжести остальной системы с весом, скажем, 28. И есть ещё одна точка, с весом, очевидно, 1. Как будем искать центр тяжести?

Сообщение отредактировано: Jolaf, Jul 22 2011, 08:58 AM

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

Более того, если точек 30, то ты сначала ищешь центр тяжести двух оставшихся точек, а потому отрезок между ним и цетром масс остальной системы делится уже не на 29 частей, а на 15, что уже лучше.

Сообщение отредактировано: elraen, Jul 22 2011, 09:04 AM

Да, на 29 частей циркулем и линейкой делить невесело

То-то и оно. Очень громоздко получается, и занудно. Хочется элегантного решения. Грубо говоря, больше думать и меньше считать.

Я вот сейчас думаю в сторону алгоритма, в котором нужно правильно (анализ может занять приличное время, но требует смотреть и измерять, а не рисовать) выбрать первую точку, потом вторую, как первую из оставшихся, и из этой последовательности потом как-то высчитывать центр...

С учетом того, что такое занудство - разовое, это не так уж и плохо.

Я вот сейчас думаю в сторону алгоритма, в котором нужно правильно (анализ может занять приличное время, но требует смотреть и измерять, а не рисовать) выбрать первую точку, потом вторую, как первую из оставшихся, и из этой последовательности потом как-то высчитывать центр...

Это довольно хорошая мысль.

Тебе это для "Ночи в тоскливом октябре" или ты это просто в качестве примера привел?

Есть вот какие идеи, которые могут подойти, а могут и не подойти:
1. Учитывать возраст точки. Скажем, нужно идти от старых точек к новым, или у старых точек могут быть какие-то дополнительные свойства (другой тип точек для самых старых точек?).
2. Добавить к точкам связи. Скажем, у каждой точки есть направленные связи. Дальше считаем направленные связи как векторную сумму и получаем финальную точку. А как точку начала отсчета, от которой будет откладываться векторная сумма, можно взять центр тяжести точек другого типа, которых будет немного.

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

С учетом того, что такое занудство - разовое, это не так уж и плохо.

Оно не разовое, в том-то и дело. По мере появления в раскладе новых точек или исчезновения старых придётся пересчитывать.

Тебе это для "Ночи в тоскливом октябре" или ты это просто в качестве примера привел?

Ну, вообще конечно для.

Учитывать возраст точки
Добавить к точкам связи

Круто! Подумаю над этим.

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

Общего алгоритма не предложу, но вот именно это свойство я бы моделировал заданием двух разных алгоритмов - для четного и нечетного числа точек.

Общего алгоритма не предложу, но вот именно это свойство я бы моделировал заданием двух разных алгоритмов - для четного и нечетного числа точек.

О, крутая мысль, спасибо!

Ещё к предложению Юры можно добавить, что вес точки может быть как положительным, так и отрицательным.
А четность количества точек, например, меняет все знаки для определённого набора точек.

Ещё к предложению Юры можно добавить, что вес точки может быть как положительным, так и отрицательным.
А четность количества точек, например, меняет все знаки для определённого набора точек.

Ага, тоже круто.

Вопрос в том, что дальше делать с этими весами? На компе-то, понятно, можно посчитать физический центр тяжести и всё. А на бумаге, карандашом и линейкой?

С циркулем центр тяжести ищется легко. Только с линейкой - тоже, но точность будет существенно ниже.

Сообщение отредактировано: elraen, Jul 22 2011, 08:40 AM

С циркулем центр тяжести ищется легко. Только с линейкой - тоже, но точность будет существенно ниже.

Можешь описать алгоритм? Алгебраически всё понятно - берём среднее арифметическое по одной координате и по другой, и готово. А геометрически?

(речь о центре тяжести не плоской фигуры, а набора точечных равных весов на плоскости)

Можешь описать алгоритм? Алгебраически всё понятно - берём среднее арифметическое по одной координате и по другой, и готово. А геометрически?

(речь о центре тяжести не плоской фигуры, а набора точечных равных весов на плоскости)
[right][snapback]380592[/snapback][/right]

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

Понятно, что в любом частном случае это неоптимальный метод решения, но, естественно, вывести оптимальный способ решения в общем случае невозможно.

Сообщение отредактировано: elraen, Aug 9 2011, 05:45 PM

Если тебе нужен способ, который просто работает для любого количества точек - то центр тяжести в системе из двух точек находится на отрезке, соединяющем эти точки на расстоянии от точек, пропорциональном весам точек (т.е. середина для равных весов). При этом вес центра тяжести равняется сумме весов точек, входящих в систему. Это свойство позволяет найти центр тяжести системы из любого количества точек:
Берем произвольные две точки, находим центр тяжести системы, ставим на карту, записываем его вес, исходные две точки вычеркиваем. Повторяем до тех пор, пока не останется одна последняя точка - она и будет центром тяжести системы.

Н-да, громоздко. Для, скажем, 30 точек задолбаешься считать. Ладно, будем искать другие пути.

В абсолютно любом частном случае можно навскидку найти решение проще, подумав 10 секунд.
Другое дело, что даже в частных случаях получается чуть-чуть громоздко - но с другой стороны я так понял, что реально тебе нужно, чтобы игроки тратили хотя бы минут 10 на решение этой задачи.

Главный минус такого варианта (если делать его в лоб в приведенном виде) - в том, что пропуск одной (двух, трех) точек вблизи центра тяжести почти никак не влияет на результат.
Я уже писал выше, что в связи с этим свойством, такая модель без дополнений не подходит, нужны разные типы точек, которые по-разному учитываются. И даже предлагал всякие варианты, которые приходили мне в голову.

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

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

Ну да. Я думал об это именно как об элементе. Окей, пошёл думать дальше. Спасибо.

на бумаге это делается элементарно например, на миллиметровке -
ставим точки с весами по координатам.
по каждой координате берём сумму (координата точки * вес точки)
делим на общее кол-во точек
получаем координаты центра масс

на обычной бумаге - сложнее, но тоже можно упростить, введя координаты(просто нарисовав оси)

без бумаги/ручки, а в уме - тяжело, да.

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

для примерного подсчёта достаточно срисовать путём налоожения с карты на клетчатую (5 мм) бумагу и проделать то же самое. Точность - +- 5 мм на карте, что конечно немало, но зависит от масштаба.

Может быть, скажу бред, но тем не менее, такая идея:

1. Найти самую внешнюю и самую внутреннюю ломанную фигуру, т.е. внешний и внутренний "круги силы"

2. Найти их центры тяжестей.

3. Искомый центр системы находится на прямой, соединяющей центры тяжестей внутренней и внешней фигур, его расположение зависит от количества внутренних фигур - "кругов силы" и количества точек во внешней и внутренней.

Идея прикольная -- вся сложность в том, как эти круги провести однозначно.

А какие могут быть неоднозначности ?

Делаешь строго выпуклые фигуры - и вперед.

А, вот если ограничивать условием выпуклости...

1. Найти самую внешнюю и самую внутреннюю ломанную фигуру, т.е. внешний и внутренний "круги силы"
2. Найти их центры тяжестей.
3. Искомый центр системы находится на прямой, соединяющей центры тяжестей внутренней и внешней фигур, его расположение зависит от количества внутренних фигур - "кругов силы" и количества точек во внешней и внутренней.

Звучит круто.
Самая большая выпуклая фигура - ок.
Что такое самая внутренняя выпуклая фигура? Самая маленькая?
Видится проблема - положение точек, не относящихся к внутренней и внешней фигурам, никак не влияет на результат, пока не пересекает границы фигур, я прав?

Блин. Ну что значит самая внутренняя фигура ?

Построй самую внешнюю и выкинь ее точки. Построй на новом наборе самую внешнюю. И так, пока не останется одна, последняя фигура. Вот она и есть самая внутренняя.

Положение точек, не относящихся к этим фигурам ВЛИЯЮТ на результат на этапе построения, так как ОПРЕДЕЛЯЮТ, что же такое есть самая внешняя и самая внутренняя фигуры. Добавление одной точки приводит к потребности перестраивать последовательность таких фигур - не всю, но возможно существенную ее часть.

Построй самую внешнюю и выкинь ее точки. Построй на новом наборе самую внешнюю. И так, пока не останется одна, последняя фигура. Вот она и есть самая внутренняя.

Понял, да. Может сработать. Спасибо, буду думать.


Сообщение отредактировано: Jolaf, Jul 22 2011, 11:59 AM

Кстати, приятный бонус такого метода.

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

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

Попробовал. Замечены следующие проблемы:
- Расстояние между центрами внешнего и внутреннего кругов в подавляющем большинстве случаев очень невелико.
- Очень мало смысла прятать что-либо на уже известном коротком отрезке - в условиях полигона он наверняка будет просматриваться.
- После небольшой тренировки, глядя на карту, я могу сходу, без всякого расчёта, попасть в точку будущего центра с весьма приличной точностью.

Мораль: нужно что-то придумать, чтобы итоговый центр не стремился к центру масс системы, и таким образом не был очевиден.

Ну то, что центр масс более-менее очевиден - слабое место всех моделей, так или иначе завязанных на центр масс.

Возможные решения:
- большой полигон (мое любимое решение многих проблем ролевых игр
- разные веса точек, отрицательные массы
- попробовать зайти в суммы векторов, как я писал выше.
- что-то еще

Сообщение отредактировано: elraen, Jul 22 2011, 02:28 PM

Я вот еще предложил Йолафу вариант с хэш-функцией по множеству координат.

Я вероятно тупой, но как ты будешь считать хэш-функцию, если у тебя есть карта, карандаш и линейка? У тебя даже точной системы координат нет (да, карта возможно разбита на квадраты, но есть разница между здоровыми квадратами и точными координатами).

А что потом делают с найденной точкой ? Просто ищут в ней ценности или проводят дорогой ритуал ?

Т.е. насколько дорого "использовать" найденную точку в сравнении с ее расчетом ?

А что потом делают с найденной точкой?

Проводят в ней Самый Важный Ритуал. Тот, кто оказался самым умным и единственный из всех посчитал правильно - заведомо выиграл игру. Тот, кто посчитал неправильно и оказался такой сукой, что ему никто не сказал правильного ответа - пролетел мимо самого интересного.

Т.е. насколько дорого "использовать" найденную точку в сравнении с ее расчетом?

Не понял вопроса.

Пока самым толковым по результату показал себя следующий метод:

Найти три точки, образующие самый маленький треугольник. Выкинуть их. Повторять. Центром объявить центр последнего треугольника (если остаются одна или две точки - разрулить как-нибудь).

Выглядит нелепо и нелогично, и этим мне не нравится, но зато в половине случаев даёт результат вблизи центра масс, а в половине - черт знает где.

А как ты вообще собираешься определять самый маленький треугольник? Считать площадь? Периметр?

Площадь вообще не годится - для точек почти на одной прямой, на большом расстоянии друг от друга вполне реально получить треугольник с углом 178 градусов. Его площадь на коленке будет считаться очень неточно, в итоге сравнение с маленьким остроугольным треугольником будет очень неточным.

А как ты вообще собираешься определять самый маленький треугольник?

Объявляем размером треугольника длину его самой длинной стороны. Минимизируем по этому параметру.

Выбрать самую любую (северную, центральную, и т.д.) точку, начальное направление (например на тот же север).
Берем начальное положение и от него ищем ближайшую (в смысле поворота) влево точку. Выкидываем первую из рассмотрения. Теперь начальное направление - то которое соединяет выкинутую точку и найденную. Повторяем, пока не найдем последнюю точку. Для получения искомой точки, например повторить последний отрезок второй раз. Или найти тот же центр треугольника из трех последних точек.
Если выбирать за начальную точку - точку с краю, то получится закручивающаяся внутрь спираль, устойчивая к добавлению внешних точек. Так что лучше или выбирать за первую точку что-то в центре, либо например искать точку от направления *последний построенный луч + угол, зависящий от числа точек*. Даже при линейной зависимости от факта добавления одной точки всё сбивается.
Итоговую точку уносит в рандомном направлении за россыпь исходных точек.
Правда, если без модификаций, то на бумаге считается быстро. При хорошем пространственном воображении считается на местности.

Хорошая идея.

Навскиду сложности:
- с начальной точкой в центре все тоже будет достаточно устойчиво к добавлению новых точек. В части случаев новая точка вообще ни на что не будет влиять. По условиям это очень плохо.
- Идея "последний построенный луч + угол" плоха тем, что скалдывать углы на бумаге на коленке еще хуже, чем вышепреведенные заморочки с центром тяжести.
- Действительно быстро считается.

Может быть нужно переходить не в новую точку, а в удвоенное растояние от предыдущей? Это с одной стороны существенно проще, чем складывание углов, а с другой более чувствительно к добавлению новых точек. Плюс вместо закрчивающейся/раскручивающейся спирали будет бросать вокруг основного скопления точек. Плюс финальная точка попадет не на существующую точку, а в поле. Йолаф этого не написал, но вообще это важное условие, "центр" системы не должен совпадать с существующеми точками.

Навскиду сложности:
- с начальной точкой в центре все тоже будет достаточно устойчиво к добавлению новых точек. В части случаев новая точка вообще ни на что не будет влиять. По условиям это очень плохо.
- Идея "последний построенный луч + угол" плоха тем, что скалдывать углы на бумаге на коленке еще хуже, чем вышепреведенные заморочки с центром тяжести.
- Действительно быстро считается.
[right][snapback]379502[/snapback][/right]

Добавлямый угол можно при желании сделать каким-нибудь удобным. П/(2^n) - строится не слишком сложно. Впрочем, как и деление отрезка на n частей. Если игрок применяет альтернативные пути вроде "построить угол и откромсать шаблон от ненужного угла карты", то и совсен просто.
Да, быстро - это правда.

Может быть нужно переходить не в новую точку, а в удвоенное растояние от предыдущей? Это с одной стороны существенно проще, чем складывание углов, а с другой более чувствительно к добавлению новых точек. Плюс вместо закрчивающейся/раскручивающейся спирали будет бросать вокруг основного скопления точек. Плюс финальная точка попадет не на существующую точку, а в поле. Йолаф этого не написал, но вообще это важное условие, "центр" системы не должен совпадать с существующеми точками.
[right][snapback]379502[/snapback][/right]

Да, конечно же, должно попадать в поле. Я потому и предлагала для итоговой точки повторять последний отрезок.
Но твоя версия лучше - алгоритм однообразнее, что хорошо.

Ребят, я наверное тормоз - но отрезок или угол на три равных части разбить не сумею, хоть убей.
Йолаф, можешь раскрыть что-то о точках поподробнее? Есть ли у них какие-то добавочные определимые свойства, как их находят и т.п.? Сможешь ли ты ставить их на карту как захочешь, или придется к чему-то несместимому привязываться?
Пока сырая мысль: взять самый длинный и самый короткий отрезки на карте, сложить. Вычесть сумму всех отрезков, идущих параллельно меридиану с погрешностью не более n градусов, получить базовую меру длины. Посчитать количество отрезков запад-восток, получить число m. Посчитать все точки на карте, получить число k. От пересечения самых длинных отрезков "С-Ю" и "З-В" отложить m базовых длин по азимуту {45 градусов умножить на k}. Выполнять ритуал в этом месте.
ТАкое возможно только если ты точки ставишь более-менее произвольно.
Наверняка в этой мысли есть еще какая-нить засада, но пока я ее не вижу.

Ребят, я наверное тормоз - но отрезок или угол на три равных части разбить не сумею, хоть убей.
[right][snapback]379526[/snapback][/right]

Отрезок на три части делится при помощи теоремы Фалеса. А про угол пару веков назад доказали, что это невозможно : )

Сообщение отредактировано: Алестен, Jul 23 2011, 10:47 AM

Отрезок на три части делится при помощи теоремы Фалеса. А про угол пару веков назад доказали, что это невозможно : )
[right][snapback]379527[/snapback][/right]

Я наверно совсем тормоз.
Берем угол, ставим на лучах по точке, равноудаленной от центра, соединяем. Полученный отрезок делим натрое вышеуказанным способом. Из вершины угла проводим лучи к "делящим" точкам на отрезке. Чем не трисекция?
И еще, залез сейчас в яндух - говорят, что Фалес писал о равенстве отрезков, отсекаемых параллельными прямыми на двух произвольных. В принципе, кстати, имея второй лист бумаги и две линейки можно и по ней рассечь отрезок на три равных части. Но это несколько противоречит условиям.
ЗЫ я сейчас не полемизирую и не стебусь, геометрия была давно и многие методы я крепко подзабыл.

Я наверно совсем тормоз.
Берем угол, ставим на лучах по точке, равноудаленной от центра, соединяем. Полученный отрезок делим натрое вышеуказанным способом. Из вершины угла проводим лучи к "делящим" точкам на отрезке. Чем не трисекция?

Они не будут равными. Доказывать лень (без чертежа это не очень понятно будет), предлагаю просто взять лист бумаги, построить на нем большой тупой угол (например 150 градусов) и попробовать сделать предложенныое построение. Будет на глаз видно, что получившиеся углы неодинаковые.

Что касается теоремы Фалеса, то да, для разделения отрезка на равные части нужно две линейки, чтобы строить паралельные прямые от луча, построенного из одной из вершин отрезка, который нужно делить на части.

Они не будут равными. Доказывать лень (без чертежа это не очень понятно будет), предлагаю просто взять лист бумаги, построить на нем большой тупой угол (например 150 градусов) и попробовать сделать предложенныое построение. Будет на глаз видно, что получившиеся углы неодинаковые.
[right][snapback]379541[/snapback][/right]

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

Что касается теоремы Фалеса, то да, для разделения отрезка на равные части нужно две линейки, чтобы строить паралельные прямые от луча, построенного из одной из вершин отрезка, который нужно делить на части.
[right][snapback]379541[/snapback][/right]

Или линейку и любой шаблон окружности.

Йолаф, можешь раскрыть что-то о точках поподробнее? Есть ли у них какие-то добавочные определимые свойства, как их находят и т.п.? Сможешь ли ты ставить их на карту как захочешь, или придется к чему-то несместимому привязываться?

Точки - это локации, где живут персонажи (грубо говоря, у каждого свой дом). Сами точки известны заранее (находятся в удобных для строяка и жилья местах полигона), но неизвестно, какие из них будут заселены к тому моменту, когда дойдёт до дела (а кого-то могут и убить, тогда точка не считается), а также неизвестно, кто из персонажей имеет отношение к делу, а кто тут просто живёт. Таким образом, выяснение того, какие точки "считаются", а какие нет - важная игровая задача.

Ещё одна не очень крутая, но жизнеспособная конструкция.

Каждой точке присваиваем "собственный круг" радиуса, равного половине дистанции до ближайшей другой точки. Как видно, "собственные круги" точек не пересекаются, хотя могут соприкасаться.

Далее, каждой точке присваиваем "несобственный круг", радиус которого равен расстоянию до ближайшего собственного круга другой точки. Очевидно, несобственный круг любой точки никогда не меньше её собственного круга и обязательно касается как минимум одного собственного круга (других точек). Несобственные круги могут пересекаться.

Далее найдём две точки с самыми большими несобственными кругами. Отрезок, соединяющий эти две точки, поделим на две части пропорционально радиусам их несобственных кругов. Границу частей отрезка назовём Центром.

Упрощённый вариант - строим для каждой точки круг радиусом, равным расстоянию от данной точки до ближайшей соседней. Опять же, берём два самых больших круга.

Основная проблема: понятие "два самых больших круга" при ручном расчёте на бумаге может оказаться неоднозначным, решение может "скакать" из одной точки в другую от небольших геометрических ошибок.


Сообщение отредактировано: Jolaf, Jul 25 2011, 04:11 PM

Отсортировать пары точек по возрастанию расстояния между ними, взять пятнадцатую пару (например, середину соединяющего их отрезка). Ну и как сложность расчётов варьировать, понятно.

Неустойчивость к добавлению точки скорее всего будет (потому что новая точка будет достаточно близка хотя бы к каким-то, и этим всё сдвинет).

Устойчивость к шевелению частичная - если шевелить точки, не участвующие в пятнадцатой паре, то скорее всего конечный результат не поменяется (даже если будут "прыгать" отрезки 1..14).

Важно только чтобы пятнадцатая пара не прыгала. Для этого надо выбрать либо точки, либо число "пятнадцать" так, чтобы пятнадцатая пара по расстоянию ощутимо отличалась от 14-й и 16-й.

--

А вообще у тебя аццкие требования какие-то, причём скорее всего их можно ослабить. Например, требовать не неустойчивость к добавлению произвольной точки, а только к удалению точки из полного набора (ведь не важно, насколько близки будут два неправильных решения?).

Отсортировать пары точек по возрастанию расстояния между ними, взять пятнадцатую пару (например, середину соединяющего их отрезка).

Мм, очень неустойчиво к малым ошибкам измерений. При 30 точках на листе А4 может быть несколько пар претендующих на то, что именно она 15-я, и отделить правильную 15-ю от неправильной с помощью циркуля может быть сложно.

Для этого надо выбрать либо точки, либо число "пятнадцать" так, чтобы пятнадцатая пара по расстоянию ощутимо отличалась от 14-й и 16-й.

В смысле, выбрать и озвучить игрокам число "15" уже после того, как известен конкретный расклад точек на полигоне?

А вообще у тебя аццкие требования какие-то, причём скорее всего их можно ослабить. Например, требовать не неустойчивость к добавлению произвольной точки, а только к удалению точки из полного набора

Окей, давай переформулирую. Есть произвольный "полный" набор из M точек. Из них (неважно как) выбирается "рабочий" набор из N точек, для которых и ищется решение. Хорошо бы, чтобы хотя бы в половине случае выключение из рабочего набора одной точки или добавление в рабочий набор ранее отсутствующей в нём точки из полного набора существенно меняло решение.

То есть, в рамках игры мы рассматриваем ситуации вида "а игрока Х оказывается убили, значит его дом больше не считается" и "мы считали, что дом Y пустует, а оказывается там кто-то живёт, значит теперь его нужно включить в расчёт".

ведь не важно, насколько близки будут два неправильных решения?

Да, неважно.

> выбрать и озвучить игрокам число "15" уже после
Да.

Насчёт уточнения условия я не понял, и вообще уже не уверен что понимаю мотивацию и для оригинального условия.

С учётом чувствительности к добавлению точкек не имеет смысла проводит расчёт до последнего момента (если только он не может проводиться инкрементально, что ты не указывал в требованиях).

Почему не сделать просто оракул, к которому приходишь с набором точек, которые ты накопал, и если набор правильный, он тебя посылает в правильное место, а если нет - в гребеня?

С учётом чувствительности к добавлению точек не имеет смысла проводит расчёт до последнего момента

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

Почему не сделать просто оракул, к которому приходишь с набором точек, которые ты накопал, и если набор правильный, он тебя посылает в правильное место, а если нет - в гребеня?

Потому же, почему на Фронтире нельзя было вбить в компьютер пять кодов правильных светлячков и получить код чудо-белка. Потому что это поле для игры.

Я правильно понимаю, что мастера сами до последнего момента не знают правильного ответа, потому что не контролируют, кого убьют и кто в каком домике поселится? Т.е. известно только, что активизируется какое-то подмножество заранее заданного множества точек, но какое - хз?

Я правильно понимаю, что мастера сами до последнего момента не знают правильного ответа, потому что не контролируют, кого убьют и кто в каком домике поселится? Т.е. известно только, что активизируется какое-то подмножество заранее заданного множества точек, но какое - хз?

Расположение точек считается окончательным за несколько часов до момента Х, после этого никакие убийства и переезды не роляют. Так что и у мастеров, и у игроков есть несколько часов на то, чтобы всё аккуратно посчитать. Мастера это будут делать вероятно автоматически на компе.

Если вдруг кому интересно, вот программка, реализующая некоторые из упомянутых тут алгоритмов:
http://dl.dropbox.com/u/1115994/NitLO/Software/Night.py

Написана на Python, запускается так:

python Night.py

при этом печатает опции запуска и клавиши управления.

Для запуска на Ubuntu требуется:
sudo apt-get install python-pygame python-shapely

На Windows:
Python 2.7 (http://python.org/download/)
PyGame 1.9 (http://pygame.org/download.shtml)
Shapely 1.2 (http://pypi.python.org/pypi/Shapely#downloads)


Сообщение отредактировано: Jolaf, May 9 2012, 10:24 PM

Я заимплементил то что предлагал, http://pastebin.com/SqL4rKi0 .

Я заимплементил то что предлагал

О, круто, спасибо. Добавил.

Замеченная на практике проблема - ответ оказывается посередине между двумя близко расположенными точками. В условиях полигона это палевно.

"Перевернул" алгоритм, считая пары не с маленькой, а с большой. Вроде лучше получилось (см.)


Сообщение отредактировано: Jolaf, Aug 10 2011, 04:00 PM

Чтобы точки были не слишком близко расположенными - лучше выбрать k чуть побольше.

Если начинать с больших, то может получиться что точки близкие к центру вообще ни на что не влияют, а так (если предположить что они распределены более или менее равномерно) получается терпимо.

Кроме того, сравнивать большие расстояния тяжело, как и находить середину длинного отрезка.

Оригинальный способ очень хорошо подходит для выполнения на игре: приблизительно намечаешь на карте, а в тех случаях когда сомневаешься идёшь и меряешь в шагах. В итоге задолбаешься, исходишь весь полигон, и все будут видеть, чем ты занимаешься (и, может быть, запалят точки про которые знал только ты).

А чтобы не было в густонаселённой местности - можно вместо середины отрезка брать вершину равностороннего треугольника, противолежающую стороне, являющейся искомым отрезком. Из двух вариантов брать самый северный.

А чтобы не было в густонаселённой местности - можно вместо середины отрезка брать вершину равностороннего треугольника, противолежающую стороне, являющейся искомым отрезком. Из двух вариантов брать самый северный.

Мм, всё равно будет очень близко (скорее всего в прямой видимости) от населённой локации. Но можно подумать ещё в эту сторону, да.

Если потенциально интересные точки расставляют до игры мастера, то можно просто не ставить слишком близко точки на открытой местности. А в лесу с подлеском 50м - уже достаточно большое расстояние.

Я бы еще поразмышлял о том, что точку проведения ритуала открытия/закрытия будет тупо слышно - если нет дождя и ветра, в лесу голоса слышно очень хорошо, особенно ночью.

Сообщение отредактировано: elraen, Aug 10 2011, 06:50 PM

Если потенциально интересные точки расставляют до игры мастера, то можно просто не ставить слишком близко точки на открытой местности. А в лесу с подлеском 50м - уже достаточно большое расстояние.

В этом ты конечно прав.

Я бы еще поразмышлял о том, что точку проведения ритуала открытия/закрытия будет тупо слышно - если нет дождя и ветра, в лесу голоса слышно очень хорошо, особенно ночью.

Если всё сделать правильно, то точку станет слышно только начиная с момента Х, когда те, кто подойдёт позже на шум смогут быть уже только просто зрителями.

Если начинать с больших, то может получиться что точки близкие к центру вообще ни на что не влияют, а так (если предположить что они распределены более или менее равномерно) получается терпимо.

Чёрт, да, ты прав.

Кроме того, сравнивать большие расстояния тяжело, как и находить середину длинного отрезка.

Мм, зависит от инструментария. Если у тебя есть точная карта, то чем длиннее отрезок, тем проще искать середину и меньше относительная погрешность измерения. Я собственно предполагал, что у игроков будут мастерские точные карты с отмеченными всеми потенциально важными точками, и игрокам остаётся выяснить, какие из заданных точек важны и выполнить построение на бумаге.

А вот если точной карты нет, и расстояния нужно мерять шагами, то да, твой способ оказывается охренительно крутым. Я его запомнил, спасибо!

Если есть точная карта, то не обязательно геометрические алгоритмы: точки можно пронумеровать и использовать любой флоранохэш.

Основной недостаток - невозможны сюрпризы в виде совсем неожиданных точек, если только не делать Совсем Точной Карты, которую можно достать если напрячься, но это уже совсем искусственно.

Ну и неизящно.

Сообщение отредактировано: Vlad, Aug 10 2011, 08:23 PM

Если есть точная карта, то не обязательно геометрические алгоритмы: точки можно пронумеровать и использовать любой флоранохэш.

Геометрические алгоритмы здесь догма. То есть, чертить на бумаге с линейкой - в духе первоисточника, а считать хэш-функции - не в духе.

Основной недостаток - невозможны сюрпризы в виде совсем неожиданных точек

Это проблема, да, но не очень важная. Главное, чтобы Центр был совсем неожиданным.

Дамы и господа!

А не слишком ли сложно мы мыслим? Наверняка поиграть захочется не только суровым технорям, но и "блондинкам гуманитариям".

Вот экстримально бредовый геометрический вариант:
За основу взять советский аналог развивающей детской игрушки:
http://www.elc-russia.ru/jekran-dlja-risov...vat-spiral.html

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

Количество точек = <номер отверстия, куда ставит карандаш> + 4 (8).

Изначально каждому игроку выдается свое зубчатое колесо.

Результатом будет область в центре спирали.

Если удастся найти это чудо инженерной мысли дома, то передам его в безвозмездное пользование МГ.

Совсем не геометрический вариант предложил в теме с вопросами по игре.

Мне кажется, это вы как раз сложно мыслите.

Мало что может быть проще циркуля и линейки.

Мало что может быть проще циркуля и линейки.
[right][snapback]415040[/snapback][/right]

Игрушка, рассчитанная на детей от 3 лет всяко проще, чем циркуль, с которым знакомятся, если не ошибаюсь, в средней школе.

Игрушка, рассчитанная на детей от 3 лет всяко проще, чем циркуль, с которым знакомятся, если не ошибаюсь, в средней школе.

Тем не менее, циркуль проще. Парадокс.

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

Хотя судя по тексту тут скорее потребуется не напортачить и аккуратно нарисовать, а не считать. Художники и т.п. люди в плюсе

Сообщение отредактировано: Анжей, Feb 10 2012, 09:36 PM

Анжей прав.