関数points2triangles マニュアル

(The documentation of function points2triangles)
Last Update: 2023/7/11


◆機能・用途(Purpose)

2次元平面上の点群を用いて三角形要素を構築する。
Create triangular elements from points on a 2-D plane.

◆形式(Format)

#include <geometry.h>
inline int points2triangles
(const int Npoints,const double ∗x,const double ∗y,
 struct triangle ∗∗triangles)


◆引数(Arguments)

Npoints 点の個数。
The number of points.
x 点の\(x\)座標を並べた配列。
An array composed of the \(x\)-coordinates of the points.
y 点の\(y\)座標を並べた配列。
An array composed of the \(y\)-coordinates of the points.
triangles 求めた三角形のリストの代入先。 宣言しただけのstruct triangle ∗型変数に&を付けて与える。 関数内で配列の動的メモリの確保が行われ、 \(i\)番目の三角形要素の情報がtriangles[i]に代入される。 なお、構造体のメンバip1, ip2, ip3, p1, p2, p3のみが設定される。 三角形の3つの頂点はip1<ip2<ip3となるように並べられる。
Memory into which the list of triangles is to be inserted. Give an empty struct triangle ∗-type variable with &. Within the function, an array is allocated, and the array components triangles[i] for each \(i\) are set as representing the \(i\)th triangle. Only the members ip1, ip2, ip3, p1, p2, and p3 of the structure are set. The three vertexes for each triangle are sorted as ip1 < ip2 < ip3.


◆戻り値(Return value)

三角形要素の個数。
The number of triangular elements.

◆使用例(Example)

int Npoints=5;
double x[]={1.2,3.4,-5.6,-7.8,9.0};
double y[]={9.8,-7.6,5.4,-3.2,1.0};
int ∗∗triangles;
int Ntriangles=points2triangles(Npoints,x,y,&triangles);


◆アルゴリズム(Algorithm)

ドロネー三角形分割を使用する。 オリジナルのドロネーアルゴリズムと厳密に一致するものかは未確認であるが、 こちらのサイトを参考に、著者の理解に基づいて構築した。 以下、実際に関数内で用いているアルゴリズムを述べる。 文章だけでは分かりにくいので上記「使用例」のデータ(図1)を用いて説明する。
The Delaunay's algorithm is used. Although it is uncertain whether the algorithm used is exactly identical to the original Delaunay's algorithm, the author studied the algorithm using this website, and constructed the algorithm based on the author's understanding of it. Below, the algorithm that is exactly used in the function is described. The algorithm is not easy to understand by text alone; to compensate for this difficulty, an illustration of the data used in the “example” above (Fig. 1) is used.

図1. 以下の説明で用いる点群。
Fig. 1. The data of points used in the description below.


(1) 全ての点を含む大きな三角形を作成する (Create a large triangle that include all points)

関数points2trianglesでは全ての点を含む大きな三角形を 以下の手順により作成する。
Function points2triangles creates a large triangle that include all points by the following procedure.
点の\(x\)座標の最小値を\(x_{min}\), 最大値を\(x_{max}\)、 \(y\)座標の最小値を\(y_{min}\), 最大値を\(y_{max}\)とする。 これらの最小値・最大値で構成される長方形を考える(図2)。
Let \(x_{min}\) and \(x_{max}\) be the minimum and maximum values of the \(x\)-coordinates of the given points, respectively, and let \(y_{min}\) and \(y_{max}\) be those of the \(y\)-coordinates. Consider a rectangle composed of these minima and maxima (Fig. 2).

図2. 点の範囲を囲む長方形。
Fig. 2. A rectangle that bounds the points.

この長方形の中心点を\((x_c,y_c)\)、長い方の辺を\(L\)とする。 すなわち\(x_c=(x_{min}+x_{max})/2\), \(y_c=(y_{min}+y_{max})/2\), \(L=\max\{x_{max}-x_{min},y_{max}-y_{min}\}\)である。 点(\(x_c,y_c)\)を中心とする直径\(d=1.5L(>\sqrt{2}L)\) すなわち半径\(r=0.75L\)の円を考えれば、 全ての点がこの円内に含まれる(図3)。


図3. 全ての点を囲む円。
Fig. 3. A circle that includes all points.

この円を内接円とする、1つの辺が\(x\)軸に平行な正三角形を考える(図4)。 円の中心から三角形の底辺までの距離が\(r\)であり、 そこから三角形の左右の頂点までの距離が\(\sqrt{3}r\)である。 また、円の中心から三角形の上部の頂点までの距離は\(2r\)となる。 したがって三角形の3つの頂点の座標は \((x_c-\sqrt{3}r,y_c-r)\), \((x_c+\sqrt{3}r,y_c-r)\), \((x_c,y_c+2r)\) である。
Consider an equilateral triangle for which the circle created above is the inscribed circle. Assume that one edge of the triangle is parallel to the \(x\)-axis (Fig. 4). The distance from the center of the circle to the lower edge of the triangle is \(r\), and the distance from this contact point to the left and right vertexes of the triangle is \(\sqrt{3}r\). The distance from the center of the circle to the top vertex of the triangle is \(2r\). Therefore, the coordinates of the three vertexes of the triangle are \((x_c-\sqrt{3}r,y_c-r)\), \((x_c+\sqrt{3}r,y_c-r)\), and \((x_c,y_c+2r)\).

図4. 全ての点を囲む三角形。
Fig. 4. A triangle that includes all points.


(2) 1つ目の点を追加する (Add the 1st point)

1つ目の点を選び、 その点と上で作成した三角形の各頂点を結ぶ。 今回の例では(1.2, 9.8)が1つ目の点として選択される(図5)。
Choose the 1st point, and connect this point with the three convexes of the triangle created above. In this example, (1.2, 9.8) is chosen as the 1st point (Fig. 5).

図5. 追加した点およびその点と三角形の頂点を結ぶ線(赤)。
Fig. 5. The point added and lines connecting this point with the convexes of the triangle.

続いて、全ての要素三角形(別の三角形を内部に含まない三角形)の 外接円を描画する(図6)。
Next, plot the circumscribed circles for all elementary triangles (triangles that do not include other triangles) as shown in Fig. 6.

図6. 要素三角形の外接円。
Fig. 6. The circumscribed circles for elementary triangles.


(3) 2つ目の点を追加する (Add the 2nd point)

2つ目の点を選ぶ。 今回の例では(3.4, -7.6)が選択される(図7)。
Choose the 2nd point. In this example, (3.4, -7.6) is chosen for this point (Fig. 7).

図7. 選択した2つ目の点(赤)。
Fig. 7. The 2nd point chosen (red).

先に作成した三角形の外接円のうち、 新しく追加した(2つ目の)点を内包するものを探索する。 今回の例ではそのような外接円は1つだけである。 この外接円に対応する三角形に注目する(図8)。
Search the circumscribed circles of triangles created previously that include the newly added (2nd) point. Only one circle satisfies this condition in this example. Focus on the triangle corresponding to this circle (Fig. 8).

図8. 選択した2つ目の点を内包する三角形と外接円(水色)。
Fig. 8. The triangle and its circumscribed circle that include the 2nd point chosen (blue).

新しく追加した(2つ目の)点と、この三角形の頂点とを線で結ぶ(図9)。
Connect the newly added (2nd) point and the convexes of this triangle (Fig. 9).

図9. 選択した2つ目の点と、注目する三角形の頂点とを結ぶ線(赤)。
Fig. 9. Lines connecting the 2nd point chosen and the convexes of the triangle to focus.

得られた全ての要素三角形についてあらためて外接円を描画する(図10)。
Draw the circumscribed circles for all updated elementary triangles again (Fig. 10).

図10. 更新後の全ての要素三角形の外接円(灰色)。
Fig. 10. The circumscribed circles for all updated elementary triangles (grey).


(4) 3つ目の点を追加する (Add the 3rd point)

3つ目の点を選ぶ。 今回の例では(-5.6, 5.4)が選択される(図11)。
Choose the 3rd point. In this example, (-5.6, 5.4) is chosen for this point (Fig. 11).

図11. 選択した3つ目の点(赤)。
Fig. 11. The 3rd point chosen (red).

先に作成した三角形の外接円のうち、 新しく追加した(3つ目の)点を内包するものを探索する。 今回の場合、該当する外接円が2つある(図12)。
Search the circumscribed circles of triangles created previously that include the newly added (3rd) point. In this example, two circles include this point (Fig. 12).

図12. 選択した3つ目の点を内包する三角形と外接円(水色)。
Fig. 12. The triangles and their circumscribed circles that include the 3rd point chosen (blue).

この場合、それらの2つの外接円に対応する2つの三角形が共有する辺を削除する。 これにより、図12に水色で示した2つの三角形は1つの四角形に統合される(図13)。
In this case, remove the edge shared by the two triangles corresponding to the two circumscribed circles marked above. By this, the two triangles shown by blue in Fig. 12 are merged into a single quadrangle (Fig. 13).

図13. 2つの三角形をマージして得られる四角形(水色)。
Fig. 13. The quadrangle obtained by merging the two triangles (blue).

新しく追加した(3つ目の)点と、この四角形の頂点とを線で結ぶ(図14)。
Connect the newly added (3nd) point and the convexes of this quadrangle (Fig. 14).

図14. 選択した3つ目の点と、注目する四角形の頂点とを結ぶ線(赤)。
Fig. 14. Lines connecting the 3rd point chosen and the convexes of the quadrangle to focus.

得られた全ての要素三角形についてあらためて外接円を描画する(図15)。
Draw the circumscribed circles for all updated elementary triangles again (Fig. 15).

図15. 更新後の全ての要素三角形の外接円(灰色)。
Fig. 15. The circumscribed circles for all updated elementary triangles (grey).


(5) 4つ目の点を追加する (Add the 4th point)

4つ目の点を選ぶ。 今回の例では(-7.8, -3.2)が選択される(図16)。 この場合、この点を内包する円は1つだけ(図16水色)であり、 対応する三角形の頂点とこの点を結べば良い(図16赤)。
Choose the 4th point. In this example, (-7.8, -3.2) is chosen for this point (Fig. 16). In this case, only one circle (blue in Fig. 16) includes this point. Therefore, the point is connected with the vertexes of the triangle corresponding to this circle, as shown by red in Fig. 16.

図16. 選択した4つ目の点(赤)、それを内包する外接円(水色)、 その円に対応する三角形(水色)、 その三角形の頂点と4つ目の点を結ぶ線(赤)。
Fig. 16. The 4th point chosen (red), the circumscribed circle that includes this point (blue), the corresponding triangle (blue), and lines connecting the vertexes of this triangle ith the 4th point (red).

得られた全ての要素三角形についてあらためて外接円を描画する(図17)。
Draw the circumscribed circles for all updated elementary triangles again (Fig. 17).

図17. 更新後の全ての要素三角形の外接円(灰色)。
Fig. 17. The circumscribed circles for all updated elementary triangles (grey).


(6) 5つ目の点を追加する (Add the 5th point)

5つ目の点を選び、この点を内包する外接円を探索する。 今回の場合、3つの円がこの点を内包している(図18)。
Choose the 5th point, and search the circumscribed circles that include this point. In this example, three circles include this point (Fig. 18).

図18. 選択した5つ目の点(赤)、それを内包する外接円(水色)、 その円に対応する三角形(水色)。
Fig. 18. The 5th point chosen (red), the circumscribed circles that include this point (blue), and the corresponding triangles (blue).

これらの三角形が共有する辺を削除して五角形にした上で、 その五角形の頂点と新たに追加した(5つ目の)点を結ぶ(図19)。
Remove the common edges of these triangles. The result is a pentagon. Connect the vertexes of this pentagon with the newly added (5th) point (Fig. 19).

図19. 選択した5つ目の点(赤)、それを内包する外接円(水色)、 その円に対応する三角形を合体した五角形(水色)、 五角形の頂点と5つ目の点を結ぶ線(赤)。
Fig. 19. The 5th point chosen (red), the circumscribed circles that include this point (blue), the corresponding triangles that are merged into a pentagon (blue), and lines connecting the vertexes of this pentagon with the 5th point (red).

得られた要素三角形は図20のようになる。
Fig. 20 shows the elementary triangles obtained.

図20. これまでの操作で得られた要素三角形。
Fig. 20. The elementary triangles obtained.

最初にダミーで追加した3点(図20の緑) およびそれらの点を含む辺を削除すれば図21のようになり、 目的の三角形要素分割が得られる。
Removing the dummy three points added at the first step (green in Fig. 20) and edges that include these points, we obtain Fig. 21, which is the triangular element decomposition of the points.

図21. 最終的な三角形要素分割。
Fig. 21. The final decomposition of the points into triangular elements.


●アルゴリズムとしての記述 (Description as an algorithm)

以上のアプローチをアルゴリズムとして記述する。 図示しなくとも実行可能なアルゴリズムにする必要があり、 その際に課題になるのが 要素三角形(他の三角形を内包しない三角形)と、 他の三角形を内包する三角形の自動識別である。 例えば図5において、赤線を辺として含む3つの三角形はいずれも要素三角形であるが 緑線のみで構成される大きな三角形は要素三角形ではない。 これは目で見れば一目瞭然だが、 数値データのみを使って両者を識別するのは容易ではない。
Let us now describe the aforementioned approach as an algorithm, which needs to be executable without plotting and manual inspection. A task in this stage is an automatic distinction of elementary triangles (triangles that do not include other triangles) and those that include other triangles. For example in Fig. 5, the three triangles have have red-colored edges are elementary triangles, while the large triangle constituted by the green-colord-edges are not an elementary triangle. This is obvious by manual inspection; however, it is not easy to automatically distinguish them by numerical data alone.

図5(再掲).
Fig. 5. (reproduced)

この問題に対処するため、 コンピュータには点と点を結んだ「辺」を記憶させるのではなく、 「要素三角形」をリストとして直接記憶させる という考え方を取る。 例えば図5では 「赤色の点と緑色の三角形の3つの頂点を結んで線を引く」 という捉え方をするのではなく、 「緑色の三角形をリストから削除し、 緑色の1辺と赤色の点から成る3つの三角形をリストに追加する」 という捉え方をする。 このようにすればリストに含まれるのは常に要素三角形になる。
To cope with this requirement, the computer remembers a list of elementary triangles directly, instead of remembering the edges that connect two points. For example, do not regard Fig. 5 as connecting the red point with the three convexes of the green triangle; instead, regard this operation as first removing the green triangle from the list of elementary triangles, and then adding three triangles, each of which consists of a green edge and the red point. Following this concept, the list of triangles always consist of only the elementary triangles.
この考え方のもとで上記の手順をアルゴリズムとして記述すると以下のようになる。
Based on this concept, the procedures explained above can be described as an algorithm as follows.
  1. 全ての点を包含する大きな三角形(図5の緑)を作成する。 この三角形のみを含むように「要素三角形のリスト」を初期化する。
    Create a large triangle (green in Fig. 5) that includes all points. Initialize the “list of elementary triangles” to include only this large (green) triangle.

  2. 未処理の点が無くなるまで以下の処理を繰り返す。
    Repeat the following procedures until no points have been processed.

    1. 「要素三角形のリスト」にある全ての三角形について外接円を求める。
      Determine the circumscribed circles for all triangles in the “list of elementary triangles”.

    2. 未処理の点を1つ選ぶ。
      Choose a point that has not been processed.

    3. 外接円がその点を含む全ての三角形を 「要素三角形のリスト」から削除する。
      Remove all triangles whose circumscribed circles include that point from the “list of elementary triangles”.

    4. 前のステップで削除した要素三角形の1辺 (削除した複数の要素三角形によって共有されていた辺を除く)と 現在処理中の点によって三角形を作成する。 それらを全て「要素三角形のリスト」に追加する。
      Constitute a triangle by the currently processing point and an edge of an elementary triangle that has been removed in the previous step. Add all triangles constituted in this way to the “list of elementary triangles” as long as the edge was not shared by multiple removed elementary triangles.

  3. 最初のステップで追加したダミーの点を頂点に含む三角形を 「要素三角形のリスト」から削除する。
    Remove triangles that have vertexes at the dummy points that have been added in the first step from the “list of elementary triangles”.


◆補足(Additional notes)