有效地找到一组线的交点

Question

我正在通过 determinants 找到一组线的交点。但是，为了查找所有交叉点，我正在检查每一行与其他每一行，创建 O(n^2) 检查。

是否有更有效的方法来检查所有交叉路口？我害怕在尝试整理数百或数千行之间的交集时运行时间。

Answer 1

请说明 - 您是指无限线吗？

对于线段，有高效的 Bentley-Ottmann 算法。

对于 N 条无限直线，大约有 N^2 个交叉点（如果它们中的大多数不平行），因此您的方法在复杂性方面是最优的（也许可以进行微优化）

编辑： 阐明了任务描述 Bentley-Ottmann 看起来像是开销。

Find intersections of lines with clipping window
(for example, using Liang-Barsky algorithm)
Consider only lines that intersect window

Scan top window border from left corner to the right
Insert every line end into the binary search tree 
(and add link to this tree node from the paired end to the map) 


Scan right window border from top corner to the bottom right one
Check whether current line already has another end in the tree/map
If yes
    all lines with ends between positions of the first and 
    the second ends do intersect with it
    Calculate intersections and remove both line ends from tree and map
else
  Insert line end into the list

Continue for bottom and left edge.

复杂度O(N)用于初步处理，O(K + MlogM)用于相交window矩形和K个交点的M条线（注意K可能约为N^2）

示例：围绕周边行走的树状态

 E               //and map F to E node
 EG              //and map H to G
 EGI     
 EGIK
 EGIK + H
      H has pair point G, so GH intersect IJ and KL
      remove G
 EIK
 EIK + F
      F has pair point E, so EH intersect IJ and KL
      remove E
 IK
 IK + J
      J has pair point I, so IJ intersect KL
      remove I
 K
 K+L  
    remove K
 end (5 intersections detected)

有效地找到一组线的交点

Efficiently finding the intersections of an array of lines

language-agnostic

geometry

lines

points