образец случайной точки в треугольнике

Question

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

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

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

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

EDIT

Как было отмечено в комментарии к the mathoverflow question, Graphical Gems discusses this algorithm.

Answer 1

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

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

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