標籤：

如何在三角形（比如正三角形）里隨機取點？

11-25

要求均勻。

用線性代數的思路，三角形的一個頂點作為坐標原點，兩條臨邊對應兩個向量，分別叫它們為e1和e2，比如下面這個樣子：

因為是三角形所以 e1, e2 一定線性無關的，用它們作為基底構成一個二維線性空間，三角形在這個空間里剛好是單位正方形的下三角部分，在單位正方形內很容易產生平均分布的點，x, y 坐標分別為0..1 之間的隨機數，不過會有一半的點落在三角形外面，外面這部分是一個一模一樣的三角形，沿矩形中心轉180°剛好重合，這裡面的點也可以對應過去，方法是 (1,1) - (x, y)，見下圖：

不用判斷點是否在三角形內，norm((x,y)) 和norm( (1,1) - (x,y)) 哪個小就取哪個，一定是在三角形內的，然後得到如何下結果：

構造一個矩陣 M = (e1,e2)，M*(x,y) 把點轉換回原來的空間就可以了：

你取三角形的其中兩個邊，然後取倆隨機數，作為基於這兩個邊的坐標，它會在一個平行四邊型上。如果在平行四邊型的另外那半拉，就翻轉回來。
========================================
關於」線密度「的問題，按某人的看法，我推論一下：
設矩形內有N個點，假設它們是按某人的演算法抽取的，已經是「均勻分布」好了的。那麼，它們必然在一條邊上的線密度是N/a，概率密度是1/a；另一條邊上的線密度是N/b，概率密度是1/b。完B了，線密度不均勻！！！腫末辦？！！
========================================
實驗一下，懶得寫C++，直接Perl好了。
生成兩組十萬個隨機數，一組來自於[0, 1000)的隨機數除以1000，另一組來自於[0, 1000)的隨機數反覆排除直至小於1。然後分別排序、求相鄰值的間距。

#!/usr/bin/perl

use common::sense;

# 1e6 random numbers in [0,1) by scale
say "generate random numbers by scaling";
my @values_scale;
for (1..100000)
{
push @values_scale, rand_by_scale();
}

# 1e6 random numbers in [0,1) by clamp
say "generage random numbers by clamping";
my @values_clamp;
for (1..100000)
{
push @values_clamp, rand_by_clamp();
}

say scalar(@values_scale), " scaled values, mean neighbor distance ", mean_neighbor_distance(@values_scale);
say scalar(@values_clamp), " clamped values, mean neighbor distance ", mean_neighbor_distance(@values_clamp);

sub rand_by_scale
{
my $result = rand(1000);
return $result / 1000;
}

sub rand_by_clamp
{
while (1)
{
my $result = rand(1000);
return $result if $result &< 1; } } sub mean_neighbor_distance { my @sorted = sort {$a &<=&> $b} @_;

my $sum = 0;
for my $i (0..$#sorted-2)
{
my $distance = $sorted[$i+1] - $sorted[$i];
$sum += $distance;
}

return $sum / @sorted;
}

目視結果好像沒有啥區別。

generate random numbers by scaling
generage random numbers by clamping
100000 scaled values, mean neighbor distance 9.99956026148261e-06
100000 clamped values, mean neighbor distance 9.99981190545895e-06
generate random numbers by scaling
generage random numbers by clamping
100000 scaled values, mean neighbor distance 9.99972875288289e-06
100000 clamped values, mean neighbor distance 9.99975474645254e-06
generate random numbers by scaling
generage random numbers by clamping
100000 scaled values, mean neighbor distance 9.99976552477687e-06
100000 clamped values, mean neighbor distance 9.99966629546378e-06

懶得跑更多了。你們誰有興趣可以跑一萬遍。那個use common::sense可以用use feature qw/say/代替。
============================
我們再來理論上推導一下：
假如我用坐標縮放的方法，獲得了尺寸為a x b的矩形內的N個點。這N個點在短邊上的線密度就是N/a，在長邊上的密度就是N/b。
然後，把矩形補成方的，補的那塊面積就是(b-a) x b。在上面用同樣的方法成比例地搞K個點，讓K與N和這倆的面積成比例，即K : N = (b-a) : a，這樣就有K = N * (b-a) / a。然後，摞到一起，總的點數就是M = K+N = N*b/a。往長邊上投射，線密度是M / b = N / a。

假如使用投射後截取的方法：我們首先在b x b尺寸的正方形上搞M個點，然後再截一塊a x b的矩形出來，上面的點數N，就有M : N = b : a，完了。

這就好比：阿基米德定律說物體受的浮力等於排開水的重力，那麼1kg水有沒有可能浮起2kg物體？
============================
重新模擬了一下2D的實際情景，兩種方法的X坐標分別為縮放得到和剔除得到，都是得到2x5矩形內的100K個點；Y坐標使用相同的方法得到。然後，計算寬度為1的橫、縱向條帶內部的點的平均縱、橫向距離，統計這些距離的均值與標準差。因為懶，依然使用Perl腳本：

#!/usr/bin/perl

use strict;
use feature qw/say/;
use List::Util qw/sum/;

my $width = 2;
my $height = 5;
my $n_point = 100000;

sub calc_mean_var
{
my $mean = sum(@_) / @_;
my $var;
foreach (@_)
{
my $delta = $_ - $mean;
$var += $delta * $delta;
}
$var /= @_ - 1;
return $mean, sqrt($var);
}

sub stat_row_band
{
my ($row_y, $radius, $list) = @_;

my @points_in_band =
sort { $a-&>[0] &<=&> $b-&>[0] }
grep { $row_y - $radius &<= $_-&>[1] and $_-&>[1] &< $row_y + $radius } @$list; my @dists; for my $i (0..$#points_in_band-2) { push @dists, $points_in_band[$i+1][0] - $points_in_band[$i][0]; } my $n = @points_in_band; my ($mean, $var) = calc_mean_var(@dists); say " row band $row_y +- $radius: $n points, X dist $mean +- $var"; } sub stat_col_band { my ($col_x, $radius, $list) = @_; my @points_in_band = sort { $a-&>[1] &<=&> $b-&>[1] }
grep {$col_x - $radius &<= $_-&>[0] and $_-&>[0] &< $col_x + $radius} @$list; my @dists; for my $i (0..$#points_in_band-2) { push @dists, $points_in_band[$i+1][1] - $points_in_band[$i][1]; } my $n = @points_in_band; my ($mean, $var) = calc_mean_var(@dists); say " column band $col_x +- $radius: $n points, Y dist $mean +- $var"; } say "generate points by scaling X"; my @points_by_scale; while (1) { my $x = rand(1000) * $width / 1000; my $y = rand($height); push @points_by_scale, [$x, $y]; last if @points_by_scale == $n_point; } stat_row_band($_, 0.5, @points_by_scale) foreach 0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 4.5; stat_col_band($_, 0.5, @points_by_scale) foreach 0.5, 1.0, 1.5; say "generate points by clamping X"; my @points_by_clamp; while (1) { my $x = rand(1000); my $y = rand($height); push @points_by_clamp, [$x, $y] if $x &< $width; last if @points_by_clamp == $n_point; } stat_row_band($_, 0.5, @points_by_clamp) foreach 0.5, 1.0, 1.5, 2.0, 2.5, 3.0, 3.5, 4.0, 4.5; stat_col_band($_, 0.5, @points_by_clamp) foreach 0.5, 1.0, 1.5;

結果如下：

$ ./rand_2d_band.pl
generate points by scaling X
row band 0.5 +- 0.5: 19931 points, X dist 0.00010034522604204 +- 9.90234180792267e-05
row band 1 +- 0.5: 19867 points, X dist 0.000100644424121937 +- 9.86298894173467e-05
row band 1.5 +- 0.5: 20029 points, X dist 9.9842892244707e-05 +- 9.99879028183919e-05
row band 2 +- 0.5: 20083 points, X dist 9.95742867067129e-05 +- 9.92611843001927e-05
row band 2.5 +- 0.5: 20183 points, X dist 9.90808805984591e-05 +- 9.87553373597311e-05
row band 3 +- 0.5: 19834 points, X dist 0.000100834233953072 +- 0.000100899918606908
row band 3.5 +- 0.5: 19818 points, X dist 0.000100915794565392 +- 0.000100199903201948
row band 4 +- 0.5: 20006 points, X dist 9.99563692154631e-05 +- 9.98754321737075e-05
row band 4.5 +- 0.5: 20039 points, X dist 9.98014671140116e-05 +- 9.95131979663643e-05
column band 0.5 +- 0.5: 50094 points, Y dist 9.98106217203317e-05 +- 0.000100214056788598
column band 1 +- 0.5: 50119 points, Y dist 9.97633377467165e-05 +- 9.98593730642938e-05
column band 1.5 +- 0.5: 49906 points, Y dist 0.000100191237953084 +- 0.000100009329749359
generate points by clamping X
row band 0.5 +- 0.5: 19996 points, X dist 0.00010002666301678 +- 9.95013096873671e-05
row band 1 +- 0.5: 19700 points, X dist 0.000101529754307925 +- 0.000100282972977617
row band 1.5 +- 0.5: 19923 points, X dist 0.000100391531850098 +- 9.99276115197597e-05
row band 2 +- 0.5: 20113 points, X dist 9.94430762262343e-05 +- 9.93646982787434e-05
row band 2.5 +- 0.5: 19965 points, X dist 0.000100181429779361 +- 0.000100960988748272
row band 3 +- 0.5: 19934 points, X dist 0.000100338778482168 +- 0.000100947944741255
row band 3.5 +- 0.5: 19974 points, X dist 0.000100118697213791 +- 9.95583694965059e-05
row band 4 +- 0.5: 20106 points, X dist 9.94565915780385e-05 +- 9.75210374137402e-05
row band 4.5 +- 0.5: 20142 points, X dist 9.92788141551582e-05 +- 9.92902344154209e-05
column band 0.5 +- 0.5: 49945 points, Y dist 0.000100109777149598 +- 0.00010127742888257
column band 1 +- 0.5: 50217 points, Y dist 9.95667412102462e-05 +- 9.95035606303423e-05
column band 1.5 +- 0.5: 50055 points, Y dist 9.98892651377844e-05 +- 9.92531376381724e-05

不但兩種方法沒有區別，每種方法的X向和Y向也是沒有區別的。也就是說，即便是兩向不等的對於隨機點雲的線性縮放，其結果依然是均勻的。這可能與隨機點的本性有關係，不能簡單地用規律分布的點去套用。

下面是直觀上來看。用電子表格生成了500個隨機點，畫2D散點圖：

我們把它蹂躪一下，看起來會變成這樣：

我們不難發現，進行不等壓縮之後，直觀上看起來仍然是均勻的，與前面的計算相符。這體現了隨機數可能像無窮大那樣，具有一些與通常直觀想反的性質。

uniform random point in triangle
這裡有詳細的討論，相關論文可見http://www.cs.princeton.edu/~funk/tog02.pdf
這個實現是在PBRT的代碼裡面看到的。PBRT書上也有推導過程。

使用基於正方形的隨機採樣，拒絕落在三角形外面的採樣點也是可以，效率可能是個問題。把三角形外的點翻轉回來可能會把距離很遠的點，變得很近，甚至造成點的重疊。

既然是正三角形，就可以把大的正三角形分解成4個小的正三角形(把每個邊的中點連起來)。然後再把每個小的正三角形分成四個更小的正三角形。如此循環分下去，直到分的夠細。每個小的正三角形的中心即為樣本。要隨機的話，把所有樣本亂序就好了。

我本來是來圍觀的，也怪我自己，沒事多啥嘴啊！

有兩位的答案說，你先定義一下什麼是「均勻」：

這不是在抖機靈，就是沒好好學過概率論。「均勻分布」這個詞，不好意思啊，在數學裡面是有嚴格定義的。比如在Jun S. Liu的書《Monte Carlo Strategies in Scientific Computing》裡面，第一章，第一頁，出現了這個：

... where D is often a region in a high-dimension space...If we can draw independent and identically distributed random samples x(1),...x(m) uniformly from D,....

人家似乎也沒定義什麼叫均勻。

然而我們隨手一搜，維基百科裡面，Uniform distribution (continuous)，就給出了答案：

This distribution can be generalized to more complicated sets than intervals. If S is a Borel set of positive, finite measure, the uniform probability distribution on S can be specified by defining the pdf to be zero outside S and constantly equal to 1/K on S, where K is the Lebesgue measure of S.

然後，是那個匿名用戶的「在圓上隨機選擇一條弦」，就是 @孟晨說的「貝特朗悖論」吧？這壓根不是個問題，這個悖論是說我們必須定義清楚「樣本空間」，而在這裡，樣本空間有歧義么？

我就很搞不清楚，這個問題，如果給那些做過monte carlo的人，甚至都不必是專門的研究概率統計的人，都沒有任何歧義，為啥有一些數學系的學生，查也不查一查，就出來到處跟人argue呢？

回到這個問題。其實很簡單，rejection method就可以解決。但是如果簡單粗暴的畫矩形再rejection，其實效率挺低的，因為產生兩次隨機數才有一個被accept，其實這個問題可以這樣做：

A、B兩點如果被抽到，可以直接根據三角形的一條邊對稱過來，這樣就沒有rejection了。

以其一邊作正方形，然後正方形內均勻取點。若其在三角形內則取用，否則就不用。

取長方形裡的隨機樣本，

若 值1不在三角形範圍內 或 值2不在三角形範圍內，

值1 和 值2 旋轉180°

隨機得夠隨機了吧。重點是要旋轉！！

我實現過隨機取任意三角形內一點的演算法:

三角形三個頂點A,B,C

首先:
求得兩個向量
ab = B - A
ac = C - A。

然後:
使用rand()獲得兩個0～1之間的隨機實數x, y
如果x+y&>1， 那麼令x"=1-x, y"=1-y
如果x+y&<=1, 那麼令x"=x, y"=y

最後：
隨機點 = A + x" * ab + y『 * ac

給個圖像:

看到有人質疑這個演算法,我也不會用嚴謹的數學方法來證明.就發兩幅圖像佐證一下吧:

兩幅圖中,第一幅是正方形內隨機取點12000000次生成的圖像.第二幅是三角形內隨機取點4000000次生成的圖像.看上去雪花屏的感覺是一樣的.

------------------------
參考 @李曉生答案中的鏈接：uniform random point in triangle
我使用這個公式P=A*(1 - sqrt(r1)) + B*sqrt(r1)*(1 - r2) + C*r2*sqrt(r1),也生成了同樣的雪花屏圖像.

------------------------
關於均勻與隨機.
舉個例子:假如你娶了3個媳婦,要做到"雨露均沾",有兩種辦法:
第一種,三個輪流著來.每次嚴格按ABCABCABC...的順序,這叫均勻.
第二種,每次ABC中都有1/3的概率被選中,這叫隨機.
所以均勻是規則的,隨機是不規則的.對於這個問題,只能做到隨機,無法做到絕對的均勻.

還有個相關的問題:隨機三維單位向量的生成演算法如何做到均勻分布？ - 葉飛影的回答

給 @葉飛影 的答案提供一種證明
要求均勻分布，對於一個三角形，可以理解為
p_{x,y}(x,y) = egin{cases} frac{1}{S} ext{$(x,y) in Delta ABC$} \ 0 ext{$(x,y) otin Delta ABC$} end{cases}
其中S是三角形面積。
根據第一個答案給出的解法，先產生兩個屬於[0,1]的均勻分布的隨機數，可以記為
u sim U[0,1] \ v sim U[0,1]
由於兩者是獨立的，因此有
P_{u,v}(u,v) = P_{u}(u)P_{v}(v)
即P_{u,v}(u,v) = egin{cases} 1 u in [0,1], v in [0,1] \ 0 other condition end{cases}
將三角形的左下角的A點設為原點，建立坐標系，根據答主給出的變換關係

隨機點 = A + x" * ab + y『 * ac

即為(x, y) = u vec{AB} + vvec{AC}
對應關係為
x = u|ABcos(A)| + v|AC|
y = u|ABsin(A)|
利用二維連續型隨機變數的變數替換，根據上面的等式關係，有
u = frac{y}{|ABsin(A)|}
v = frac{x}{|AC|} - frac{y}{|ACtan(A)|}
因此雅可比矩陣為
J = frac{partial(u,v)}{partial(x,y)} = [egin{matrix} 0 frac{1}{|ABsin(A)|} \ frac{1}{|AC|} -frac{y}{|ACtan(A)|} end{matrix}]
因此有
p_{x,y}(x,y) = p_{u,v}(u,v)|J| = frac{1}{|AC ABsin(A)|}
這裡計算的其實是整個平行四邊形對應的均勻分布，而平行四邊形的面積為
S = |AB AC sin(A)|
說明這種方法生成的平行四邊形是均勻分布，因此生成的三角形也是均勻的。

這些答案裡面我最喜歡@慧航的。簡單又直觀。可惜最後那個映射的方法不好簡單推廣到所有其他任意圖形。

這真是個很有趣的問題，我也想到一個方法，可以求任意圖形中的隨機分部點。方法的原理也比較簡單明了，比較容易理解。

首先講一下idea。
假設我們有一個任意圖形，我想隨機地找到其上一個點。得到其x，y坐標。

那麼第一步，我先把這個圖形的年紀歸一化。

接下來，需要生成一個0到1之間的隨機數a。然後用a來得到一個隨機的x坐標。

x坐標怎麼定呢？因為圖像並不是均勻（均勻的意思是，一般粗細的），那麼可以預見，我們所得到的x坐標也不是均勻分部的。

那麼這裡有一個轉換要做。這個轉換的原則是，如下圖所示：

x0點的選取，恰好讓左側的圖形面積等於隨機數a.（圖中寫得隨機數1，懶得改了，抱歉）

這個時候就得到了x0的值。

y0的值怎麼得到呢？如下圖。我們需要另外一個隨機數。

設這個圖像在x0處的高度是dy，那麼，y0點將在這個高度內均勻隨機分布。

於是我們只需要再取一個隨機數，來計算得到這個y0。（注意上圖中y0的含義是我們取得的點離圖形下沿的距離）

以上就是整體思路，以下將用這個方法得到一個正三角形的隨機分布點。

Yike

提出一個設想求大家辯駁：
1.先構造一個與該三角形邊長相等的正方形。
2.在正方形內置隨機數，通過隨機置x y 兩個變數即可。
3.如果這個點落在該三角形內，取為為一個隨機點。如果不在，繼續置，直到在該三角形內
4.重複2.3步即可

這個問題居然可以轟轟烈烈的討論那麼久。首先過三角形的一個角做內高，然後這就組成了一個直角坐標系，你做一個包含矩形出來，當場均勻取點。這樣你有一半的點會落在外面，沒關係，折進來就好了。

多容易啊。

把三角形放到坐標系內，定點和原點重合，底邊在x軸上，以底為邊做一個矩形，頂點在矩形邊上。然後有了xy的範圍，用matlab的unifrnd在範圍內取隨機數，然後把三角形外的點去掉，應該就能滿足均勻了

BASE1 = [1, 0] #第一個基
BASE2 = [1/2.0, 3**0.5/2.0] #第二個基
T_LEN = 10 #正三角形長度

#random.random() ~U(0,1)
x = random.random()
y = random.random()
if x + y &> 1:
x = 1 - x
y = 1 - y

x = x * T_LEN
y = y * T_LEN

point = [ x * BASE1[0] + y * BASE2[0] , x * BASE1[1] + y * BASE2[1] ]

"""
相當先映射到一個平行四邊形。然後把另一塊對稱對去。
所以可見是均勻分布的，這個可以推廣到任意三角形。
"""
密集恐懼症，別盯太久 ＝ ＝

————————————————————————————————————————
x~U(0,1)
y~U(0,1)
point&<-&>(x,y)
一 一對應，且x,y獨立
所以每一個點的概率密度是：1/s ＝ const
s為三角形面積。

三角形三條邊，以其中一個銳角頂點和一條邊為中心和X軸構建一個直角坐標系，

A點坐標為(x1，y1)，B點坐標為(x2，0)
可以求出
OA:
Yoa=(y1/x1)X

AB: (a b 自己算)
Yab=aX+ b

按照下面的篩選，
x隨機取值為(0，x2)
y隨機取值為(0，y1)

boolean s(x，y){
if(x小於x1){
Yoa(x)小於y1就反回true，否則就是false
}else{
Yab(x)小於y1就反回true，否則就是false
}
}

大概就是這個意思

給出某個高維空間有限點集均勻的定義：高維空間某區域內，假設以某演算法生成n個點x_1~x_n，我們可以量化這個點集的均勻性：以x_k為中心作面積最大且不覆蓋周圍點的橢圓，橢圓長軸長a_k，短軸長b_k，面積s_k，如果這個點集是均勻的，那麼對任意epsilon，存在N，對任意n&>N，有|(a_k/b_k)-1|&幾個高票答案其實不滿足各向同性分布。

====

做為數學背景出身的，開始我很驚訝居然有很大一部分本科生甚至研究生（當然我猜大多數都是工科背景）對高維空間均勻點集的概念不清楚，不過後來想了想也正常，在沒有學過高維概率統計和測度論之前，對這個概念是會存在認知上的局限的，容易陷入在一維空間中思考高維問題的誤區，所以也不能算錯，只是數學修養不夠導致的思維局限性而已，就如@Milo Yip所說，大家對「均勻」的定義不同。當然另外一些能想通為何高維空間的均勻需要各個方向線密度相等的同學，空間想像能力是相當不錯的，有做數學家的潛質。

====

@Xi Yang貼的程序是錯誤的，假設a:b為10:1，在b方向產生N個坐標值，應該丟棄落在區域外的大約N*0.9個樣本，他的程序並沒有丟棄這些點，而是不斷死循環嘗試算出一個落在區域內的點，這沒有意義。我寫了C++程序，隨機生成0~0.1*RAND_MAX之間的樣本，比較了clamp模式和scale模式，計算了樣本點的平均距離，基本上就是10比1：


clamp average: 21375.6

scale average: 2147.47

另外他的證明也是錯的，用了二維量M和N除以一維量a和b去算線密度，光是單位就錯了。正確的方法是把M和N分解為一維量，假定b&>a（以他的假設為準）。
縮放法：N=J*J，線密度分別是J/a和J/b
截取法：M=K*K=J*J/a*b，也就是K=J*sqrt(b/a)，線密度分別是K/b*a/a=K/b和K/b，顯然截取法能獲得一致均勻，縮放法不行。
形象一點比喻，比如一個9x4的空間里，有36個人，站成6排6列還是9排4列更均勻（當然每個人可能有隨機微小擾動）？

#include &

#include &

#include &

#include &

#include &

#include &


std::vector& vclamp;

std::vector& vscale;


double average(const std::vector& v)

{

double sum = 0;

for(size_t i = 1; i &< v.size(); ++i)

sum += std::abs(v[i] - v[i - 1]);

return sum / (v.size() - 1);

}


int main()

{

for(int i = 0; i &< 100000; ++i)

{

double v = double(rand());

if(v &< 0.1 * RAND_MAX)

vclamp.push_back(v);

}

for(int i = 0; i &< 100000; ++i)

vscale.push_back(0.1 * rand());

std::sort(vclamp.begin(), vclamp.end(), std::less&());

std::sort(vscale.begin(), vscale.end(), std::less&());

std::cout &<&< "clamp average: " &<&< average(vclamp) &<&< " ";

std::cout &<&< "scale average: " &<&< average(vscale) &<&< " ";

return 0;

}


====


補充，再普及下什麼是高維空間的均勻。假設一個長方形邊長a和b不相等，但是用同一個隨機函數生成長方形內的坐標（ x=a*rand(0,1), y=b*rand(0,1) ），那麼在兩個方向的一維概率密度分別是1/a和1/b，那麼這個長方形內只有單個方向的概率分布是均勻的，但並不是各向均勻，只有a=b時才是真正的均勻，有些人沒有分清楚一維均勻和高維均勻的區別。


所以，如果在長方形外面外接一個邊長為a的正方形（假設a&>b），那麼先用隨機函數在正方形區域內獲得各項同性的均勻分布點（ x=a*rand(0,1), y=a*rand(0,1) ），各向概率密度為1/a，那麼如果我們丟掉在長方形外部的樣本，那麼在長邊方向，總概率還是1，但是短邊方向我們丟掉了大約(a-b)/a的樣本，總概率變成了1 - (a-b)/a = b/a，而長邊的概率密度為1/a，短邊的概率密度為(b/a) / b = 1/a，這樣才是各向同性均勻，各個方向的線密度相等。

＝＝＝＝

簡單看了下，三個高票答案都是錯的，如果兩個隨機採樣的方向不正交或者度量不同，結果並不會均勻，試試極端情況就知道了，目前只有 @陳思睿 的答案最靠譜，在外接正方形里做二維均勻隨機採樣，丟掉落在三角形外的樣本即可。另外 @Di Wang 給出了證明，證明那些答案錯在哪裡。

有人表示兩個採樣方向不用正交，那我再上個圖說明正交的重要性，兩個圖裡紅點都是一一對應的，估計很多人不知道什麼是各向異性分布（非均勻）：

用同樣的係數和基來表示點的位置，直角三角形里分布均勻的點，到了非直角三角形里，沿著長邊方向的分布密度顯然小於和它正交的方向。

請定義什麼叫均勻。

比如這是原三角形 (黃色):

把三角形複製一遍 (藍色), 然後旋轉180度後拼在一起:

然後開始在下面這個黑色矩形範圍內撒點, 如果撒到了粉色區域就平移到右邊藍色區域:

上一步得到的點如果不在黃色區域, 那一定在藍色區域. 繞下面的黑點中心對稱一下:

完了.補充: 或者直接找兩邊中點向底邊畫垂線, 然後把兩個角翻上去?

以下應該是技術上最簡單的辦法

以三個頂點做一個矩形，要求可以包括整個三角形。用x，y坐標在矩形中隨機取點，如果取到三角形外則重新取。這樣可以保證每個點被取到的概率是相同的。

用拒絕採樣。做包圍三角形的矩形，在矩形內做均勻採樣然後接受落在三角形內的點作為採樣點。

推薦閱讀：

※手機的九宮格圖案解鎖總共能繪出多少種圖案？
※什麼是動態規劃？動態規劃的意義是什麼？
※PRML為何是機器學習的經典書籍中的經典？
※1000桶水，其中一桶有毒，豬喝毒水後會在15分鐘內死去，想用一個小時找到這桶毒水，至少需要幾頭豬？
※想學好計算機演算法，是否需要重新學數學呢?

TAG:演算法 | 數學 | 概率論 |