术语

名词解释
standards-compliant符合标准的

基础

两直线交点

HTTPS://WWW.CNBLOGS.COM/XZYXZY/P/10033130.HTML

HTTPS://IMAGES.CNBLOGS.COM/CNBLOGS_COM/XZYXZY/1374475/O_%E5%AE%9A%E6%AF%94%E5%88%86%E7%82%B9FLASH.PNG

  • 参考上图
  • A1P 与 A1A2 在同一条直线上

  • 另外 C X B 等于 A1P X B

    • 叉积的意义：平行四边形的面积

  • 所以，A1P 与 A1A2 的比例 T

    • 就是两个平行四边形的面积比例
  • A1P / A1A2 = (C X B) / (A1P X B) = T

  • 最后：P = A1 + A1A2 * T

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

      // * 点向法表示直线
  //调用前需保证 Cross(v, w) != 0
  // P, v 一条直线
  // Q, w 一条直线
  Point GetLineIntersection(Point P, Vector v, Point Q, Vector w){
Vector u = P - Q;
double t = Cross(w, u)/Cross(w, v);
return Q + v*t;
  }


  // * 两点法表示直线
  Point GetCrossPoint(Point A1, Point A2, Point B1, Point B2){
Vector a = A2 - A1;
Vector b = B2 - B1;
Vector c = B1 - A1;
double t = Cross(c, b) / Cross(a, b);

return A1 + a * t;  
  }

两直线相交

两次跨立实验

  • B1A1 X B1A2 与 B2A1 X B2A2 是否异号

    • (B1 —> A1, A2) 与 (B2 —> A1, A2) 构建向量

  • a1b1 x a1b2 与 a2b1 x a2b1 是否以后

    • (a1 —> b1, b2) 与 (a2 —> b1, b2) 构建向量

scipy.spacial.ConvexHull

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

  from scipy.spatial import ConvexHull

  # A 正方形，四个顶点，和中心（1,1）
  A = [[0, 0],
[2, 0],
[2, 2],
[0, 2],
[1, 1]]

  hull = ConvexHull(A)

  hull.simplices
  """
  array([[1, 0],
  [2, 1],
  [3, 0],
  [3, 2]], dtype=int32)
  """
  hull.vertices
  """
  array([0, 1, 2, 3], dtype=int32)
  """

概述

这是一个类 class,用来处理凸包问题

方法

hull.simplices

极边 Extreme Edge 的两个端点[终点，起点], 按逆时针方向

hull.vertices

极点 Extreme Point 的在 hull.points 中的索引 index

hull.points

ConvexHull 初始化用到的 points

图形计算库

simpy.spacial

python 符号运算库

scipy.spacial

python 库

cgal

https://www.cgal.org/ C++ 计算几何算法库 computational geometry algorithm library

算法

扫描线算法

线段交点的扫描线算法 Bentley-Ottmann algorithm

  • wiki https://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm#:~:text=The%20main%20idea%20of%20the,in%20sequence%20as%20it%20moves.&text=No%20three%20line%20segments%20intersect%20at%20a%20single%20point.