jts
jts 源码学习。学习源码，才能更深入的了解原理
index
从index的package-info里面可以看到，这个包提供各种空间索引，SpatialIndex接口里面定义了索引的4个操作，增删查，实现这个接口的有3个类：HPRtree，Quadtree和STRtree。下面简要介绍下包内的内容。
| 名称 | 空间索引 | 使用场景 | help |
|---|---|---|---|
| Binary Interval Tree | 否 | 四叉树的一维版本。给定一个包含 n 个区间的集合 S 和一个查询点 q，报告所有包含 q 的区间；和重叠区间搜索问题：给定一个包含 n 个区间的集合 S 和一个查询区间 Q，报告 S 中与 Q 重叠的所有这些区间。 | https://iq.opengenus.org/interval-tree/ |
| Monotone Chains | 否 | 凸包 | https://zhuanlan.zhihu.com/p/158043191 |
| Hilbert-Packed R-tree | 是 | 是R-tree的一种变体，是多维对象的索引，基于分形曲线构建静态 R 树的压缩算法 | dim(E(a)∩E(b)) |
| intervalrtree | 否 | 一维间隔实现R树索引 | |
| KD-Tree | 否 | 分割k维数据。主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。 | https://en.wikipedia.org/wiki/K-d_tree |
| Quadtree | 是 | 将已知范围的空间等分成四个相等的子空间 | |
| R-tree | 是 | MBR最小边界矩形的方法，从叶子节点开始用矩形将空间框起来 | |
| sweepline | 否 | 它用于计算索引中间隔之间的所有重叠 |
可以参考JTS-SpatialIndex空间索引使用说明（十五）
srtree
https://developer.aliyun.com/article/750351 https://www.cnblogs.com/fly2wind/p/14525405.html https://www.jianshu.com/p/06ba03e1692f https://www.bbsmax.com/A/Vx5MXQG9JN/ http://t.zoukankan.com/naaoveGIS-p-6774549.html
https://blog.csdn.net/wk1134314305/article/details/76408181 继续 https://gitee.com/shengshifeiyang/jts-learning/blob/master/docs/jts-core/demo/foot-point.md https://www.zhihu.com/question/268006579
algorithm
geom
从官网地址中可以看到，DE-9IM矩阵值，指两个几何之间的拓扑关系，这种拓扑关系可以用于描述两个几何图形空间关系的一种标准。 更多详情可以参考ogc官网或者wikipedia。
DE-9IM矩阵是带有整数项的3x3矩阵，矩阵条目表示每个交点的可能维度 。通常将每个几何图形分为三部分：外部（exterior),边界（boundary)和内部(interior)，如下表格。
| Interior | Boundary | Exterior | |
|---|---|---|---|
| Interior | dim(I(a)∩I(b)) | dim(I(a)∩B(b)) | dim(I(a)∩E(b)) |
| Boundary | dim(B(a)∩I(b)) | dim(B(a)∩B(b)) | dim(B(a)∩E(b)) |
| Exterior | dim(E(a)∩I(b)) | dim(E(a)∩B(b)) | dim(E(a)∩E(b)) |
布尔形式
矩阵的定义域为{-1,0,1,2}，常见的拓扑关系描述符大概10种左右
- 0,1,2表示非空，用T进行表示
- 空集-1用F表示
- *表示是什么都可以(所以不需要计算)
可以参考wikipedia,jts或者GEOS找到相关的返回值，部分如下
| 谓词 | 返回值 |
|---|---|
| 相等（Equals) | T*F**FFF* |
| 相离（Disjoint) | FF*FF**** |
| 相接（Touches) | FT*******\F**T*****\F***T**** |
| 覆盖（Covers) | T*****FF*\*T****FF*\***T**FF*\****T*FF* |
| 叠置（Overlaps) | T*T***T**\1*T***T** |
参考
MBR
在JTS或shapely程序中，为了提升计算性能，一般还会先进行MBR判断，再进行DE-9IM判断
Area
jts使用鞋带定理计算面积
空间关系
- 线段的拐向判断 可以利用矢量的叉积判断： p=（x1,y1）,q=(x2,y2) p×q=x1y2-x2y1;
若PxQ>0，则说明P在Q的顺时针方向
若PxQ<0，则说明P在Q的逆时针方向
若PxQ=0，则说明PQ共线(共线有可能反向也可能正向)
- 判断点是否在线段上 设点为Q，线段为P1P2，判断点Q在该线段上的依据是（Q-P1）X(P2-P1) = 0，这样就保证Q在P1P2这条直线上，但是还是不能保证在P1P2的线段上，所以我们得多加个条件：且Q在P1,P2为对角顶点的矩形内
- 判断两线段是否相交 分为两步确定两天线段是否相交： ①快速排斥试验:mbr ②跨立试验:如果ab,cd相交，那么ab必跨过cd，那么（ac x ab ）x（bd xab）<=0
- 判断点是否在多边形内 一种是射线法，另一种是转角法。
https://www.cnblogs.com/zhongHW/p/11047020.html
geomgraph
io
operation
simplify
IntersectionMatrix
https://www.cnblogs.com/zhongHW/p/11047020.html
几何结构
DelaunayTriangulationBuilder
MinimumBoundingCircle
newVoronoiDiagramBuilder
度量函数
DistanceOp
DiscreteHausdorffDistance
AreaSimilarityMeasure
HausdorffSimilarityMeasure
空间算法
线段相交算法 RobustLineIntersector
数学函数
角度分析 Angle