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

[Kisa]

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

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

[Юра]

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

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

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

[Jolaf]

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

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

[Jolaf]

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

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

[Алестен]

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

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

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

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

[Jolaf]

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

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

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

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

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

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


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

[Vlad]

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

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

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

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

--

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

[Jolaf]

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

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

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

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

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

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

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

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

Да, неважно.

[Vlad]

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

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

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

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

[Jolaf]

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

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

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

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

[Vlad]

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

[Jolaf]

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

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

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

[Jolaf]

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

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

[Jolaf]

Если вдруг кому интересно, вот программка, реализующая некоторые из упомянутых тут алгоритмов:
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

[Юра]

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

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

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

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

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

[Jolaf]

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

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

[Юра]

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

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

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

[Jolaf]

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

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

[Vlad]

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

[Jolaf]

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

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

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

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


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