ボロノイ図を利用した従来より連続性の高い多次元補間法の開発

使用 Voronoi 图开发比传统方法具有更高连续性的多维插值方法

• 批准号: 12875021
• 负责人: 杉原 厚吉
• 金额: $ 1.47万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Exploratory Research
• 财政年份: 2000
• 资助国家: 日本
• 起止时间: 2000 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-12875021/
• 关键词: 多次元補間; ボロノイ図; G1連続; グレゴリーパッチ; 曲率最小化; 多価関数; 三角形ベジエパッチ; 不規則メッシュ; 曲率極小面; 自然近傍; 局所座標; ドロネー分割

本研究の目的は,多次元空間にランダムに配置された観測点でのデータから,観測点以外の点での値を補間するための,従来のものより連続性の高い手法を開発することであった.この目的のもとで,最終年度である本年度は次のような研究実績を得ることができた.昨年度は2次元に配置された観測点での高さのデータから地形を補間によって求めるG1連続曲面の新しい補間法を構成したが,本年度は,それを3次元空間に配置されたデータ点を通過する曲面補間法へ拡張した.これは,地形にたとえるとオーバーハングを許す補間とみなすことができ,また多価関数の補間ということもできる.このように多価関数とみなす補間の拡張は,直接には難しいため,本研究では,3次元空間に埋め込まれた2次元曲面を円板と同相ないくつかのパッチに分解し,それぞれのパッチを2変数関数とみなすというパラメータ化によって,昨年度の方法に近い定式化を行った.このパラメータ化によっても問題は格段に難しく,昨年度のようなベジエ曲面の貼り合わせでは計算が著しく不安定となることがわかった.そこでパッチに張る曲面を,ベジエパッチより自由度の高いグレゴリーパッチに切り替え,追加された自由度を利用して計算の安定化をはかった.その結果,球と同相な曲面,トーラスと同相な曲面などに関してはなめらかな補間が可能であることを確認できた.しかし,今のところ,数学的にはG1連続が保証されるという意味でなめらかではあるが,大域的に見ると不必要なうねりがまだ残されており,これを克服することが次の課題として残されている.基本的には,曲率の2乗和の曲面全体での積分を最小化するという方針で目的が達成されると考えているが,この積分は厳密に計算することが難しいため,何らかの近似が必要となる.現在の方法では,局所的に曲面の法線を推定し,それに平行な方向へ射影することによって昨年度の方法に帰着させている.これの近似精度が十分ではないため,より精度の高い近似を今後追求していきたい.

The purpose of this study is to develop a high level of connectivity between the measurement points in the multi-dimensional space and the compensation points outside the measurement points. This year's research results are achieved. Last year, the 2-dimensional space was allocated to the measurement point, and the terrain was interpolated. The new interpolation method for G1 continuous surface was constructed. This year, the 3-dimensional space was allocated to the measurement point. This is the first time I've ever seen a woman who's had sex with someone else. In this study, 3-dimensional space is embedded in 2-dimensional surface, and 2-dimensional surface is decomposed into 2-dimensional space. This problem is difficult to solve, but the calculation is unstable. The surface of a curved surface, the degree of freedom, the degree of freedom, the degree of As a result, spherical in-phase curved surfaces, spherical in-phase curved surfaces, spherical The problem of mathematics is that it is not necessary to solve the problem of mathematics. The integral of the curvature of the basic surface is minimized. The policy is to achieve the goal. The integral is to calculate the density. The approximation is necessary. Now the method is to estimate the normal line of the curved surface of the bureau, and to project the parallel direction. The accuracy of approximation is very high, and the accuracy of approximation is high.

项目成果

A.Okabe B.Boots,K.Sugihara and S.-N.Chiu: "Spatial Tessellations-Concepts and Applications of Voronoi Diagrams,Second Edition"John Wiley and Sons. 671+xvi (2000)

A.Okabe B.Boots、K.Sugihara 和 S.-N.Chiu：“空间镶嵌 - Voronoi 图的概念和应用，第二版”John Wiley and Sons。

室谷浩平, 杉原厚吉: "不規則メッシュ上のG1連続な補間局面の生成法"情報処理学会グラフィックスとCAD研究会. CG・105・9. (2001)

Kohei Murotani、Atsuyoshi Sugihara：“不规则网格上的 G1 连续插值表面的生成方法”日本图形学和 CAD 研究组信息处理学会 CG·105·9。

K.Kobayashi, K.Sugihara: "Crystal Voronoi Diagram and Its Applications to Collision-Free Paths"Computational Science-ICCS 2001, Lecture Notes in Computer Science. 2073. 738-747 (2001)

K.Kobayashi、K.Sugihara：“水晶沃罗诺伊图及其在无碰撞路径中的应用”计算科学-ICCS 2001，计算机科学讲义。

H.Hiyoshi and K.Sugihara: "A sequence of generalized coordinate systems based on Voronoi diagrams and its application to interpolation"Proceedings of Geometric Modeling and Processing 2000. 242-250 (2000)

H.Hiyoshi 和 K.Sugihara：“基于 Voronoi 图的广义坐标系序列及其在插值中的应用”《几何建模与处理论文集》2000 年。242-250 (2000)

Daniel FOGARAS, Kokichi SUGIHARA: "Topology-oriented construction of line arrangements"IEICE Transactions of Fundamentals of Electronics, Communications and Computer Sciences. E85-A・5. (2002)

Daniel FOGARAS、Kokichi SUGIHARA：“线路排列的拓扑导向构造”IEICE 电子、通信和计算机科学基础知识汇刊 E85-A·5 (2002)。