徒然なるままに

最小包含球に関して 教えている専門学校生は、ゲーム制作を主として勉強しているのだけれども、前回講義が終わってから質問があった。当たり判定を行う上で、キャラクターのポリゴンを包むエリアを球で表したいけれども、その最小の球の中心と半径を求めたいとな…。 ふむふむ、当然、そういうケースも起こりうるわなぁと。 「で、今はどんな方法を？」 「とりあえず、頂点の平均値から中心を求めているが、当然最小ではなくて、他の方法を探しています」 「平面であれば外接円を求めることになるよね？」 「それは分かりますが、空間で行う場合のアルゴリズムが分からないので…」 調べましたがな… 即答するのには、こちらも手持ちのネタがない。 「1週間待ってくれ。ヒントぐらいはあげられる筈だから…」（本当か？）と思いつつ、調査することに。 いろいろな方法が有るんだけれども、ゲームということは実行時間が短く、メモリをあまり食わない方法が最適。この条件で良さそうなものを探すことに。見つけたのが、 「 点の集合を包含する球 」という文献。 ここにも、様々な方法が紹介されているものの、最後のものが良さそう。 ということで、実際にコーディングして確かめることに。 条件は変なデータはないという前提でエラーチェックも最低限にして…。 #include <math.h> #include <stdio.h> #define INPUT_FILE "stars-s.txt" #define DATANUM 30 typedef struct { double x, y, z; /* coordinates */ } pos; int n=DATANUM; pos point[DATANUM]; pos center; double distance(pos p,pos pp) {     double rr;     return((pp.x-p.x)*(pp.x-p.x)+(pp.y-p.y)*(pp.y-p.y)+(pp.z-p.z)*(pp.z-p.z)); } double solve_by_movement(void) {     int k,i,t;...