tcql/greiner-hormann

语言: JavaScript

git: https://github.com/tcql/greiner-hormann

Greiner-Hormann多边形裁剪,具有简并处理
Greiner-Hormann polygon clipping, with degeneracy handling
README.md (中文)

Greiner-Hormann多边形裁剪

Build Status

这是Greiner-Hormann多边形裁剪算法的实验性实现,具有额外的简并处理。

  • 支持 支持孔 支持多边形输入
  • 操作 联盟 相交 减去
  • 相对稳定但在某些情况下可能会产生无效结果。这是因为: 对于GH,退化处理不是一个完全回答的问题 GH没有用于裁剪多个多边形或处理空洞的内置规定

最终目标是提供一个基本多边形裁剪库,它将支持在TurfJs中使用的集合理论几何操作,作为JSTS依赖的替代。

基准

node bench

测试

npm test

将执行所有操作以及内置实用程序的测试用例。

已知的问题

  • 当前的实现不能返回行或点,因此一些退化集将只返回任何内容。
  • 需要一些重构
  • 未完全优化 - 使用级联联合和边界框预检查可以大大提高分解剪切调用

来源

  • 格瑞纳 - 霍曼算法
  • 退化处理(见注释)
  • Python Polyclip
  • Python Polyclip +一些简并处理

笔记

  • 人们已经注意到,退化处理文件(“具有退化的任意多边形的剪辑”)已被撤销,因为它并未真正解决它声称的所有案例。因此,我偏离了它的建议,但总的来说我正在使用本文所述的技术(如in / on / out顶点标记和交叉点去除)

本文使用googletrans自动翻译,仅供参考, 原文来自github.com

en_README.md

Greiner-Hormann Polygon Clipping

Build Status

This is an experimental implementation of the Greiner-Hormann polygon clipping algorithm, with additional degeneracy handling.

  • Support
    • Supports holes
    • Supports multi-polygon inputs
  • Operations
    • union
    • intersect
    • subtract
  • Relatively Stable but may produce invalid results in some cases. This is because:
    • Degeneracy handling is not a fully answered question with GH
    • GH has no built in provision for clipping multiple polygons or dealing with holes

The end goal of this is to provide a base polygon clipping library that will support set-theoretic geometry operations for use in TurfJs, as a replacement for the JSTS dependency.

Benchmarks

node bench

Tests

npm test

Tests cases for all operations as well as the built in utilities will be executed.

Known Issues

  • The current implementation cannot return lines or points, so some degenerate sets will simply return nothing.
  • Needs some refactor
  • Not fully optimized - decomposing clipping calls could be greatly improved using cascade unions and bounding box pre-checks

Sources

Notes

  • It's been noted that the Degeneracy handling paper ("Clipping of Arbitrary Polygons with Degeneracies") has been withdrawn because it doesn't truly solve all cases it claims to. As such, I've deviated somewhat from it's recommendations, but in general I'm using the techniques (such as in/on/out Vertex labelling and intersection removal) described in the paper