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

Автор темы Alex 
ОбъявленияПоследний пост
ОбъявлениеСтуденческий конкурс в области программирования AR Start16.04.2012 10:07
ОбъявлениеМосковского математического общество объявляет конкурс ММО для молодых ученых 2012 года23.04.2012 01:34
ОбъявлениеНабор в Школу анализа данных Яндекса, отд. Биоинформатики18.05.2012 10:47
25.06.2009 14:25
Равномерное распределение в треугольнике
Есть такая задача: построить (написать генератор случайных точек) равномерное распределение в выпуклом многоугольнике на плоскости.
Ну просто её, видимо, не решить, так что решили разбить многоугольник на треугольники и уже строить равномерное распределение в треугольнике.

В треугольнике распределение строится так:
  1. Берутся два случайных числа $p, q$ равномерно распределённые на отрезке $[0, 1]$.
  2. Вычисляются коэффициенты:
    $\lambda_1 = \min(p,q)$,
    $\lambda_2 = \max(p,q) - \lambda_1$,
    $\lambda_3 = 1 - \max(p,q)$,
    т. е. $\lambda_1 + \lambda_2 + \lambda_3 = 1$.
  3. Получается точка внутри треугольника ABC: $\vec{x} = \lambda_1 \vec{A} + \lambda_2 \vec{B} + \lambda_3 \vec{C}$.

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



Редактировалось 1 раз(а). Последний 25.06.2009 15:01.
25.06.2009 15:07
О численном эксперименте.
Я бы, для начала, попробовал подтвердить или опровергнуть гипотезу о равномерном распределении численными экспериментами с треугольниками разного вида.
25.06.2009 16:31
Re: О численном эксперименте.
Цитата
brukvalub
Я бы, для начала, попробовал подтвердить или опровергнуть гипотезу о равномерном распределении численными экспериментами с треугольниками разного вида.

Ну, численные эксперименты вроде показывают, что распределение равномерное. Кстати, для многоугольников построенное подобным образом распределение уже не равномерное.
26.06.2009 01:15
Порассуждаем
Равнораспределение означает, что вероятность попадания точки в "бесконечно малую область" пропорциональна площади этой области.
1) Рассмотрим преобразование квадрата IxI в треугольник с помощью преобразования:
$\lambda_1=\min(p,q)$
$\lambda_2=\max(p,q)-\lambda_1$
Выбросим из единичного квадрата IxI его диагональ (она имеет меру 0). На каждом из двух оставшихся треугольников мы имеем взаимно однозначное линейное отображение с модулем якобиана равным 1 в любой точке. Эти треугольники при этом склеиваются, но это не важно - главное это то, что одинаковые площади преобразуются в одинаковые площади (что характерно для линейных 1-1 преобразований). Образом квадрата получается треугольник ограниченный координатными прямыми и прямой $\lambda_1+\lambda_2=1$
2) Полученный треугольник является проекцией треугольника получаемого пересечением плоскости
$\lambda_1+\lambda_2+\lambda_3=1$ с трехгранным углом, образуемым положительными квадрантами координатных плоскостей (это равносторонний треугольник, получаемый Вами в п.2).
Т.к. проектирование переводит равные площади в равные, то распределение $(\lambda_1,\lambda_2,\lambda_3)$ является равномерным в указанном треугольнике.
3) В пункте 3 Вы с помощью линейного преобразования переводите этот треугольник в данный. Как уже отмечалось, якобиан линейного преобразования не зависит от точки и сохраняет равновеликость.

Замечание: отображение одной плоскости на другую, порожденное линейным пребразованием трехмерного пространства является линейным преобразованием плоскости при любом выборе координат в плоскостях . Термин "линейное преобразование" я использовал в школьном смысле, т.е. речь идет об афинном преобразовании.
12.07.2009 19:55
Спасибо
Спасибо за подробный ответ (я что-то забыл ответить раньше :).
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти