Хм, верно, можно и так понять
Однако это скорее баг русского или вообще языка. В математике "различных" означает именно "не одинаковых", а не более разговорное "всяких"
Трихроматное строение человеческого глаза достаточно удобно для создания изображения (на видеокарте) — rgb+a хорошо стыкуется с трехмерными координатами мира xyz+w, позволяет использовать для обработки координат те же вычислительные блоки что и для обрабортки цвета, и получившиеся четыре координаты удобно работают с двоичной системой счисления.
Как бы это все выглядело будь человек тетрахроматом?
Но многоугольник от этого может перестать быть "хорошим" — в нем могут появиться самопересечения. А значит в конце можно остаться не с одним треугольником, а с рандомной кашей из намотаных вокруг точки вершин.
Ну вот представьте многоугольник в виде буквы М с соединением снизу. Удалив треугольник из двух нижних точек и одной верхней мы получим самопересечение.
Возможно в конце можно будет сделать какой то вывод. Но это надо бы доказать. И в любом случае получится больше чем O(N) из-за того что "если с треугольником не получилось — переходим к следующему". Насколько больше — тоже как-то нетривиально посчитать.
Вы должны доказать что это работает, а не "не могу придумать варианта".
Вон возьмите пример из правой верхней картинки статьи, только точка находится "между ног" а треугольник вы взяли из трех нижних точек. Точка в нем лежит, а в исходном многоугольнике — нет.
Если точки многоугольника и искомая точка целые числа то там надо просто математикой выкинуть все операции деления, это возможно, и считать в целых числах. Достаточно просто. Но алгоритм пересечения отрезка с лучом придется переписать. Превращаться в последовательности вертикальных и горизонтальных отрезков не надо.
В случае выпуклого многоугольника исходная задача становится супер простой — проверить что точка лежит с одной стороны от прямых созданных из всех отрезков (например слева от всех отрезков)
Однако в задаче очевидно подразумевается произвольный многоугольник, что и нарисовано на картинках В произвольном многоугольнике треугольник составленный из трех последовательной точки может ему не принадлежать полностью или частично.
Превратили O(N) задачу в O(N^3) потому что найти треугольник в многоугольнике это O(N^2) в худшем случае для простых алгоритмов. Есть сложные (сложнее чем определение точки в многоугольнике) которые побыстрее на больших многоугольниках но все равно получается больше чем O(N^2)
Можно. Проверка здесь будет только по одной из координат, а не результат какого-то вычисления (которое подвержено ошибкам)
Многоугольник обходится в одну сторону (по или против часовой стрелки). Вот для каждого отрезка одна из точек — начало, вторая — конец. Конец одного отрезка это начало другого
Второй вариант — считать точку с меньшим Х началом, с большим Х концом. Это будет лучше обрабатывать еще один особый случай (внутреннее касание вершины)
Я могу точно сказать что можно потому что такой алгоритм я писал и он работает в проде.
В данном случае для пересечения совсем не обязательно считать детерминанты и т.п. — пересечение с лучом параллельным оси можно посчитать проще, и, главное, с меньшим влиянием ошибок точности плавающей запятой.
можно еще проще. Считать попаданием в начальную точку отрезка, но не считать в конечную. Т.е. для одной из точек условие будет что то типа >= а для второй строго >
Да.
auto p = a; -b;
auto p = a -b;
auto p = a; (b=5);
auto p = a(b=5);
Я не сишник, уверен сишники сейчас еще десяток примеров приведут.
Парочку примеров, от нового майкрософта (2014+)?
Хм, верно, можно и так понять
Однако это скорее баг русского или вообще языка. В математике "различных" означает именно "не одинаковых", а не более разговорное "всяких"
Я уже видел йогурты в литрово выглядящих бутылках содержащих 690 мл. 690 мл уже в принципе округляется до половины литра.
Трихроматное строение человеческого глаза достаточно удобно для создания изображения (на видеокарте) — rgb+a хорошо стыкуется с трехмерными координатами мира xyz+w, позволяет использовать для обработки координат те же вычислительные блоки что и для обрабортки цвета, и получившиеся четыре координаты удобно работают с двоичной системой счисления.
Как бы это все выглядело будь человек тетрахроматом?
Но многоугольник от этого может перестать быть "хорошим" — в нем могут появиться самопересечения. А значит в конце можно остаться не с одним треугольником, а с рандомной кашей из намотаных вокруг точки вершин.
Ну вот представьте многоугольник в виде буквы М с соединением снизу. Удалив треугольник из двух нижних точек и одной верхней мы получим самопересечение.
Возможно в конце можно будет сделать какой то вывод. Но это надо бы доказать. И в любом случае получится больше чем O(N) из-за того что "если с треугольником не получилось — переходим к следующему". Насколько больше — тоже как-то нетривиально посчитать.
есть еще Manufactoria 2022 — мне ок зашла, слегка похоже на классику Spacechem и иже с ними
Вы должны доказать что это работает, а не "не могу придумать варианта".
Вон возьмите пример из правой верхней картинки статьи, только точка находится "между ног" а треугольник вы взяли из трех нижних точек. Точка в нем лежит, а в исходном многоугольнике — нет.
В статье выпускаемый луч вертикальный поэтому правильно считать по Х а не по У
Если точки многоугольника и искомая точка целые числа то там надо просто математикой выкинуть все операции деления, это возможно, и считать в целых числах. Достаточно просто. Но алгоритм пересечения отрезка с лучом придется переписать. Превращаться в последовательности вертикальных и горизонтальных отрезков не надо.
В случае выпуклого многоугольника исходная задача становится супер простой — проверить что точка лежит с одной стороны от прямых созданных из всех отрезков (например слева от всех отрезков)
Однако в задаче очевидно подразумевается произвольный многоугольник, что и нарисовано на картинках В произвольном многоугольнике треугольник составленный из трех последовательной точки может ему не принадлежать полностью или частично.
Массив это не множество — массив уже имеет порядок. Массив точек однозначно задает многоугольник.
Для данного конкретного алгоритма самопересечение многоугольника не играет роли.
Превратили O(N) задачу в O(N^3) потому что найти треугольник в многоугольнике это O(N^2) в худшем случае для простых алгоритмов. Есть сложные (сложнее чем определение точки в многоугольнике) которые побыстрее на больших многоугольниках но все равно получается больше чем O(N^2)
То что точка является результатом вычислений это неважно. Важно чтобы она была учтена один раз, и в этом случае полуоткрытые отрезки работают.
Полигон это массив точек а не отрезков. В отрезки уже превращаем его мы в алгоритме, и мы можем это сделать аккуратно.
Ну и "второму варианту" на порядок пофиг, а он все равно лучше первого
Поэтому и "второй вариант".
Можно. Проверка здесь будет только по одной из координат, а не результат какого-то вычисления (которое подвержено ошибкам)
Многоугольник обходится в одну сторону (по или против часовой стрелки). Вот для каждого отрезка одна из точек — начало, вторая — конец. Конец одного отрезка это начало другого
Второй вариант — считать точку с меньшим Х началом, с большим Х концом. Это будет лучше обрабатывать еще один особый случай (внутреннее касание вершины)
Я могу точно сказать что можно потому что такой алгоритм я писал и он работает в проде.
Последний вопрос я не понял
В данном случае для пересечения совсем не обязательно считать детерминанты и т.п. — пересечение с лучом параллельным оси можно посчитать проще, и, главное, с меньшим влиянием ошибок точности плавающей запятой.
можно еще проще. Считать попаданием в начальную точку отрезка, но не считать в конечную. Т.е. для одной из точек условие будет что то типа >= а для второй строго >
вторичного зеркала*
Без сегмента первичного зеркала переживут