Случайная точка в треугольнике

Выборочная случайная точка в треугольнике

Предположим, что у вас есть произвольный треугольник с вершинами A , B и C . В этой статье (раздел 4.2) говорится, что вы произвольно генерируете случайную точку P равномерно из треугольника ABC следующей выпуклой комбинация вершин:

где r1 и r2 равномерно вычерчены из [0, 1] , а sqrt — функция квадратного корня.

Как вы подтверждаете, что выбранные точки, равномерно распределенные в треугольнике ABC ?

ИЗМЕНИТЬ

Видео:Алгоритмы. Попадание точки в треугольникСкачать

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

ОТВЕТЫ

Ответ 1

У вас есть карта P (r1, r2) от квадрата единицы к вашему треугольнику. Выбор r1 и r2 равномерно дает случайную точку в единичном квадрате. Изображение в треугольнике распределяется по определителю Якобиана отображения P, которое оказывается константой. Поэтому распределение изображения равномерно.

Собственно, для проверки этого вам нужно только проверить его на одну тройку неколлинеарных точек A, B, C. Аффинные линейные отображения имеют постоянный якобиан, поэтому вы можете применить один из них, чтобы переместить произвольную тройку в эту стандартную позицию, не влияя на распределение.

Наконец, слово о «почему»: Рассмотрим треугольник как заполненный отрезками, параллельными стороне BC. В формуле для P переменная r1 выбирает, на какой сегмент будет стоять точка, тогда как r2 определяет, где по сегменту она будет. Для однородности все точки на данном сегменте должны обрабатываться одинаково (следовательно, линейными по r2). Но для r1, так как некоторые сегменты короче других, нам нужно отдавать предпочтение длинным сегментам для достижения равномерного распределения. Для этого отвечает sqrt (r1) в формуле.

Видео:Игры хаоса. Фракталы [Numberphile на русском]Скачать

Игры хаоса. Фракталы [Numberphile на русском]

Равномерное распределение точек в треугольнике

Большинство двухмерных квазислучайных методов рассчитано на сэмплирование в единичном квадрате. Однако в компьютерной графике также очень важны треугольники. Поэтому я описал простой метод прямого построения для равномерного покрытия последовательностью точек треугольника произвольной формы.

Случайная точка в треугольнике

Рисунок 1. Новый прямой метод построения открытой (бесконечной) квазислучайной последовательности с низким расхождением в треугольнике произвольной формы и размера. На рисунке показаны распределения точек в пятнадцати случайных треугольниках для первых 150 точек.

Видео:Где находится точка в треугольнике заданном координатами вершин, внутри или вне треугольника.Скачать

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

Краткий обзор

Последовательности с низким расхождением (low discrepancy), равномерно сэмплирующие/заполняющие квадрат, активно изучались почти сотню лет. БОльшую часть этих квазислучайных последовательностей можно расширить до прямоугольников простым растягиванием, не сильно повредив при этом расхождению.

Однако в этом посте мы рассмотрим интересное и важное расширение последовательностей с низким расхождением на произвольный треугольник.

Насколько я мог понять, построению множеств равномерно распределённых в треугольнике точек и последовательностей уделялось очень мало внимания. Примечательные работы недавних лет Басу [2014], Пилландса [2005] и Брандолини [2013] представляют основные, если не единственные статьи по этой теме.

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

В посте описывается простой метод прямого построения, не требующий ни принятия/исключения, ни отбрасывания или рекурсии; и самое важное то, что его можно применять к треугольникам произвольного размера и формы.

Пост состоит из четырёх разделов:

  1. Квазислучайные последовательности в квадрате
  2. Наложение единичного квадрата на треугольник.
  3. Снижение искажений
  4. Дальнейшие обобщения

Видео:Точка пересечения медиан в треугольникеСкачать

Точка пересечения медиан в треугольнике

1. Квазислучайные последовательности точек

Вы можете подумать, что разместить 100 точек в квадрате таким образом, чтобы минимальное расстояние между соседними точками оставалось как можно бОльшим, будет легко. Но что если нужно разместить 13 точек? 47? А как насчёт 2019 точек?!

Оказывается, что последовательности точек с низким расхождением обеспечивают систематический способ решения этой задачи. Существует множество квазислучайных последовательностей с низким расхождением, от простой последовательности Холтона до более сложной последовательности Соболя. Каждая из этих последовательностей имеет свои достоинства и недостатки. Например, последовательности Холтона оказываются более полезными при размещении объектов в области, потому что у неё хорошо оптимизированы такие метрики локального расстояния, как ближайшие соседи. Последовательность Соболя склонна к образованию большей «скученности», однако глобальное распределение точек очень равномерно, поэтому она имеет превосходные свойства квадратуры.

Есть ещё одна последовательность, которую я люблю использовать, с отличными локальными, а также глобальными свойствами. Это последовательность Случайная точка в треугольнике, подробно описанная в моём предыдущем посте «Неожиданная эффективность квазислучайных последовательностей».

Если вкратце, то мы задаём бесконечную двумерную последовательность Случайная точка в треугольнике, такую, что

Случайная точка в треугольнике

Случайная точка в треугольнике

Случайная точка в треугольнике

Подробнее об этом особом значении Случайная точка в треугольнике, которое часто называют «пластической константой» можно прочитать в Википедии или Mathworld.

В итоге, на рисунке 2 показано сравнение различных последовательностей с низким расхождением (и простая равномерная случайная выборка для сравнения). Как видите, эта случайная выборка демонстрирует скапливание точек. При этом в ней есть области, вообще не содержащие точек («белый шум»), в то время как квазислучайная последовательность с низким расхождением — это метод построения (бесконечной) последовательности точек детерминированным образом так, чтобы на любом этапе размещённые точки равномерно распределялись по всему пространству.

Случайная точка в треугольнике

Рисунок 2. Иллюстрация первых 150 членов различных квазислучайных последовательностей с низким расхождением. Заметьте, что все они создают более равномерно распределённые в пространстве точки, чем простое равномерное случайное распределение (внизу слева).

Видео:Замечательные точки треуг-ка. 8 класс.Скачать

Замечательные точки треуг-ка. 8 класс.

2. Наложение единичного квадрата на треугольник

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

Случайная точка в треугольнике

Рисунок 3. Метод параллелограмма

Метод параллелограмма заключается в следующем.

Для треугольника Случайная точка в треугольникерассмотрим параллелограмм Случайная точка в треугольнике.

Для точки единичного квадрата Случайная точка в треугольникезададим такую точку Случайная точка в треугольнике, что Случайная точка в треугольнике.

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

То есть если Случайная точка в треугольнике, то Случайная точка в треугольнике, но если Случайная точка в треугольнике1$» data-tex=»inline»/>, то Случайная точка в треугольнике.

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

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

Аналогично, метод инверсного распределения накопленных вероятностей применяет к точкам нелинейное искажение. В последовательностях Холтона и Соболя это означает, что две точки очень часто подталкиваются очень близко друг к другу.

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

Случайная точка в треугольнике

Рисунок 4. Сравнение преобразования различных квазислучайных последовательностей в треугольнике. Вверху показана последовательность Холтона, посередине — последовательность Соболя, внизу — последовательность Случайная точка в треугольнике. Видно, что в последовательности Холтона возникает значительная скученность точек, а в последовательности Соболя — значительное образование полос. По сравнению с ними, в последовательности Случайная точка в треугольникеточки распределены очень равномерно, и почти отсутствует заметная скученность или полосы.

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

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

Случайная точка в треугольнике

Рисунок 5. Можно увидеть, что преобразованная последовательность Случайная точка в треугольникеобеспечивает очень простой, но эффективный способ равномерного распределения множества из Случайная точка в треугольникеточек в треугольнике. Он работает и с остроугольными, и с тупоугольными треугольниками. (Цвет обозначает порядок расположения).

Видео:Замечательные точки треугольника | Ботай со мной #030 | Борис Трушин ||Скачать

Замечательные точки треугольника | Ботай со мной #030 | Борис Трушин ||

3. Другие аспекты

Видео:№238. Докажите, что в равнобедренном треугольнике отрезок, соединяющий любую точку основания,Скачать

№238. Докажите, что в равнобедренном треугольнике отрезок, соединяющий любую точку основания,

Искажение

Метод параллелограмма требует выбора двух сторон треугольника в качестве базисных векторов.

Если вершины помечаются в случайном порядке, то паттерны точек обычно напоминают показанные на рисунке 6.

Случайная точка в треугольнике

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

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

Если принять такой порядок, то получаются паттерны точек, показанные выше на рисунках 1, 4 и 5.

Однако даже при определённом порядке вершин в некоторых случаях всё равно заметны эффекты искажений. Больше всего они заметны, когда в треугольниках один из углов очень мал. В случае тупоугольных треугольников, когда наименьший угол меньше 30 градусов, то заметно некоторое искажение, а в случае остроугольных треугольников, когда наименьший угол меньше 20 градусов, становится видным искажение. (Если сэмплируемые треугольники являются частью сетки Делоне, то такие проблемы с искажениями могут быть минимальными, потому что триангуляция Делоне специально предназначена для минимизации количества треугольников с малыми углами.)

Видео:Что скрывает фрактальный треугольник? // Vital MathСкачать

Что скрывает фрактальный треугольник? // Vital Math

Другие фигуры

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

Видео:№54. Точка В не лежит в плоскости треугольника ADC, точки М, N и Р — середины отрезков ВА, ВССкачать

№54. Точка В не лежит в плоскости треугольника ADC, точки М, N и Р — середины отрезков ВА, ВС

Геометрическая вероятность

Случайная точка в треугольнике

Цели и задачи: 1) Познакомить учащихся с одним из возможных способов задания

2) Повторение пройденного и закрепление навыков формализации

текстовых вероятностных задач с помощью геометрических фигур.

1) Знать определение геометрической вероятности выбора точки

внутри фигуры на плоскости и прямой;

2) Уметь решать простейшие задачи на геометрическую вероятность,

зная площади фигур или умея их вычислять.

I. Выбор точки из фигуры на плоскости.

Пример 1. Рассмотрим мысленный эксперимент: точку наудачу бросают на квадрат, сторона которого равна 1. Спрашивается, какова вероятность события, которое состоит в том, что расстояние от этой точки до ближайшей стороны квадрата не больше чем Случайная точка в треугольнике?

Случайная точка в треугольникеВ этой задаче речь идет о так называемой геометрической вероятности.

Рассмотрим более общие условия опыта.

Точку наудачу бросают в фигуру F на плоскости. Какова вероятность того, что точка попадает в некоторую фигуру G, которая содержится в фигуре F.

Ответ зависит от того, какой смысл мы вкладываем в выражение «бросить точку наудачу».

Обычно это выражение трактуют так:

1. Брошенная точка может попасть в любую часть фигуры F.

2. Вероятность того, что точка попадает в некоторую фигуру G внутри фигуры F, прямо пропорциональна площади фигуры G.

Подведем итог: пусть Случайная точка в треугольникеи Случайная точка в треугольнике— площади фигур F и G . Вероятность события А «точка Х принадлежит фигуре G, которая содержится в фигуре F», равна

Случайная точка в треугольнике.

Заметим, что площадь фигуры G не больше, чем площадь фигуры F, поэтому Случайная точка в треугольнике

Случайная точка в треугольникеВернемся к нашей задаче. Фигура F в этом примере квадрат со стороной 1. Поэтому Случайная точка в треугольнике=1.

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

Случайная точка в треугольнике

Тогда вероятность того, что точка попала в фигуру G, равна Случайная точка в треугольнике

Пример 2. Из треугольника АВС случайным образом выбирается точка Х. Найти вероятность того, что она принадлежит треугольнику, вершинами которого являются середины сторон треугольника.

Случайная точка в треугольникеРешение: Средние линии треугольника разбивают его на 4 равных треугольников. Значит, Случайная точка в треугольнике

Вероятность того, что точка Х принадлежит треугольнику KMN, равна:

Случайная точка в треугольнике

Вывод. Вероятность попадания точки в некоторую фигуру прямо пропорциональна площади этой фигуры.

Задача. Нетерпеливые дуэлянты.

Дуэли в городе Осторожности редко кончаются печальным исходом. Дело в том, что каждый дуэлянт прибывает на место встречи в случайный момент времени между 5 и 6 часами утра и, прождав соперника 5 минут, удаляется. В случае же прибытия последнего в эти 5 минут дуэль состоится. Какая часть дуэлей действительно заканчивается поединком?

Решение: Пусть х и у обозначают время прибытия 1-го т 2-го дуэлянтов соответственно, измеренное в долях часа начиная с 5 часов.

Случайная точка в треугольнике

Случайная точка в треугольникеДуэлянты встречаются, если Случайная точка в треугольнике, т. е. xСлучайная точка в треугольнике

📹 Видео

Урок по теме ЧЕТЫРЕ ЗАМЕЧАТЕЛЬНЫЕ ТОЧКИ ТРЕУГОЛЬНИКА ГЕОМЕТРИЯ 8 КЛАСССкачать

Урок по теме ЧЕТЫРЕ ЗАМЕЧАТЕЛЬНЫЕ ТОЧКИ ТРЕУГОЛЬНИКА ГЕОМЕТРИЯ 8 КЛАСС

Окружность вписанная в треугольник и описанная около треугольника.Скачать

Окружность вписанная в треугольник и описанная около треугольника.

Пересечение биссектрис треугольника в одной точке, Геометрия 7 классСкачать

Пересечение биссектрис треугольника в одной точке,  Геометрия 7 класс

четыре замечательные точки треугольника 8 КЛАСС АтанасянСкачать

четыре замечательные точки треугольника 8 КЛАСС Атанасян

ГЕОМЕТРИЯ 8 класс: 4 замечательные точкиСкачать

ГЕОМЕТРИЯ 8 класс: 4 замечательные точки

Теория вероятностей #18: системы двух случайных величин, двумерное распределениеСкачать

Теория вероятностей #18: системы двух случайных величин, двумерное распределение

Всё о равнобедренном треугольнике за 1 минуту.Мой тг:matematikandreiСкачать

Всё о равнобедренном треугольнике за 1 минуту.Мой тг:matematikandrei

Лекция 1. Точка на прямой. Метод прямоугольного треугольникаСкачать

Лекция 1. Точка на прямой. Метод прямоугольного треугольника

№191. Отрезок ВК — биссектриса треугольника ABC. Через точку К проведена прямая, пересекающаяСкачать

№191. Отрезок ВК — биссектриса треугольника ABC. Через точку К проведена прямая, пересекающая

Выживший летчик рассказал, что он увидел в Бермудском треугольникеСкачать

Выживший летчик рассказал, что он увидел в Бермудском треугольнике

0906 Замечательные линии и точки в треугольникеСкачать

0906 Замечательные линии и точки в треугольнике
Поделиться или сохранить к себе: