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

[随性而为]

如果楼主说的方片是单位长度是1的立体方块的话，那我觉得可以把这立体的模型按照x=1，x=2，x=3……的截面划分，分别数占了多少个单位长度是1的正方形，这只是我初期的思路，至于怎么得到截面y-z的关系式，还在思考中……

 

难道要计算每个三角面的平面解析式，然后把x的值代入，得到各个y-z的关系式，再从中选取这几个关系式围成的图形吗

 

这样的话现在最麻烦的是如果这个雕塑比较复杂的话如何才能判断出哪几个y-z表达式围成的图形才是我们需要的

 

 

针对这个问题可以有这么一个解决方法：输入数据者在输入数据时可以额外输入哪几个三角面能构成封闭空间，这样可以缩小判断范围，且结果一定是较为准确的。但如果不输入这些信息的话，凭现在的我很难进行判断，楼下貌似有人理解了我的意思，是求环状图形，但这个实现起来貌似有点麻烦，毕竟直线是无限的，线一多交点也越来越多，如果楼下知道解决办法，望告知，我再想一想……（已告知）

 

昨天我是忘记考虑范围了，如果在三角面在每个y-z面上考虑y和z的范围的话，就可以把直线转化为线段，这样线段之间能围成的封闭图形就能显而易见得给计算机判断了。

 

至于楼下  楼主和另一位大佬提到的大环套小环，凸面凹面的问题，其实是有规律的，凸面没什么考虑的

 

 

四月 9, 2020，由随性而为修改

[随性而为]

51 分钟前, yhz012 说道:

 

另外前面有人提到的沿某个轴做切割也可以

这样在每个切面能够确定地得到一集合的线段

对该集合取出一个线段，找能接上该线段的线段，直到完成一个环

如果集合非空，继续重复完成环

最后会得到切面上的一集合的环

接着判定方块是否在任意一个环内就完了

 

规约到了2D，判定点在封闭多边形内，暴力三角化然后直接判断点在三角内就完了

其实2D中只要知道在哪几个环状图形内就没必要三角化了，只需要知道环状图形的解析式依然可以用y=1，y=2……求出z的各个值，然后(int )z1-(int)z2+1就是每个y上的方格数了，现在蛋疼的就是怎么求出环形图形

四月 8, 2020，由随性而为修改

[随性而为]

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

 

关于这个，我突然发现我编题的时候没有考虑STL本身是空心的情况

如果要求STL的空心搭出来还是空心（挤没了的不算）的话，平面截出来就会有大环套小环的问题。考虑在线段集里记录每个线段的法向？

如果是这样的话，我在考虑是不是不用知道环形图形反而方便一些，计算出每个y-z解析式，然后对y=1求出z1，z2……，取 i>=min(z1，z2……)&& i<=max(z1，z2……),然后看(x,y,i)是否在雕塑内，接下来y=2……，不过这个太暴力了，渣渣只能想到这么做了……，而且我也不知道如何判断点是不是在封闭空间内（好像前面一位大佬一开始就讲过了，然而原理并不太懂）

麻嘚，既然这样的话一开始就

for i in z[ ]

    for j in y[ ]

       for k in x[ ]

暴力破解不就省事多了

四月 8, 2020，由随性而为修改

[随性而为]

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），然而没有哪些三角面可以构成封闭空间的相关信息

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

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