xtorcga3D?計算幾何算法庫

演示地址

案例：

文檔與演示（國內(nèi)鏡像）網(wǎng)速快

文檔與演示（github）

• 點與其他元素的距離 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

使用

• 全部引用;：

import * as cga from "xtorcga";
function randomV3() {
  return cga.v3(
    Math.random() * 100 - 50,
    Math.random() * 100,
    Math.random() * 100 - 50
  );
}

var point = new cga.Point().copy(randomV3());
var seg = new cga.Segment(randomV3(), randomV3());
var result = point.distanceSegment(seg);

• 按需求引用：

import { v3, Point, Segment } from "xtorcga";
function randomV3() {
  return v3(
    Math.random() * 100 - 50,
    Math.random() * 100,
    Math.random() * 100 - 50
  );
}

var point = new Point().copy(randomV3());
var seg = new Segment(randomV3(), randomV3());
var result = point.distanceSegment(seg);

• 網(wǎng)頁嵌入：直接下載使用 build 目錄下面的 cga.js，包含到項目中

<script src="cga.js" />
或者
<script src="https://raw.githack.com/yszhao91/xtorcga/master/build/cga.js" />
<script>
  var point = new cga.Point(1, 2, 3);
  var line = new cga.Line(
    new cga.Vector3(10, 10, 20),
    new cga.Vector3(20, 15, 10)
  );
  var result = point.distanceLine(line);
</script>

項目編譯

npm install
國內(nèi)
cnpm install

npm run build //編譯到build目錄下
npm run dev  //運行項目，自己更改源碼測試

對象的類名

1. 點：Point
2. 直線：Line
3. 射線：Ray
4. 線段：Segment
5. 圓圈：Circle
6. 平面：Plane
7. 三角形：Triangle
8. 矩形：Rectangle
9. 圓盤：Disk
10. 球體：Sphere
11. 膠囊體： Capsule
12. 包圍盒：Box

已經(jīng)實現(xiàn)算法

在同一平面點集的凸包

已完成

var convexHull = new ConvexHull(points, { planeNormal: cga.Vector3.UnitZ });
var hull = convexHull.hull;

3d 凸包

進行中

同一平面點集 delauny 三角網(wǎng)構(gòu)建

進行中

3d 點集 delauny 四面體構(gòu)建

進行中

同一平面 voronoi 圖構(gòu)建

進行中

3d voronoi 圖構(gòu)建

進行中

最近點對問題

點集合中最近找出距離最近的一對點 算法時間 O(nlogn)

進行中

折線或者路徑簡化

折線或者路徑中過密或者過直的點去除;
(2020 年 1 月 17 增加)
/**
 * 簡化點集數(shù)組，折線，路徑
 * @param {*} points 點集數(shù)組，折線，路徑 ,繼承Array
 * @param {*} maxDistance  簡化最大距離 默認值0.1
 * @param {*} maxAngle  簡化最大角度 弧度 默認值 Math.PI / 180 * 5
 */
simplifyPointList(points, maxDistance, maxAngle);

距離

一級目錄與二級目錄存在相應距離算法關(guān)系

• 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

相交

相交可以使用距離算法來實現(xiàn)，準確的說距離中的 closets 最近點在 distance 為 0(小于 1e-4，精度可以自定義)的時候也就是交點,parameters 表為 0 或 1 可以判斷為端點相交

偏移

• Segment

切割

• Segment
  • Segment
• Plane
  • Segment
  • Triangle

參考文章

計算機幾何算法（CGA）專欄 https://zhuanlan.zhihu.com/c_1196384168014368768