3D 计算几何算法库(3D Computional Geometry Algorithm)
inspire by Wild Magic
概要
Computional Geometry Algorithm implement JavaScript,javascript 实现计算机几何算法库,实现比如像距离,相交,包含,偏移,平行垂直判断,正负位置等算法
如果你需要计算几何类的算法还没实现,可以 issue 提出,获取 Q 群联系我,优先实现
演示地址
案例:
-
点与其他元素的距离 http://dcgraph.gitee.io/xtorcga/guide/distPointAll.html
-
线与其他元素的距离 http://dcgraph.gitee.io/xtorcga/guide/distLineAll.html
-
射线与其他元素的距离 http://dcgraph.gitee.io/xtorcga/guide/distRayAll.html
-
线段与其他元素的距离 http://dcgraph.gitee.io/xtorcga/guide/distSegmentAll.html
-
常用 https://yszhao91.github.io/xtorcga/guide/%E5%B8%B8%E7%94%A8.html
安装
npm install xtorcga -D
使用
- 全部引用;:
; { return cga;} var point = ;var seg = ;var result = point;
- 按需求引用:
; { return ;} var point = ;var seg = ;var result = point;
- 网页嵌入:直接下载使用 build 目录下面的 cga.js,包含到项目中
或者
项目编译
npm install
国内
cnpm install
npm run build //编译到build目录下
npm run dev //运行项目,自己更改源码测试
对象的类名
- 点:Point
- 直线:Line
- 射线:Ray
- 线段:Segment
- 圆圈:Circle
- 平面:Plane
- 三角形:Triangle
- 矩形:Rectangle
- 圆盘:Disk
- 球体:Sphere
- 胶囊体: Capsule
- 包围盒:Box
已经实现算法
在同一平面点集的凸包
已完成
var convexHull = points planeNormal: cgaVec3UnitZ ;var hull = convexHullhull;
3d 凸包
进行中
同一平面点集 delauny 三角网构建
进行中
3d 点集 delauny 四面体构建
进行中
同一平面 voronoi 图构建
进行中
3d voronoi 图构建
进行中
最近点对问题
点集合中最近找出距离最近的一对点 算法时间 O(nlogn)
进行中
折线或者路径简化
折线或者路径中过密或者过直的点去除;2020 年 1 月 17 增加/** * 简化点集数组,折线,路径 * @param * @param * @param */;
距离
一级目录与二级目录存在相应距离算法关系
- Point
- Point
- Line
- Ray
- Segment
- Circle
- Plane
- Triangle
- Rectangle
- Disk
- Sphere
- Capsule
- Line
- Line
- Ray
- Segment
- Triangle (2020 年 1 月 17 增加)
- Ray
- Ray
- Segment
- Triangle (2020 年 1 月 17 增加)
- Segment
- Segment
相交
相交可以使用距离算法来实现,准确的说距离中的 closets 最近点在 distance 为 0(小于 1e-4,精度可以自定义)的时候也就是交点,parameters 表为 0 或 1 可以判断为端点相交
偏移
- Segment
切割
- Segment
- Segment
- Plane
- Segment
- Triangle
参考文章
计算机几何算法(CGA)专栏 https://zhuanlan.zhihu.com/c_1196384168014368768
展望
项目将会不断完善,如果你有好的想好可以提交你的想法。欢迎 star,让项目更进一步
讨论
QQ 群:469014839 by: 换孤
本人 2013 接触从事 webgl/threejs 工作,开发经验 7 年左右,一直以来都想着开源,结交更多志同道合的朋友
其他开源项目 看我的 github 主页 地址:https://github.com/yszhao91 欢迎大家 follow star,希望开源能帮到大家