ドロネー三角形分割のプログラムを作成中なのですが、参考プログラムが読めなく困っています。
ドロネー三角形分割のプログラムを作成中なのですが、参考プログラムが読めなく困っています。
ソースコードは以下の様になります。
--------------------------------------------------
bool incircle(point a, point b, point c, point p) {
a -= p; b -= p; c -= p;
return norm(a) * cross(b, c)
+ norm(b) * cross(c, a)
+ norm(c) * cross(a, b) >= 0; // < : inside, = cocircular, > outside
}
#define SET_TRIANGLE(i, j, r) \
E[i].insert(j); em[i][j] = r; \
E[j].insert(r); em[j][r] = i; \
E[r].insert(i); em[r][i] = j; \
S.push(pair<int,int>(i, j));
#define REMOVE_EDGE(i, j) \
E[i].erase(j); em[i][j] = -1; \
E[j].erase(i); em[j][i] = -1;
#define DECOMPOSE_ON(i,j,k,r) { \
int m = em[j][i]; REMOVE_EDGE(j,i); \
SET_TRIANGLE(i,m,r); SET_TRIANGLE(m,j,r); \
SET_TRIANGLE(j,k,r); SET_TRIANGLE(k,i,r); }
#define DECOMPOSE_IN(i,j,k,r) { \
SET_TRIANGLE(i,j,r); SET_TRIANGLE(j,k,r); \
SET_TRIANGLE(k,i,r); }
#define FLIP_EDGE(i,j) { \
int k = em[j][i]; REMOVE_EDGE(i,j); \
SET_TRIANGLE(i,k,r); SET_TRIANGLE(k,j,r); }
#define IS_LEGAL(i, j) \
(em[i][j] < 0 || em[j][i] < 0 || \
!incircle(P[i],P[j],P[em[i][j]],P[em[j][i]]))
double Delaunay(vector<point> P) {
const int n = P.size();
P.push_back( point(-inf,-inf) );
P.push_back( point(+inf,-inf) );
P.push_back( point( 0 ,+inf) );
int em[n+3][n+3]; memset(em, -1, sizeof(em));
set<int> E[n+3];
stack< pair<int,int> > S;
SET_TRIANGLE(n+0, n+1, n+2);
for (int r = 0; r < n; ++r) {
int i = n, j = n+1, k;
while (1) {
k = em[i][j];
if (ccw(P[i], P[em[i][j]], P[r]) == +1) j = k;
else if (ccw(P[j], P[em[i][j]], P[r]) == -1) i = k;
else break;
}
if (ccw(P[i], P[j], P[r]) != +1) { DECOMPOSE_ON(i,j,k,r); }
else if (ccw(P[j], P[k], P[r]) != +1) { DECOMPOSE_ON(j,k,i,r); }
else if (ccw(P[k], P[i], P[r]) != +1) { DECOMPOSE_ON(k,i,j,r); }
else { DECOMPOSE_IN(i,j,k,r); }
while (!S.empty()) {
int u = S.top().first, v = S.top().second; S.pop();
if (!IS_LEGAL(u, v)) FLIP_EDGE(u, v);
}
}
double minarg = 1e5;
for (int a = 0; a < n; ++a) {
for (set<int>::iterator itr = E[a].begin(); itr != E[a].end(); ++itr) {
int b = *itr, c = em[a][b];
if (b < n && c < n) {
point p = P[a] - P[b], q = P[c] - P[b];
minarg = min(minarg, acos(dot(p,q)/abs(p)/abs(q)));
}
}
}
return minarg;
}
--------------------------------------------------
http://www.prefield.com/algorithm/geometry/delaunay.htmlのサイト様のものなんですが、私自身c++プログラム初心者なので、わからず困っています。。概要でも結構ですのでどなたか回答してくださる方いらっしゃれば回答よろしくお願いします。
補足
確かに情報不足ですね、申し訳ありません。 開発環境ですが、 Windows XP VisualC++2005 Express Edition DirectX を使用しています。度々申し訳ありませんが、よろしくお願いします。