если существует разрезание многоугольника на две равные части, то существует разрезание многоугольника на два равных многоугольника
Замешательство перестаёт быть лёгким. Если под «частью» понимается ломаная линия, то утверждение очевидно (как очевидно то, что обладающий осевой симметрией многоугольник может быть побит на два конгруэнтных: ось симметрии и есть этот разрез). В противном случае я не понял вообще, что имелось в виду. Похоже, мне пора спать -_-.
Подход ребят из НР (а они рассматривают и случай гладких криволинейных границ) меня радует сильнее. Ох, и молодцы же у них в HP Labs…
Вообще, по обеим статьям (я немедленно схоронил статью, указанную @winger-ом, разумеется) хочется отметить, что авторы к вопросу подошли очень обстоятельно. Особенно радует высказывание из статьи по ссылке @winger-а:
We are interested in a split polyline that has minimum complexity but is not a single line segment. In this case, we call the partition trivial and the problem reduces to symmetry detection which has been solved in linear time in [2].
Т.е. класс фигур, которым достаточно линейного разреза, авторам не интересен изначально как тривиальный.
Пока, правда, пробежал статью только бегло, поэтому могу ошибиться в суждениях. Надо бы попробовать реализовать предложенные ими алгоритмы. Было бы здорово посмотреть на такой рассекатель где-нибудь на JS…
… Ещё, наверное, неплохо было бы рекурсивно применить эту рандомную процедурку уже для генерации квадратных блоков лабиринта разной скважности и направленности. Полученный лабиринт (где-нибудь 3х5 блоков), наверное, уже будет весьма интересной штуковиной.
Удивлён, что никто ещё не пошутил про это (лабиринт в пару строк JS, оригинальная идея была написана на терминалах, в одну строку). Изначально, конечно, сама идея шуточная. Там, конечно, речи нет ни о гарантированной полной связности лабиринта, ни о чём-то ещё детерминированном, т.к. рандом.
Зато, например, настраивать «общую направленность» или степень заполнения можно уже там, а затем, для придания нужной формы и свойств, детерминированными методами склеивать отдельные участки лабиринта (с разной «общей направленностью»), а также «прорубать» проходы для обеспечения требуемой связности участков. Так, для восстановления связности можно выбирать не жадным способом, а именно минимальное число проходов; для связи между блоками — выбирать область с прицелом на наименьший (а может, лучше наибольший?) общий путь прохождения.
… Или про это: генератор уровней для классических шутеров Oblidge.
Кстати, автор последнего, уже без шуток, генерирует именно проходимые уровни. По своему опыту отмечу, что порой не такие уж и плохие, а иногда и вовсе неплохие. Особенно радует в нём функция «сгенерировать полный комплект уровней», которая создаёт целую игру (например, 32 уровня для второго дума), с возрастающими сложностью, размерами карт и количествами врагов, а также учитывает стилистические особенности отдельных уровней (map07, map30...). Впрочем, это уже очень узконаправленная штука. Да и упора на сложность лабиринта там особо никто не делал. Жду — не дождусь, когда автор всё-таки выведет из беты на сносный уровень HL1/CS16.
А если без шуток, то да, очень занятно. Вкупе с материалом про прохождение лабиринта «в условиях тумана» (когда у программы нету карты) может получиться отличная пара (генератор лабиринтов-заданий и программы-Тесеи). Если с красивым визуализатором, то можно будет и speedrun-ы смотреть.
Жесть, однако. Удивлён масштабом обсуждения, и вдвойне удивлён отсутствием ссылок на
(а) базовый уровень (Algolist)
(б) продвинутый уровень, для любителей оптимизации кода: раз, два.
Отмечу, что в самой статье говорится о нахождении точки внутри тела, а эта задача требует определения пересечения треугольника с лучом, а не отрезком (что избыточно).
Вообще, мне думается, вот этот раздел алголиста очень показан к изучению всем, кому приходится работать с вычислительной геометрией, но не по миллиону раз в секунду.
В 10ке можно было полностью настроить на манер прошлых версий. Если отличия и были — то незначительные. Шифт был нормальный, звать защитника было можно, pace control работал. Это для меня было главное.
У меня нету веб-камеры, так что снять само исполнение не выйдет.
Опишу словами: я настроил клавиатуру так, чтобы при нажатии LShift автоматически дожималась кнопка «Pace Control» (которая «плавный контроль мяча») и стрелки переключались с Left Stick на Right stick. Таким образом я, нажимая LShift, автоматически переключался в режим «нарисуй финт на стрелочках и отпусти шифт». В общем, это было точь-в-точь как в старой доброй десятой фифе.
Проще всего исполняются (и потому наиболее полезны, по крайней мере, мне)
* Heel Flick (быстро вперёд-назад) — эти два касания проще исполнить и увидеть, чем описать словами
* Радуга (быстро назад-вперёд или назад-вперёд, потом ещё раз вперёд, если в два касания) — переброс
* 360 (назад-вбок-вперёд) — ну, тут всё понятно.
Остальное я практически не использую, т.к. самые важные и полезные финты в фифе уже очень давно (наверное, прямо с момента её выхода на РС) исполняются на кнопки S, W и A. Иногда с добавлением модификаторов, но это уже вторично.
… Говорю же, DirectInput обрабатывает первым. Все сообщения Windows случаются позже.
Я же писал выше: сначала я вообще хотел писать драйвер. В пользовательском режиме я не
схвачу кнопки до фифы.
Это как? Можно, пожалуйста, пример нарисовать?
Я в лёгком замешательстве.
Замешательство перестаёт быть лёгким. Если под «частью» понимается ломаная линия, то утверждение очевидно (как очевидно то, что обладающий осевой симметрией многоугольник может быть побит на два конгруэнтных: ось симметрии и есть этот разрез). В противном случае я не понял вообще, что имелось в виду. Похоже, мне пора спать -_-.
Вообще, по обеим статьям (я немедленно схоронил статью, указанную @winger-ом, разумеется) хочется отметить, что авторы к вопросу подошли очень обстоятельно. Особенно радует высказывание из статьи по ссылке @winger-а:
Т.е. класс фигур, которым достаточно линейного разреза, авторам не интересен изначально как тривиальный.
Пока, правда, пробежал статью только бегло, поэтому могу ошибиться в суждениях. Надо бы попробовать реализовать предложенные ими алгоритмы. Было бы здорово посмотреть на такой рассекатель где-нибудь на JS…
PS. Было бы неплохо натравить их алгоритм на «ту самую» задачку, ага.
Зато, например, настраивать «общую направленность» или степень заполнения можно уже там, а затем, для придания нужной формы и свойств, детерминированными методами склеивать отдельные участки лабиринта (с разной «общей направленностью»), а также «прорубать» проходы для обеспечения требуемой связности участков. Так, для восстановления связности можно выбирать не жадным способом, а именно минимальное число проходов; для связи между блоками — выбирать область с прицелом на наименьший (а может, лучше наибольший?) общий путь прохождения.
… Или про это: генератор уровней для классических шутеров Oblidge.
Кстати, автор последнего, уже без шуток, генерирует именно проходимые уровни. По своему опыту отмечу, что порой не такие уж и плохие, а иногда и вовсе неплохие. Особенно радует в нём функция «сгенерировать полный комплект уровней», которая создаёт целую игру (например, 32 уровня для второго дума), с возрастающими сложностью, размерами карт и количествами врагов, а также учитывает стилистические особенности отдельных уровней (map07, map30...). Впрочем, это уже очень узконаправленная штука. Да и упора на сложность лабиринта там особо никто не делал. Жду — не дождусь, когда автор всё-таки выведет из беты на сносный уровень HL1/CS16.
А если без шуток, то да, очень занятно. Вкупе с материалом про прохождение лабиринта «в условиях тумана» (когда у программы нету карты) может получиться отличная пара (генератор лабиринтов-заданий и программы-Тесеи). Если с красивым визуализатором, то можно будет и speedrun-ы смотреть.
(а) базовый уровень (Algolist)
(б) продвинутый уровень, для любителей оптимизации кода: раз, два.
Отмечу, что в самой статье говорится о нахождении точки внутри тела, а эта задача требует определения пересечения треугольника с лучом, а не отрезком (что избыточно).
Вообще, мне думается, вот этот раздел алголиста очень показан к изучению всем, кому приходится работать с вычислительной геометрией, но не по миллиону раз в секунду.
хорош до первого
Думаю, стоит поправить макрос.
Опишу словами: я настроил клавиатуру так, чтобы при нажатии LShift автоматически дожималась кнопка «Pace Control» (которая «плавный контроль мяча») и стрелки переключались с Left Stick на Right stick. Таким образом я, нажимая LShift, автоматически переключался в режим «нарисуй финт на стрелочках и отпусти шифт». В общем, это было точь-в-точь как в старой доброй десятой фифе.
Проще всего исполняются (и потому наиболее полезны, по крайней мере, мне)
* Heel Flick (быстро вперёд-назад) — эти два касания проще исполнить и увидеть, чем описать словами
* Радуга (быстро назад-вперёд или назад-вперёд, потом ещё раз вперёд, если в два касания) — переброс
* 360 (назад-вбок-вперёд) — ну, тут всё понятно.
Остальное я практически не использую, т.к. самые важные и полезные финты в фифе уже очень давно (наверное, прямо с момента её выхода на РС) исполняются на кнопки S, W и A. Иногда с добавлением модификаторов, но это уже вторично.
Я же писал выше: сначала я вообще хотел писать драйвер. В пользовательском режиме я не
схвачу кнопки до фифы.
Человечек в черном или провайдер?А по-моему, все провайдеры обязаны. Разве нет?