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

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

P = (1 - sqrt(r1)) * A + (sqrt(r1) * (1 - r2)) * B + (sqrt(r1) * r2) * C

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

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

ИЗМЕНИТЬ

Как указано в комментарии к вопросу о mathoverflow, Graphical Gems обсуждает этот алгоритм.

Ответ 1

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

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

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