xtorcga3D?計(jì)算幾何算法庫(kù)

演示地址

案例：

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

文檔與演示（github）

• 點(diǎn)與其他元素的距離 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)頁(yè)嵌入：直接下載使用 build 目錄下面的 cga.js，包含到項(xiàng)目中

<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>

項(xiàng)目編譯

npm install
國(guó)內(nèi)
cnpm install

npm run build //編譯到build目錄下
npm run dev  //運(yùn)行項(xiàng)目，自己更改源碼測(cè)試

對(duì)象的類名

1. 點(diǎn)：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)實(shí)現(xiàn)算法

在同一平面點(diǎn)集的凸包

已完成

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

3d 凸包

進(jìn)行中

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

進(jìn)行中

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

進(jìn)行中

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

進(jìn)行中

3d voronoi 圖構(gòu)建

進(jìn)行中

最近點(diǎn)對(duì)問(wèn)題

點(diǎn)集合中最近找出距離最近的一對(duì)點(diǎn) 算法時(shí)間 O(nlogn)

進(jìn)行中

折線或者路徑簡(jiǎn)化

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

距離

一級(jí)目錄與二級(jí)目錄存在相應(yīng)距離算法關(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

相交

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

偏移

• Segment

切割

• Segment
  • Segment
• Plane
  • Segment
  • Triangle

參考文章

計(jì)算機(jī)幾何算法（CGA）專欄 https://zhuanlan.zhihu.com/c_1196384168014368768