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

Question

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

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

#三角形クラス
class Triangle:
    def __init__(self,a,b,c):
        a=list(a)
        b=list(b)
        c=list(c)
        self.ver=[a,b,c]
        a=self.ver[0]
        b=self.ver[1]
        c=self.ver[2]
        self.x_max=max(a[0],b[0],c[0])
        self.x_min=min(a[0],b[0],c[0])
        self.y_max=max(a[1],b[1],c[1])
        self.y_min=min(a[1],b[1],c[1])
        self.z_max=max(a[2],b[2],c[2])
        self.z_min=min(a[2],b[2],c[2])
        self.max_list=[self.x_max,self.y_max,self.z_max]
        self.min_list=[self.x_min,self.y_min,self.z_min]


#BSP木ノード
class BSP_tree:
    def __init__(self,tri_list):
        self.tri_list=tri_list
        self.child_list1=None
        self.child_list2=None
        x_max,y_max,z_max=-100000,-100000,-100000
        x_min,y_min,z_min=100000,100000,100000
        for tri in tri_list:
            x_max=max(tri.x_max,x_max)
            y_max=max(tri.y_max,y_max)
            z_max=max(tri.z_max,z_max)
            x_min=min(tri.x_min,x_min)
            y_min=min(tri.y_min,y_min)
            z_min=min(tri.z_min,z_min)
        self.max_list=[x_max,y_max,z_max]
        self.min_list=[x_min,y_min,z_min]

#引数tri_nodeはBSP_treeのノードで、再帰的にBSP木を作る
#limit_min_numは各ノードの最大数、これ以上なら分ける
#-------この関数を動かすとエラーが起きます--------
def obj_subdiv(tri_node,limit_min_num):
    if len(tri_node.tri_list)>limit_min_num:
        one,two=list_subdiv(tri_node)
        one=BSP_tree(one)
        two=BSP_tree(two)
        tri_node.child_list1=one
        tri_node.child_list2=two
        obj_subdiv(tri_node.child_list1,limit_min_num)
        obj_subdiv(tri_node.child_list2,limit_min_num)

#実際に分けるコード
def list_subdiv(tri_node):
    x_range=tri_node.max_list[0]-tri_node.min_list[0]
    y_range=tri_node.max_list[1]-tri_node.min_list[1]
    z_range=tri_node.max_list[2]-tri_node.min_list[2]
    border=None
    index=None
    if x_range>=y_range and x_range>=z_range:
        index=0
    elif y_range>=x_range and y_range>=z_range:
        index=1
    else:
        index=2
    border=(tri_node.max_list[index]+tri_node.min_list[index])/2
    list_one=[]
    list_two=[]
    for tri in tri_node.tri_list:
        if tri.max_list[index]<border:
            list_one.append(tri)
        else:
            list_two.append(tri)
    return list_one,list_two

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

import numpy as np
from matplotlib import pylab as plt
import sys
import random
sys.setrecursionlimit(10000000)

tri_list=[]
#三角形クラスを1000個作ってリストに入れる
for i in range(1000):
    a=[random.randint(-10,10),random.randint(-10,10),random.randint(-10,10)]
    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)]
    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)]
    tri=Triangle(a,b,c)
    tri_list.append(tri)
    
#rootノードを作成
tri_node=BSP_tree(tri_list)
limit_min_num=10

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

obj_subdiv(tri_node,limit_min_num)

Answer 1

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

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

追記

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

def f(n):
    if n == 0:  # 再帰関数を終了する条件
        return 1

    return n * f(n - 1)

print(f(5))

Comments

[mikan_professor]

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

[tiitoi]

setrecursionlimit() は最大再帰数 (どのくらい入れ子にして再帰関数を呼べるのか) の制限を設定する関数で、再帰関数自体の再帰数を設定するものではありません。

> sysで上限を指定しているのにRecursionError: maximum recursion depth exceededとは出ない

とても大きい値を設定した場合、RecursionError になる前にクラッシュします。

再起関数をどういう条件で終了するかは質問者が再起関数内に設定するべきものです。現在、再帰関数を終える処理がないため、永遠に再帰関数が繰り返し呼ばれてクラッシュしています。

[mikan_professor]

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