python - 确定一个点是否属于 n 阶科赫雪花指定的区域

Question

我正在尝试编写一个执行以下计算的 python 脚本:

输入:(1) List L:一些二维点的列表(2) list 五:三角形的顶点(3) 正整数n:从该三角形创建科赫雪花的阶数

输出:列表 O，L 的子集，包含 L 中位于区域 Kn 之上或之内的点，该区域由 n 阶雪花定义。

---

我的尝试:首先，我想我应该先实现一个标准算法来绘制给定顺序(和边长)的雪花。这是我写的代码:

import turtle
from test import test

world= turtle.Screen()
t= turtle.Turtle()

def koch(t, order, size):
    if order == 0:
        t.forward(size)
    else:
        for angle in [60, -120, 60, 0]:
           koch(t, order-1, size/3)
           t.left(angle)

def koch_fractal(t, order, size, main_polygon_sides= 3):
    for i in range(main_polygon_sides):
        koch(t, order, size)
        t.right(360/main_polygon_sides)

koch_fractal(t, 2, 100)
world.mainloop()

但由于它没有说明雪花区域的任何信息，我无法继续前进。接下来，我想雪花的面积可能会有一些见解，所以我写了这个函数:

from math import sqrt
koch_cache={}
def koch_fractal_area(n, side):
    original_area = (sqrt(3)/4) * side**2 #Area of the original triangle 
    koch_cache[0] = original_area
    for i in range(n+1):
        if i not in koch_cache:
         koch_cache[i] = koch_cache[i-1] + (3*4**(i-1))*(sqrt(3)/4) * (side/(3**i))**2
    return koch_cache[n]

它实现了一个显式公式来计算面积。同样，它似乎与我尝试做的事情无关。

我该如何解决这个问题？提前致谢!

Answer 1

为了提高效率，当您将点与边进行比较时，请使用以下规则:

• 如果你在蓝色区域，则点在外面，

• 如果你在橙色区域，则点在里面，

• 否则您将需要递归测试，但请确保选择该点所在的绿色三角形，以便您仅在一个子边上递归。

这可能看起来差异很小，但可以节省大量资金。实际上，在第 n 代，薄片有 3 x 4^n 个面(即第 10 代 3145728)；如果你递归到一个子端，你将只做 12 测试!

@cdlane 的版本是最差的，因为它每次都会执行详尽的测试。 @ante 的版本介于两者之间，因为它有时会提前停止，但仍然可以执行指数级的测试。

---

一个简单的实现方法是假设要检查的边总是(0,0)-(1,0)。然后测试测试点属于哪个三角形是一件简单的事情，因为顶点的坐标是固定的并且是已知的。这可以通过与一条直线进行四次比较来完成。

当你需要递归到一个子面时，你将通过将它移动到原点，缩放 3 并旋转 60°(如果需要)来变换该子面；对测试点应用相同的变换。