娱乐 每 日 算 法 挑 战 【第0期，有红包】

[Mr.K 018]

1 小时前, 随性而为 说道:

针对这个问题可以有这么一个解决方法：输入数据者在输入数据时可以额外输入哪几个三角面能构成封闭空间，这样可以缩小判断范围，且结果一定是较为准确的

这个的话，原本的STL文件中三角面的存储是有序的（遵循右手法则），可以提供一些关于法向的信息（遗憾的是，本题中不一定这么存储www），然而没有哪些三角面可以构成封闭空间的相关信息

……而且我觉得这个信息的输入是件非常可怕的事情啊，一个几何体的三角面是很多的

[zheneko]

这已经超出了我的能力范围了，果然三次元区人均大佬

[随性而为]

13 分钟前, yhz012 说道:

已知环，可以再判断一下环是否是凸多边形，假设环的点我们是按照逆时针顺序排列（这个很简单判定），假设环上连续3个顶点是abc，计算ab与bc的向量积在单位z向量上的数量积，如果是正则b点为凹点，负则为凸点（实际上就是利用了向量积的右手性质来判断abc是“往左转”还是“往右转”）

假设b为凹点，那么沿着ab射线，必然和环相交一点，设为d，那么就可以用线段bd把环分成2个子环，继续判定凸性，直到所有子环为凸

接着给定一个凸环，以及另外一点x，假设环上相邻的两顶点为ij，那么继续求ij和jx的向量积在z方向的数量积，如果始终都是“往右转”，那么x就在凸环内了

 

 

另外实际上我的方案其实就是暴力破解，只是给这个暴力破解的过程提供一个判定该方块在多面体内的方法

学到了，不愧是和傅里叶老爷爷悉心交流多年的数学大神

一开始提到重心坐标什么的吓坏了，以为是什么高大上的做法，就不敢再看下去了……

[随性而为]

8 分钟前, Mr.K 018 说道:

这个的话，原本的STL文件中三角面的存储是有序的（遵循右手法则），可以提供一些关于法向的信息（遗憾的是，本题中不一定这么存储www），然而没有哪些三角面可以构成封闭空间的相关信息

……而且我觉得这个信息的输入是件非常可怕的事情啊，一个几何体的三角面是很多的

嘛，随便说说的，其实还是我不能判断点是否在雕塑内的锅，既然现在已经了解了怎么判断了，那我的方法就是——暴力破解（苦笑

[yhz012]

4 分钟前, 随性而为 说道:

学到了，不愧是和傅里叶老爷爷悉心交流多年的数学大神

一开始提到重心坐标什么的吓坏了，以为是什么高大上的做法，就不敢再看下去了……

那东西其实是用来快速判定某一点是否在凸多边形/多面体的，实际上和上面的等效。

对于二维情况，三角形只要解3个线性方程，但是如果环很大，比如说是n个顶点，那就要解n个线性方程。求n*n矩阵的逆还是饶了计算机吧（笑），不如上面说的判定右转来的快。

当然对于三维情况，就没法用上面的判定右转了。不过实际上如果已知凸多边形，选面abc，再取一顶点d，直接判断x是否和d在面同一侧。用这个方法遍历所有面也可以判断。

四月 8, 2020，由yhz012修改

[堕落之瞳]

当MC碰上了数学  我选择暴毙

[fubuki.ss]

引用

1. 输入本题的所有数据；
2. 解题；
3. 输出结果

这不就是机器学习吗（删掉

用边和顶点算体积…

感觉凸多边形的话还好，暴力扫过去也是能做的…

有凹面的话…不懂、去找找算法去

四月 8, 2020，由fubuki.ss修改

[在下东方大雕]

8 小时前, ZERC 说道:

二楼召唤阵

@ZERC @inuisanaa @随性而为 @NianRuoshui @魍魉QAQ @提辖 @yhz012 @摸鱼奇才咖啡喵

自己召唤自己可还行

[ZERC]

4 小时前, 在下东方大雕 说道:

自己召唤自己可还行

别在意这些细节....

复制粘贴的召唤阵...

[乱跑的泰兰德]

@水克火 转手邀请一个大佬过来每天刷题。

[乱跑的泰兰德]

目的：获得STL文件的所需方块

难点：三角面的相互包围的内部方块难以计算

 

首先获得边界信息：

1. MC的方块顶点意味着都是整数构成1x1x1的立体方块。

2. 三角面穿过方块才计算该方块，意味着没有接触或者三角面在方块中心，不构成方块。

 

以边界信息为前置条件，开始设计函数（只写思路了，具体写代码可能要麻烦死...）：

1. 创建一个大小为（Xmax - Xmin， Ymax - Ymin， Zmax - Zmin）大小的全0雕塑数组，每个点表示为1x1x1的方块的Xmin，Ymin，Zmin坐标。

2. 设计一个输入两个点（也就是一条线段）、一个数组，根据边界条件将数组内所有满足的方块值置为1的函数（也就是设计了一条线段穿过方块，方块值就置1的函数）。

3. 遍历所有STL文件的所有三角面，每个三角面都是从一个选中线段开始，然后根据等比三角形，朝着未被选中线段包含的点平行移动线段两端点，直到填充所有的三角形面，将所有雕塑数组中的三角面的值全都置为1。

4. 遍历雕塑数组中Zmax到Zmin的所有XY面，设计函数将XY内所有数值为1的闭合矩形平面内   所有0点置为1。

5. 累计第4步中所有1的数值，求和即为n。

 

四月 9, 2020，由mylifeyouwill修改