任給平面上一點, 如何判斷它是否在指定雪花分形圖案的內部？

01-05

如圖中k0 三角形有許多演算法判斷坐標系中一點在其中，k1可以看成是兩個三角形
k2到kn就不知道怎麼計算了，窮舉所有的三角形嗎，這計算量很大吧？

從內外同時逼近，應該可以對邊界附近點更快給出結果。

另外，斜坐標系中考慮三進位也許有效(當然本質上不會減少計算量)

（根據@野生阿獃的思路）

易知：

若p在K0內，則必在K中；

若p不在K0的外接圓C0內，則必不在K中。

則可從K0開始迭代，

檢查p是否在三角形K0中，如果是，則返回true，否則繼續；

檢查p是否在外接圓C0中，如果不是，則返回false，否則繼續；

檢查p是否在K1新增的三個三角形內，如果是，則返回true，否則繼續；

檢查p是否在K1新增的三個三角形的外接圓內，如果不是，則返回false，否則則以p所在的外接圓對應的三角形為新的K1繼續。

如此往複直至一定迭代次數。

判斷點在正三角形內應該有非常容易的辦法，並不一定要用射線法。還有迭代只要取外接圓對應的分支即可。

利用這個遞歸結構，首先將曲線劃分成六邊形內和形外六個三角形，六邊形內自然是在裡面了，如果也不在六個三角形里，那就是不在。

如果在三角形里，進一步將三角形劃分成9個小三角形，歸類成三類：在紅色區域里，則不在曲線範圍內；在綠色區域里，則在曲線範圍內；在藍色區域，為待定，但是一定屬於特定的一個藍色三角，這個藍色三角和我們這個三角形是自相似的，通過一次迭代化歸回這個問題。每次迭代，三角形的邊長縮小到1/3，因此在精度有限的條件下，這是一個 $O(log n)$ 的演算法。沒太大必要按內切圓、外切圓之類的判斷，如果在那些條件可以淘汰掉的位置上，一般來說最多也就多迭代一次而已。

謝邀，問題的本質是實現一個函數：

bool KochSnowFlake(float x, float y, unsigned int k)

函數的參數x,y為輸入的二維坐標位置，k為koch雪花的分形迭代次數。返回值為true表示該坐標位置在雪花內部。

詳細代碼見:Shadertoy .生成的雪花效果如下：

如果你打不開這個網頁，恭喜你，我現在和你一樣，這是因為牆的功勞。

好在我之前整理過它的代碼,並將其改寫成自己定義的一套腳本代碼。該腳本代碼可以生成8*8個koch雪花。

#https://www.shadertoy.com/view/Mlf3RX


#圖像大小

pixels = W:1024 H:1024
#兩變數的取值範圍,(x,y)為平面的一個坐標點

x = from 0 to 8 W

y = from -4.5 to 3.5 H
#px,py,pt為臨時變數

px = abs(fract(x)-0.5)

py = abs(fract(y)-0.5)
#循環8次

[loop start: 8

pt = - (px*1.735 - py)*0.865

py = - (abs(px + py*1.735) - 0.58)*0.865

px = pt

loop end]

#(r,g,b)為輸出顏色 r = px g = px b = px

這程序寫得，看上去很簡單，不過是幾行代碼的事。我感覺自己能讀懂，然後我就想動手將其擴展成三維的，即基於正四面體進行分形生成的雪花體。然後就沒有然後了……

既然科赫雪花是遞歸定義的，那麼判定某一點是否在其內部也可以遞歸判定。

科赫雪花可以看作是3條科赫曲線（3階旋轉對稱）。

以下討論作為科赫雪花一邊的科赫曲線。首先，我們先來給出科赫曲線的定義。

和現有多數答案相同，我們依賴如下遞歸結構：

根據科赫曲線自相似的定義，Δ1 (126)、Δ2 (236)、Δ4 (347)、Δ5 (457)和大三角形是相似的。

我們可以得到遞歸判定的邏輯：

若點在Δ3中，則在曲線內；
若點在Δ6中，則在曲線外；
否則遞歸檢查Δ1、Δ2、Δ4、Δ5。

&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>

以下給出判斷某點是否在n階科赫曲線內的Python的全部代碼。

僅依賴於numpy，來讓我們 import numpy as np。

首先，給定任意端點x1,x5，生成上述點的坐標：

theta = np.radians(60) c, s = np.cos(theta), np.sin(theta) rot60 = np.matrix([[c, -s], [s, c]])

def get_point_list(x1, x5): """generate the list of points given two end points""" x2 = (1 / 3) * x5 + (2 / 3) * x1 x4 = (2 / 3) * x5 + (1 / 3) * x1 x3 = rot60.dot(x4 - x2).A1 + x2 x6 = rot60.dot(x2 - x1).A1 + x1 x7 = rot60.dot(x5 - x4).A1 + x4 return x1, x2, x3, x4, x5, x6, x7

使用了定比分點及向量旋轉。

其次，判斷某一點p是否在某給定頂點p0,p1,p2的三角形內部：

def inside_triangle(p, p0, p1, p2): """determine if p is inside of a triangle given three points p0, p1, p2""" s, t = np.matrix(np.vstack((p1 - p0, p2 - p0))).T.I.dot(p - p0).A1 return 0 &<= s &<= 1 and 0 &<= t &<= 1 and s + t &<= 1

使用了重心坐標( Barycentric Coordinates )，可以理解為把p0p分解為p0p1與p0p2的線性組合。是否在三角形內部是仿射性質。

最後，給出上述遞歸判定是否在曲線內部的函數：

def inside_Koch_curve(x, n, x1=np.array([0, 0]), x5=np.array([1, 0])): """determine if x is inside of n-th iterations of Koch curve""" if n==0: return False x1, x2, x3, x4, x5, x6, x7 = get_point_list(x1, x5) if inside_triangle(x, x2, x3, x4): # 3 return True elif inside_triangle(x, x1, x2, x6): # 1 return inside_Koch_curve(x, n-1, x1, x2) elif inside_triangle(x, x2, x3, x6): # 2 return inside_Koch_curve(x, n-1, x2, x3) elif inside_triangle(x, x3, x4, x7): # 4 return inside_Koch_curve(x, n-1, x3, x4) elif inside_triangle(x, x4, x5, x7): # 5 return inside_Koch_curve(x, n-1, x4, x5) else: return False

其中n限制了迭代深度（數值穩定性問題，迭代過深後可能數值上矩陣不可逆）。

默認初始坐標為(0,0), (1,0)。

以上是全部代碼。使用方法為調用 inside_Koch_curve(x, n, x1, x5)。

測試代碼略去。

&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>

但是，我想說的並不只是這些。

令集合A為科赫雪花內部（及邊界）的所有點，域為六邊形（或大三角形，或整個實平面）內的所有點。上述問題為一個判定問題( Decision problem )：給定域中的一個元素，這個元素是否在集合A中？

一個很自然的問題是：

理論上，我們可以在有限時間內得到結果嗎？
是否存在一個點在科赫雪花內，但任何程序在有限時間內都無法給出判斷？

由於精度限制，上述代碼（以及任何其他代碼）只是科赫雪花的n階近似。我們想問的問題是，如果在能處理任意精度的理想計算機上，去掉迭代深度限制的返回條件，對於任意一點，我們的程序都有返回嗎？

&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>&>

在遞歸論或可計算性理論中有兩個概念：
遞歸集( Recursive set )：

可數集合A是遞歸集，如果我們能夠構造一個演算法，使其判斷一給定元素是否屬於這個集合，並在有限時間內終止。
遞歸可枚舉集( Recursively enumerable set )：

可數集合A是遞歸可枚舉集，如果存在生成A中的元素的演算法。

等價地，如果存在一個圖靈機，在給定A中元素作為輸入時總能停機，在給定不屬於A的元素時永不停機。（可以令圖靈機生成A中的元素，若與給定輸入相等則停機否則繼續）

此外我們可以定義判定問題的可判定性。

如果判定問題在有限時間內給出結果，我們稱這個判定問題是可判定的。判定問題是可判定的的充分必要條件是集合是遞歸集。

如果判定問題能在答案為肯定時終止執行並輸出，在答案為否定時永不終止，則稱該判定問題為半可判定的。判定問題是半可判定的的充分必要條件是集合是遞歸可枚舉集。

定理：集合A是遞歸集的充分必要條件是集合A與其補集均為遞歸可枚舉集。

（令程序判斷某元素屬於A或不屬於A，其中一個會在有限時間終止）

我們的問題即：

科赫雪花的內點集是遞歸集嗎?
判斷一點是否在科赫雪花內是可判定的嗎？

對於任意有限階的科赫雪花答案是肯定的。實際上，在程序中即體現了上述定理，我們同時生成了屬於內部的三角形集合及不屬於內部的三角形集合。

我們也可以用更緊密的遞歸結構，如下圖所示：

本質上與正三角形的遞歸結構是相同的。

對於生成內部點集與外部點集，遞歸過程均為：確定Δ3為內部點（外部點），遞歸Δ1、Δ2、Δ4、Δ5。（初始參數不同）

因此，一個有趣的事實是，兩種不同尺度的科赫雪花可以密鋪( Tessellation )：

來源：https://commons.wikimedia.org/wiki/File:Koch_similarity_tiling.svg

這也得益於上述內部與外部自相似的性質。

歡迎討論。

——關於遞歸與分形的有趣的內容——

測度，維度，可數性，可微性：

Cantor set

Sierpinski carpet

Koch snowflake

Space-filling curve

可計算性，可枚舉性，可判定性：

Recursively enumerable set

Halting problem

MU puzzle

原題是:

如何判斷坐標系中一個點在雪花分形圖中？

我稍微對題目做了一下調整, 只是希望調整一下語言格式, 希望沒有改變原意, 如果有, 請題主及時反饋. 調整後的題目:

任給平面上一點, 如何判斷它是否在指定雪花分形圖案的內部？

首先必須承認, 這個問題非常的有意思, 因為它問的是 "如何判斷某一點是否在某個分形圖案內部", 所以這就不單純是個畫圖問題了, 因為在這個場景下, "先把圖畫出來, 再去取給定點所在的像素點的像素值" 的辦法已經失效了.

為什麼說 "先畫圖, 再取指定點" 的辦法失效了呢? 因為這是個分形圖案, 每一個微小的菊部, 它所包含的細節都是無限豐富的, 所以在 "先畫圖" 的時候就不可避免地會遇到難以回答的問題: 我的分形圖案應該迭代多少次? 圖畫多大, 畫多少個像素才能滿足題主的精度要求?

然後即使我們暫時先接受這種明顯的不精確, 指定了一堆魔法數字, 然後開始畫圖了, 程序也會遇到顯著的性能問題: 按照現代的PC機的計算能力, 畫一個 10000 像素長寬 (即 10000 * 10000 個像素) 的圖片, 就需要1s左右 (數量級) 的時間了, 而這樣的圖片所提供的精度也僅僅是差強人意而已. 並且當你想要提高判斷的精度的時候, 付出的時間和空間的代價是迅速攀升的 (因為每一次你都得繪製整個圖形, 而查詢只用到了其中的一個點).

---------------------------------- 開始解題的分割線 -----------------------------------

首先我們來看看題主給出的圖形, 這個雪花一看就知道是一個經典的分形圖案, 它叫科赫雪花, (別問我為什麼知道, 咱書讀的少, 但畢竟有谷歌圖片搜索...

Wiki上面 (Koch snowflake - Wikipedia) 有一個動圖很直觀地表明了, 這個圖形是可以無限放大的, 並且一個菊部放大之後還能和自身相似, 這也是所有分形圖案的特點.

------------------------------ 瞎扯完畢, 真的開始解題的分割線 -------------------------

1. 明確目標

首先, 為了解決題主的問題, 我們確定一下我們的小目標:

我們需要得到這樣一個函數, 對任意的一點, 返回一個布爾值 (真或假), 表示該點是否在指定的雪花圖案內部. 用Haskell語言的類型系統來表達這樣一個函數, 就是:

insideSnowflake :: Point -&> Bool

2. 對圖形做抽象

為了得到一個判斷點是否在雪花圖形內部的函數, 我們必須描述出雪花圖形.

在這裡, 我們把圖形抽象為: 對給定的平面上一點, 返回圖形在該點上的顏色值(像素), 這裡我們用Bool值表示像素, 即:

data Graph = Graph (Point -&> Pixel) type Pixel = Bool

3. 圖形上的運算

現在我們已經確定如何表示圖形, 我們可以在此基礎上定義一些圖形上的運算:

-- 給定圖形和點, 判斷點是否在該圖形內部 inside :: Graph -&> Point -&> Bool inside (Graph f) p = f p


-- 給定兩個圖形, 返回兩個圖形的交集 (這裡把圖形看作點集)

intersect :: Graph -&> Graph -&> Graph

intersect ga gb = Graph (p -&> (inside ga) p  (inside gb) p)
-- 給定兩個圖形, 返回兩個圖形的並集 (這裡把圖形看作點集)

union :: Graph -&> Graph -&> Graph

union ga gb = Graph (p -&> (inside ga) p || (inside gb) p)
-- 給定向量和圖形, 將圖形按照指定向量平移, 得到新圖形

move :: Vec -&> Graph -&> Graph

move vec g = Graph (p -&> (inside g) (p `vecSub` vec))
-- 給定一個標量作為縮放倍率, 給定一個圖形, 對該圖形進行縮放, 返回縮放後的圖形

scale :: Scalar -&> Graph -&> Graph

scale k g = Graph ((x, y) -&> (inside g) (x / k, y / k))

-- 給定一條直線和一個圖形, 返回該圖形關於直線鏡面對稱的圖形 mirror :: Line -&> Graph -&> Graph mirror l g = Graph (p -&> (inside g) (mirrorPoint l p)) where mirrorPoint (lp, lv) p = p" where ln = vecVeer lv d = (p `vecSub` lp) `vecDot` ln p" = p `vecAdd` (vecScale (-2 * d) ln)

4. 定義科赫雪花和科赫曲線

首先我們觀察科赫雪花, 它的最初形態是一個正三角形, 我們可以認為這個正三角形的三邊是分別演化的, 這樣可以將問題簡化到由其中一條邊所衍生出的曲線, 我們稱這個雪花圖案的 1/ 3所構成的曲線為科赫曲線 (當然wiki上的定義中並未區分科赫雪花和科赫曲線, 這裡是我們根據需要對兩者做了一個區分)

下圖對AB之間的這一支科赫曲線做了一個剖析:

通過觀察, 我們可以得出以下結論:

1). AB上方的三角形區域可以被分成6個子區域, 分別編號1~6

2). 整條曲線關於m2對稱

3). 4號子區域和5號子區域關於m3對稱

4). 5號子區域中的部分曲線和整條曲線相似, 相似比為1:3

所以我們根據上述結論得到如下代碼:

kochCurve = Graph f where l = 1.0 h = (sqrt 3 / 2) f (x, y) = if y &> (h / 3) then False else if y &<= 0 then True else if abs x + (1 / sqrt 3) * y &<= 1 / 6 then True else inside (leftHalf `intersect` rightHalf) (x, y) where leftHalf = mirror ((0, 0), (0, 1)) rightHalf rightHalf = leftCurve `union` rightCurve where leftCurve = mirror ((1 / 6, 0), vecUnit (1, sqrt 3)) rightCurve rightCurve = move (1 / 3, 0) (scale (1 / 3) kochCurve)

又通過觀察這一支曲線和整個雪花圖案之間的關係, 我們知道:

1). AC之間的曲線和BC之間的曲線關於m2對稱

2). BC之間的曲線和AB之間的曲線關於m1對稱

所以我們又得到如下代碼:

kochSnowflake = topCurve `intersect` leftCurve `intersect` rightCurve where topCurve = kochCurve leftCurve = mirror ((0, 0), (0, 1)) rightCurve rightCurve = mirror ((1 / 2, 0), vecUnit (sqrt 3, 1)) topCurve

5. 解題結束

得到雪花圖形的定義 (kochSnowflake) 之後, 我們的小目標也就完成了:

insideSnowflake :: Point -&> Bool

insideSnowflake = inside kochSnowflake

通過掃描點的方式, 我們可以根據我們的 kochSnowflake 的定義畫出圖形證實一下我們的成果:

6. 性能分析

我們可以把我們定義的這個遞歸函數理解成是層層篩子, 對於落入AB上方三角區域的一點, 如果它落到子區域6 (這個概率是 4/9) 我們就可以立即斷定該點在科赫曲線外部, 若它落到子區域3 (這個概率是 1/9) 我們可以立即斷定它在科赫曲線內部, 而對於落入子區域1, 2, 4, 5的點 (這個概率是 4/9), 它們則進入篩孔, 被下一層篩子繼續篩選 (這對應著代碼中進入遞歸分支).

所以我們發現, 對於AB上方三角形區域中的點, 經過k次遞歸, 程序停機的概率為 1 - (4/9) ^ k. 這意味著, 在經過128次遞歸後, 程序中用來表示點的 (Double, Double) 所有輸入中 (共2^128個), 存在的能使該程序仍未停機的輸入的個數的期望值已經遠小於1了.

7. 其它

完整代碼可以在這裡看到: https://gist.github.com/luochen1990/c6c2750c997d089bdff831d4b72efd8b

另外, 這個解法的精度受限於Double (雙精度浮點數) 的精度, 理論上, 如果換成精度更高的數值類型, 這段代碼可以免費得到更高精度的結果.

最後, 請跟我一起念: Haskell大法好.

附相關回答: 謝爾賓斯基三角形能用編程寫出來么？該怎麼寫？ - 羅宸的回答 - 知乎

以此點為原點向任意方向作射線，計算它與圖形的邊的交點數量，奇數在其中，偶數在其外。這是一種很普遍的對無自重疊的多邊形判內外的方法。

實際上三角分型由於遞歸定義，可以靠逼近的方法層疊生成出n階內最靠近指定點的頂點，那就連相交都可以不用做了。

如果這個點不在每一階的小三角形的外接圓內，就一定不會出現在分形圖內。所以只要每一層找到包含它的外接圓即可。

畫了個示意圖:

在1,2,3,4里就繼續分割，一直分割下去就能判斷了吧，這樣可以不用窮舉？

一點也不難啊？真不知道你們怎麼想的

學的知識全都還給老師了…

記得學過電磁學裡面，高斯定律，任意閉合曲面靜電場的通量和所包含電荷量成正比。

題主可推廣到任意閉合曲線(面)，以及環狀區域。

應用在二維空間中，點(源)向周圍放射線，強度與距離成反比，沿閉合曲線積分求通量，數值為0則不在閉合曲線內。

可能我想簡單了。

測試點和質心連線，與圖形有偶數個交點（0,2,4……）則在外圖形內，否則為圖形外。