ドロネー三角形分割のプログラムを作成中なのですが、参考プログラムが読めなく困っています。
ソースコードは以下の様になります。
--------------------------------------------------
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/delau …のサイト様のものなんですが、私自身c++プログラム初心者なので、わからず困っています。。概要でも結構ですのでどなたか回答してくださる方いらっしゃれば回答よろしくお願いします。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- C言語・C++・C# c言語の問題の説明、各所ごとに 5 2023/07/26 11:03
- FX・外国為替取引 mql4のコンパイルエラー箇所の修正お願いします。 1 2023/03/15 16:14
- C言語・C++・C# C言語のエラーについて 2 2022/07/11 13:56
- C言語・C++・C# プログラムの時、フローチャートはどうなりますか?図でお願いします。 int main(void) { 1 2022/10/01 22:45
- C言語・C++・C# c言語 プログラムのエラー 1 2023/02/11 20:31
- C言語・C++・C# プログラミング c言語 4 2023/03/07 01:05
- C言語・C++・C# C言語 プログラミング 4 2022/05/22 11:53
- C言語・C++・C# C言語 3 2022/11/09 13:27
- C言語・C++・C# C 言語の Gauss Jordan 法について 2 2022/12/28 11:16
関連するカテゴリからQ&Aを探す
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
C言語
-
#define _CRT_SECURE_NO_WARNIN...
-
C言語 エラーの原因がわからな...
-
比較回数と交換回数表示について
-
複数桁10進数の*桁目だけを抽出...
-
nCmの関数
-
構造体の勉強中です 合計点の高...
-
C言語 配列と関数の練習問題
-
[C言語] 関数を利用する計算
-
実数の整数部,小数部の取得
-
C言語での引数の省略方法
-
数字列を3桁ごとにカンマで区切...
-
アスタリスクでダイヤ型を作る
-
覆面算のプログラムが分かりません
-
C言語の基礎 . 2乗値の差につ...
-
c言語
-
プログラミング
-
【C++】関数ポインタの使い方
-
毎回違う乱数を生成するにはど...
-
if と配列の組み合わせ
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
C言語での引数の省略方法
-
#define _CRT_SECURE_NO_WARNIN...
-
「指定されたキャストは有効で...
-
C言語 配列と関数の練習問題
-
複数桁10進数の*桁目だけを抽出...
-
(int *)の意味
-
if と配列の組み合わせ
-
ラップ関数とはどんなものですか?
-
卒業研究でよく分からないとこ...
-
【C++】関数ポインタの使い方
-
c言語
-
足して100になるような乱数のア...
-
C言語初心者です、、、お助けく...
-
数字列を3桁ごとにカンマで区切...
-
C言語 エラーの原因がわからな...
-
実数の整数部,小数部の取得
-
課題でつまってます・・・
-
商と剰余を同時に求める(C言語)
-
C言語の配列をC++のvectorに高...
-
std::set<int> で、ある値が何...
おすすめ情報