我试图编写一个执行以下计算的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}$它实现了一个显式公式来计算面积。再说一次,这似乎和我想做的无关。在
我如何解决这个问题? 提前谢谢!在
为提高效率,将点与边进行比较时,请使用以下规则:
如果您在蓝色区域,则该点在外部,
如果您在橙色区域,则该点在内部,
否则,您将需要递归测试,但是请确保选择点所在的绿色三角形,以便只在一个子边上递归。
这看起来可能只是一个小小的差别,但却可以节省大量开支。实际上,在第
n
-代时,薄片有3 x 4^n
面(即第十代的3145728
);如果你递归到一个子边,你将只做12
测试!在@cdlane的版本是最差的,因为它每次都会执行一个详尽的测试。@ante的版本介于两者之间,因为它有时会提前停止,但仍然可以执行指数级的测试。在
一种简单的实现方法是假设要检查的那一面总是
(0,0)-(1,0)
。然后测试测试点属于哪个三角形是一件简单的事情,因为顶点的坐标是固定的和已知的。这可以通过四个与直线的比较来完成。在当您需要递归到子边时,您将通过将其移动到原点、缩放3并旋转60°(如有必要)来变换该子边;将相同的变换应用于测试点。在
可以用递归创建Koch雪花的相同方式检查点位置。步骤包括:
这种方法更快,因为它不创建整个多边形并对其进行检查。在
以下是使用numpy实现的要点:
找到一个具有a routine for performing the "point in polygon" inclusion test的Python模块;使用turtle的}捕获代码生成的顶点,然后应用缠绕数测试:
begin_poly()
、end_poly()
和{^{pr2}$
相关问题 更多 >
编程相关推荐