⚡

几何算法库Skill geometry-algorithm-library

几何算法库是一个专注于实现和提供计算几何核心算法的技能。它旨在为算法竞赛、编程挑战、图形学应用和需要空间计算的问题提供高效、可靠的代码解决方案。核心功能包括凸包计算（如格雷厄姆扫描）、线段与多边形相交判断、最近点对搜索、点在多边形内测试、以及高级的德劳内三角剖分和沃罗诺伊图生成。该技能支持多种编程语言（C++、Python、Java），并可根据需求生成可视化代码，是解决二维平面几何问题的强大工具箱。 关键词：计算几何，算法实现，凸包算法，线段相交，最近点对，点在多边形，德劳内三角剖分，沃罗诺伊图，竞赛编程，几何库

其他 0 次安装 2 次浏览 更新于 2/23/2026

名称: 几何算法库 描述: 实现计算几何算法 允许使用的工具:

  • 读取
  • 写入
  • 搜索
  • 全局匹配
  • 编辑

几何算法库技能

目的

为竞赛编程和算法问题实现计算几何算法。

能力

  • 凸包（格雷厄姆扫描法，安德鲁单调链算法）
  • 线段相交算法
  • 最近点对
  • 点在多边形内测试
  • 沃罗诺伊图，德劳内三角剖分
  • 多边形裁剪

目标流程

  • 计算几何

算法目录

凸包

  • 格雷厄姆扫描法 O(n log n)
  • 安德鲁单调链算法 O(n log n)
  • 贾维斯步进法 O(nh)

相交算法

  • 用于线段相交的扫描线算法
  • 本特利-奥特曼算法
  • 多边形相交

距离问题

  • 最近点对 O(n log n)
  • 最远点对（旋转卡壳法）
  • 点-多边形距离

三角剖分

  • 耳切法 O(n^2)
  • 德劳内三角剖分
  • 沃罗诺伊图

输入模式

{
  "type": "object",
  "properties": {
    "algorithm": { "type": "string" },
    "variant": { "type": "string" },
    "language": {
      "type": "string",
      "enum": ["cpp", "python", "java"]
    },
    "includeVisualization": { "type": "boolean", "default": false }
  },
  "required": ["algorithm"]
}

输出模式

{
  "type": "object",
  "properties": {
    "success": { "type": "boolean" },
    "code": { "type": "string" },
    "complexity": { "type": "object" },
    "usage": { "type": "string" }
  },
  "required": ["success", "code"]
}