Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 39
А не подскажете как нарисованы столь превосходные иллюстрации. Чую ручками в графическом редакторе.
И ещё, не подскажете по одной задачке на построение. Вообще в школе любимая тема была, а тут брату в 7м классе задали, и ни он ни я не смогли решить. В решебнике чушь написана. Пошёл с несделанной, а там никто не сделал, да ещё и препод на просьбу разобрать стушевалась и сказала типа времени нет. Вот теперь хочу сам разобраться.
Требуется построить треугольник по периметру, углу и высоте, проведённой не из этого угла.
Собственно угол с высотой строятся элементарно и получается пол искомого треугольника. Вторую же часть надо достроить так чтобы соблюсти периметр. И я не смог придумать адекватного способа сделать такое. А тут дело осложняется тем что это первый год изучения геометрии и даже теорема Пифагора не изучена и соответственно не может быть применена.
И ещё, не подскажете по одной задачке на построение. Вообще в школе любимая тема была, а тут брату в 7м классе задали, и ни он ни я не смогли решить. В решебнике чушь написана. Пошёл с несделанной, а там никто не сделал, да ещё и препод на просьбу разобрать стушевалась и сказала типа времени нет. Вот теперь хочу сам разобраться.
Требуется построить треугольник по периметру, углу и высоте, проведённой не из этого угла.
Собственно угол с высотой строятся элементарно и получается пол искомого треугольника. Вторую же часть надо достроить так чтобы соблюсти периметр. И я не смог придумать адекватного способа сделать такое. А тут дело осложняется тем что это первый год изучения геометрии и даже теорема Пифагора не изучена и соответственно не может быть применена.
Построение производится так: от основания высоты в сторону от вершины угла откладывается отрезок, равный «остатку» периметра. Его конец обзовём К. Затем проводится срединный перпендикуляр к отрезку между К и вершиной, из которой проведена высота. Точка, где срединный перпендикуляр пересекает сторону угла, на которую опущена высота, и будет недостающей вершиной треугольника.
Если кому интересно, откуда мы берём чёрные линии — это срединные перпендикуляры к соответствующим отрезкам.
Минут 5 не мог понять, о каких отрезках идет речь. Потом нашел-таки их. Однако, как мне кажется, было бы не плохо написать (или показать на картинке), что это за отрезки.
А в каком месте из рассмотрения выкинули ещё одного кандидата на центр поворота — середину верхней стороны прямоугольника 3x6 (на границе красной и желтой областей верхнего рисунка)? Поворот вокруг этой точки на 90 гр ничему не противоречит: угол в 180 гр делится пополам, дальние вершины переходят одна в другую… остальные концы чёрных лучей кандидатами не являются (угол, под которым из них видны две соответствующие дальние вершины, не равен половине угла при этой точке). Но красно-жёлтая точка, по крайней мере сразу, не отметается.
На всякий случай, вдруг автор не видел: Crazy Cuts: Dissecting Planar Shapes into Two Identical Parts
PS. Было бы неплохо натравить их алгоритм на «ту самую» задачку, ага.
PS. Было бы неплохо натравить их алгоритм на «ту самую» задачку, ага.
Автор не видел. но и не удивлён существованием)
В ней рассматривается только случай параллельного переноса/поворота, случай отражения (с пар. переносом) рассматривается в Partitioning a Polygon into Two Mirror Congruent Pieces
Я думал, кстати, попытаться решать эту задачку железным мозгом. Потом всё же отказался от этой мысли, ибо хотелось порисовать няшные чертежи. Почитаю, посмотрю, так ли авторы подошли к вопросу, как думал я.
Они рассматривают многоугольник как строку, описывающую его границу, и исследуют какие строки могут получиться если состыковать два одинаковых многоугольника.
И такая мысль меня тоже посещала. У этого плана есть неприятная особенность: приходится ограничиваться многоугольниками. Можно, конечно, путём некоторого секса доказать, что если существует разрезание многоугольника на две равные части, то существует разрезание многоугольника на два равных многоугольника… Но всё равно геморрой.
Этот факт вроде бы доказывается легко.
приходится ограничиваться многоугольниками
Я в лёгком замешательстве.
если существует разрезание многоугольника на две равные части, то существует разрезание многоугольника на два равных многоугольника
Замешательство перестаёт быть лёгким. Если под «частью» понимается ломаная линия, то утверждение очевидно (как очевидно то, что обладающий осевой симметрией многоугольник может быть побит на два конгруэнтных: ось симметрии и есть этот разрез). В противном случае я не понял вообще, что имелось в виду. Похоже, мне пора спать -_-.
Подход ребят из НР (а они рассматривают и случай гладких криволинейных границ) меня радует сильнее. Ох, и молодцы же у них в HP Labs…
Вообще, по обеим статьям (я немедленно схоронил статью, указанную @winger-ом, разумеется) хочется отметить, что авторы к вопросу подошли очень обстоятельно. Особенно радует высказывание из статьи по ссылке @winger-а:
Т.е. класс фигур, которым достаточно линейного разреза, авторам не интересен изначально как тривиальный.
Пока, правда, пробежал статью только бегло, поэтому могу ошибиться в суждениях. Надо бы попробовать реализовать предложенные ими алгоритмы. Было бы здорово посмотреть на такой рассекатель где-нибудь на JS…
Вообще, по обеим статьям (я немедленно схоронил статью, указанную @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…
В общем, почитаю. Но, так или иначе, этот подход фундаментально ограничен. Например, он покрывается мохнатой вагиной, если разрешить частям быть несвязными.
Его можно расширить и на случай несвязных кусков, правда сложность будет расти экспоненциально от их количества. Ваш метод тоже фундаментально ограничен — он не обобщается даже на произвольные выпуклые многоугольники (не говоря уж о фигурах с гладкими границами).
Ну, «мой метод» — это звучит слишком гордо. В России, как говорится, нет дорог, а есть направления. Я имею в виду, я пока не ставил задачу создать законченную методологию, которой на вход подаётся фигура, а она на выходе рассказывает, таки разрезабельна фигура или нет. Но у меня есть общее направление исследования. Если мне дадут конкретную фигуру, я смогу почесать в затылке, добавить к уже написанному пару-тройку критериев и найти разрезание/доказать его невозможность. И потенциально метод, основанный на движениях, мощнее. Не хотелось бы пока делать громких заявлений, но у меня есть одна мыслишка…
если разрешить частям быть несвязными
Это как? Можно, пожалуйста, пример нарисовать?
Возьмём одну из горизонталей шахматной доски. Это прямоугольник 1х8. Его точки можно разделить на два множества — принадлежащие чёрным клеткам и принадлежащие белым (ещё граница, но на неё традиционно забиваем). Каждое из этих множеств состоит из четырёх изолированных квадратов; однако если считать каждое из них частью, то это будет разбиением прямоугольника на две равные части.
Перед этим, думается мне, следует конструктивно или, хотя бы, просто положительно ответить на вопрос о существовании связного множества, которое можно представить в виде объединения двух несвязных конгруэнтных множеств, и нельзя — в виде объединения двух связных конгруэнтных множеств.
Легко. Возьмём ту же шахматную доску, отрежем от неё две нижние горизонтали, объединённые с крайней правой вертикалью. Я не возьмусь сейчас это строго доказывать, но ставлю стопицот денег, что это как раз нужный пример.
Действительно, несложно. Ну что ж, если удастся решить задачу и для несвязных составляющих множеств, будет неплохо. Единственное «но» — две статьи выше — очень строгие, и содержат алгоритмы. Получится ли выдумать алгоритм и для несвязного случая?
Эх, реализовать надо бы алгоритмы из (2), да работы сейчас слишком много.
Эх, реализовать надо бы алгоритмы из (2), да работы сейчас слишком много.
Насколько я понимаю, работает такая лемма.
Если многоугольник (не обязательно связный) можно разрезать на два куска, один из которых переходит в другой некоторым преобразованием R, то границу этого многоугольника можно разбить на конечное число пар отрезков A_i и B_i так, что для любого i существует такое k, что B_i=R^k(A_i). При этом если k нечетно, то ориентация отрезка границы относительно фигуры сохраняется (точки фигуры в окрестности отрезка переходят в точки фигуры, а точки из её дополнения — в точки дополнения). А если k четно, то наоборот — фигура и её дополнение в этом месте меняются местами.
Правда, обратное, скорее всего, неверно. Но для поворотов можно довольно быстро ограничить множество потенциальных центров (взяв фрагмент границы и нарисовав множество центров поворотов, переводящих его в другие фрагменты — это будет набор отрезков). Пересечение таких фигур для нескольких фрагментов и даст множество центров. А вот когда отрезки границы вдруг разобьются на пары — можно будет начинать чесать затылок.
Если многоугольник (не обязательно связный) можно разрезать на два куска, один из которых переходит в другой некоторым преобразованием R, то границу этого многоугольника можно разбить на конечное число пар отрезков A_i и B_i так, что для любого i существует такое k, что B_i=R^k(A_i). При этом если k нечетно, то ориентация отрезка границы относительно фигуры сохраняется (точки фигуры в окрестности отрезка переходят в точки фигуры, а точки из её дополнения — в точки дополнения). А если k четно, то наоборот — фигура и её дополнение в этом месте меняются местами.
Правда, обратное, скорее всего, неверно. Но для поворотов можно довольно быстро ограничить множество потенциальных центров (взяв фрагмент границы и нарисовав множество центров поворотов, переводящих его в другие фрагменты — это будет набор отрезков). Пересечение таких фигур для нескольких фрагментов и даст множество центров. А вот когда отрезки границы вдруг разобьются на пары — можно будет начинать чесать затылок.
Утверждение: если центр искомого поворота находится на серединном перпендикуляре двух вершин то углы при этих вершин должны быть равны и поворот должен переводить один угол в другой.
Таким образом, достаточно рассмотреть максимум по одной точке на серединных перпендикулярах между парами равных углов + их попарные пересечения.
Таким образом, достаточно рассмотреть максимум по одной точке на серединных перпендикулярах между парами равных углов + их попарные пересечения.
Утверждение ложно. Мне рисовать контрпример?
Дополнительное условие: на внешней границе должны находиться только эти две вершины. Случай когда есть другие вершины рассматривается через попарные пересечения (видимо нужно брать все серединные перпендикуляры, а не только между равными углами).
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Разрезание на две равные части, часть вторая