質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

1回答

628閲覧

BSP木を作成しようとしているのですが、Pythonでkernelが落ちます。

mikan_professor

総合スコア28

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

0クリップ

投稿2020/05/17 14:43

Pythonにて、3次元空間内での大量の三角形の図形をBSP木により分けたいと思っているのですが、ある関数でkernelが落ちてしまいます。google colabで実行しても無理だったため、パソコン本体の問題ではないと思います。

こちらが全体の関数のコードです。

Python

1 2#三角形クラス 3class Triangle: 4 def __init__(self,a,b,c): 5 a=list(a) 6 b=list(b) 7 c=list(c) 8 self.ver=[a,b,c] 9 a=self.ver[0] 10 b=self.ver[1] 11 c=self.ver[2] 12 self.x_max=max(a[0],b[0],c[0]) 13 self.x_min=min(a[0],b[0],c[0]) 14 self.y_max=max(a[1],b[1],c[1]) 15 self.y_min=min(a[1],b[1],c[1]) 16 self.z_max=max(a[2],b[2],c[2]) 17 self.z_min=min(a[2],b[2],c[2]) 18 self.max_list=[self.x_max,self.y_max,self.z_max] 19 self.min_list=[self.x_min,self.y_min,self.z_min] 20 21 22#BSP木ノード 23class BSP_tree: 24 def __init__(self,tri_list): 25 self.tri_list=tri_list 26 self.child_list1=None 27 self.child_list2=None 28 x_max,y_max,z_max=-100000,-100000,-100000 29 x_min,y_min,z_min=100000,100000,100000 30 for tri in tri_list: 31 x_max=max(tri.x_max,x_max) 32 y_max=max(tri.y_max,y_max) 33 z_max=max(tri.z_max,z_max) 34 x_min=min(tri.x_min,x_min) 35 y_min=min(tri.y_min,y_min) 36 z_min=min(tri.z_min,z_min) 37 self.max_list=[x_max,y_max,z_max] 38 self.min_list=[x_min,y_min,z_min] 39 40#引数tri_nodeはBSP_treeのノードで、再帰的にBSP木を作る 41#limit_min_numは各ノードの最大数、これ以上なら分ける 42#-------この関数を動かすとエラーが起きます-------- 43def obj_subdiv(tri_node,limit_min_num): 44 if len(tri_node.tri_list)>limit_min_num: 45 one,two=list_subdiv(tri_node) 46 one=BSP_tree(one) 47 two=BSP_tree(two) 48 tri_node.child_list1=one 49 tri_node.child_list2=two 50 obj_subdiv(tri_node.child_list1,limit_min_num) 51 obj_subdiv(tri_node.child_list2,limit_min_num) 52 53#実際に分けるコード 54def list_subdiv(tri_node): 55 x_range=tri_node.max_list[0]-tri_node.min_list[0] 56 y_range=tri_node.max_list[1]-tri_node.min_list[1] 57 z_range=tri_node.max_list[2]-tri_node.min_list[2] 58 border=None 59 index=None 60 if x_range>=y_range and x_range>=z_range: 61 index=0 62 elif y_range>=x_range and y_range>=z_range: 63 index=1 64 else: 65 index=2 66 border=(tri_node.max_list[index]+tri_node.min_list[index])/2 67 list_one=[] 68 list_two=[] 69 for tri in tri_node.tri_list: 70 if tri.max_list[index]<border: 71 list_one.append(tri) 72 else: 73 list_two.append(tri) 74 return list_one,list_two

以下がメインパートとなります。

Python

1import numpy as np 2from matplotlib import pylab as plt 3import sys 4import random 5sys.setrecursionlimit(10000000) 6 7tri_list=[] 8#三角形クラスを1000個作ってリストに入れる 9for i in range(1000): 10 a=[random.randint(-10,10),random.randint(-10,10),random.randint(-10,10)] 11 b=[random.randint(a[0]-3,a[0]+3),random.randint(a[1]-3,a[1]+3),random.randint(a[2]-3,a[2]+3)] 12 c=[random.randint(a[0]-3,a[0]+3),random.randint(a[1]-3,a[1]+3),random.randint(a[2]-3,a[2]+3)] 13 tri=Triangle(a,b,c) 14 tri_list.append(tri) 15 16#rootノードを作成 17tri_node=BSP_tree(tri_list) 18limit_min_num=10 19

この状況で以下の関数を実行するとエラーが起きます。

Python

1obj_subdiv(tri_node,limit_min_num)

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

limit_min_num を変化させないと、再帰関数は無限に呼び出されることにならないでしょうか。
再帰関数を呼び出していったとき、len(tri_node.tri_list) > limit_min_num でない場合がいつか現れないと、再帰関数が無限ループします。

※ 実装の正しさについては検証していません。カーネルが落ちるという問題についてです。

追記

例えば、階乗を計算する再帰関数を作るなら以下のようになります。
今の質問者さんのコードには、n == 0 の場合は再帰をやめるという処理がない状態です。

python

1def f(n): 2 if n == 0: # 再帰関数を終了する条件 3 return 1 4 5 return n * f(n - 1) 6 7print(f(5))

投稿2020/05/17 15:09

編集2020/05/17 15:41
tiitoi

総合スコア21956

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

mikan_professor

2020/05/17 15:32

回答ありがとうございます。 これについては考えたのですが、 ①sysで上限を指定しているのにRecursionError: maximum recursion depth exceededとは出ない ②範囲を半分にして狭めているため、いつかは条件が満たされるはず と思います... もう一度再確認してみます。
tiitoi

2020/05/17 15:38 編集

setrecursionlimit() は最大再帰数 (どのくらい入れ子にして再帰関数を呼べるのか) の制限を設定する関数で、再帰関数自体の再帰数を設定するものではありません。 > sysで上限を指定しているのにRecursionError: maximum recursion depth exceededとは出ない とても大きい値を設定した場合、RecursionError になる前にクラッシュします。 再起関数をどういう条件で終了するかは質問者が再起関数内に設定するべきものです。現在、再帰関数を終える処理がないため、永遠に再帰関数が繰り返し呼ばれてクラッシュしています。
mikan_professor

2020/05/17 15:41

なるほど、勘違いしておりました。ありがとうございます!!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問