确定一个点是否属于n阶Koch雪花指定的区域

Question

我试图编写一个执行以下计算的python脚本：

输入： （1） 列表L：一些二维点的列表 （2） 列表V：三角形的顶点 （3） 正整数n：从该三角形创建Koch雪花的顺序

输出： 列表O，L的一个子集，包含来自L的点，位于区域Kn上或内部，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()

但既然它没有说明雪花的区域，我就不能再往前走了。接下来，我认为雪花的区域可能包含一些见解，因此我编写了以下函数：

^{pr2}$

它实现了一个显式公式来计算面积。再说一次，这似乎和我想做的无关。在

我如何解决这个问题？ 提前谢谢！在

Answer 1

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

• 如果您在蓝色区域，则该点在外部，

• 如果您在橙色区域，则该点在内部，

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

这看起来可能只是一个小小的差别，但却可以节省大量开支。实际上，在第n-代时，薄片有3 x 4^n面（即第十代的3145728）；如果你递归到一个子边，你将只做12测试！在

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

---

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

当您需要递归到子边时，您将通过将其移动到原点、缩放3并旋转60°（如有必要）来变换该子边；将相同的变换应用于测试点。在