空間分割法を用いた線分交差列挙アルゴリズム

DOI Web Site Web Site 参考文献6件

書誌事項

タイトル別名
  • An Algorithm for Enumerating Intersections of Line Segments Using Space Segmentation Method
  • クウカン ブンカツホウ オ モチイタ センブン コウサ レッキョ アルゴリズム

この論文をさがす

抄録

<p>This paper describes a space segmentation method (SSM)-based algorithm for enumerating all intersections of given line segments on a bounded plane, which is a classical problem in computational geometry. Here, SSM is an algorithm for finding all combinations of input data that generate points satisfying some conditions for a particular space. Assuming that the minimum distance between these points is bounded, the algorithm finds the combinations by recursively segmenting the space. Defining a hierarchical mesh system, we designed an efficient and simple algorithm for the line segment intersection enumeration problem. Although we have been unable to estimate the computational complexity of the algorithm, the performance on random inputs of a program implementing the algorithm was extremely high. It was also faster than an implementation of a well-known algorithm by Bentley and Ottmann(4). Moreover, as our algorithm is quite simple, it can easily be rewritten as a parallel program. In a twelve-threaded environment, such a program ran approximately 2.6 times faster than a single-threaded version of the program.</p>

収録刊行物

参考文献 (6)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ