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

[Mr.K 018]

好的！经过一个晚上的商讨，我们的每日算法挑战要和大家见面了！

如标题所示本期是第0期，就是每日算法挑战的公测。下面放上简介！

1 这是什么？

每日算法挑战本质上不就是拿来热版的花招么

每日算法挑战，顾名思义，就是每天会po一道算法相关的题目，来让大家讨论讨论，做一做。当然了，这个每日算法挑战并不是什么ACM之类的算法题，各位就算交了代码也没有用。因此，大家只要说说算法和思路，最多给出伪代码就可以了。伪代码写得也可以随便一点，但是太过耍赖的“伪代码”也是不行的哦！比如这样的伪代码:

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

这样的伪代码说的就太模糊了，有点耍赖。我们约定除了众所周知的少数算法（如排序）之外，伪代码也要由常数时间内就能做完的动作（或自己定义的过程调用）组成。同样地，对于自定义数据结构也尽可能写的清楚一点为好。

如果觉得伪代码要求太复杂了，其实也不用非得写伪代码，只要能说明白算法的大致实现过程也可以。写得详细的可以拿到和伪代码一样的奖励哦！

2 有奖励吗！

有啊，当然有了！我们欢迎所有形式的讨论，尤其会对这样的贴子发放奖励：

• 首先给出了正确答案（或者相对本题可以接受的答案）的，可以拿到最多的奖励！
• 虽然不是首先给出答案，但是有一些新内容的（比如新方法啊，复杂度等等的讨论啊，算法思路的说明啊，以及正确性证明等等）；
• 参与讨论，有一些新颖的见解或者指出了其他人答案的bug的。

顺带一提，三种奖励可以叠加！

今天作为公测，我先放出来一道我随便杜撰的题吧!

 

第0期 我的世界

K想要在MC里搭一个雕塑。他手头有一个STL文件，里面保存了这个雕塑的样子。

题目中为了简化，认为STL文件由若干三角面组成，每个三角面由九个实数组成，前三个、第4-6个和第7-9个实数分别定义了三角面的三个顶点。可以认为每个STL文件中的各个三角面能围成一个封闭的几何体。

我们规定，对于每个MC中的方块区域，只要三角面穿过了这个区域，就要在那里搭上方块，并且这个雕塑是实心的，即几何体的内部也要填上方块。

K在搭建雕塑之前，首先要知道他要准备多少个方块，来计划挖矿（指给苦力ABCDE等人安排挖矿任务）。现在他想问问你，修雕塑要多少方块呢？

输入

第一行是一个整数n，表示这个STL文件中的三角面个数。

接下来有n行，每行有9个实数，分别表示三角面中的三个顶点，顺序是X1 Y1 Z1 X2 Y2 Z2 X3 Y3 Z3。

输出

输出一行，其中有一个整数，表示雕塑需要多少方块。

嗯……这个题是我杜撰的，因此没有预设的正确答案，大家可以畅所欲言。

[ZERC]

二楼召唤阵

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

[ZERC]

三楼补充召唤阵： @萨卡

[ラムダデルタ]

真就三次元算数区啊（蹭个红包

[Orochis]

头痛了，是数列题啊，看着就麻烦

[yhz012]

是计算几何，正好是我ddl要干的活，我死了

 

看了一下，可以理解为是判定点是否在多面体内？

然后这个多面体应该认为可以是非凸的

四月 8, 2020，由yhz012修改

[随性而为]

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

 

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

 

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

 

 

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

 

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

 

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

 

 

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

[Mr.K 018]

1 分钟前, Orochis 说道:

头痛了，是数列题啊，看着就麻烦

这个题其实是个图形学相关的题，一时兴起就出了这么一道（笑

[Orochis]

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

这个题其实是个图形学相关的题，一时兴起就出了这么一道（笑

反正肯定是带n的式子吧。我统称数列

[yhz012]

最平凡的情况是如果多面体确定为凸，那么文件内所有点当做顶点，直接用barycentric coordinates（翻译好像叫重心坐标？）

通过求判定点到各顶点距离反过来解线性方程组能得到barycentric coordinates，然后判定坐标的各分量是否在01之间，如果是，则在体内，否则在体外

 

然后对于非凸的情况就可以做分割得到凸多面体来带走了

 

暴力一点的分割凸多面体方案可以是拿出一个三角面，找和该三角面有公用边的另一个三角面（存在性需要证明，不过目测应该是必然存在的）

这两个三角面构成四面体，为凸，同时得到另外2个新三角面，加入到三角面列表

把所有pair遍历之后应该就能把整个几何体给三角化了

感觉这个三角化有点问题，不过已知顶点集（即输入文件），肯定有三角化的算法，翻一下工具书或者面向github编程一下就可以了吧（

 

看了一下因为涉及到坐标取整问题，所以大概对于同一个方块需要判定8次（即方块的8个顶点坐标），只要有一个在体内就判定这个方块是在体内

 

为了避免暴力遍历所有方块，可以用类似二分的方式先取(min x: max x, min y: max y, min z: max z)范围内的方块

然后均匀3刀得到8个小方块分别判定 1.小方块的8个顶点存在至少一个在几何体内， 2. 几何体的所有顶点存在至少一个在小方块内（直接判断xyz范围就好）。这两个条件任意满足则继续细分。如果两个都不满足直接丢了就好，肯定这个区域内没方块要放的

 

感觉应该还有不少可以优化的地方

 

 

 

 

另外前面有人提到的沿某个轴做切割也可以，切割的点选取输入文件中的全部z坐标，这样可以避免漏掉某些小三角形

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

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

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

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

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

 

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

四月 8, 2020，由yhz012修改

[原初の冷火]

这已经超出我的知识范围了

明明都是中文汉字  但是放在一起我就看不懂了

[NianRuoshui]

人傻了 咱才刚把排序学会

[Xchara]

这个门槛有点高，没学过大学的内容应该是做不了的。。。

[Mr.K 018]

25 分钟前, yhz012 说道:

最平凡的情况是如果多面体确定为凸，那么文件内所有点当做顶点，直接用barycentric coordinates（翻译好像叫重心坐标？）

通过求判定点到各顶点距离反过来解线性方程组能得到barycentric coordinates，然后判定坐标的各分量是否在01之间，如果是，则在体内，否则在体外

 

然后对于非凸的情况就可以做分割得到凸多面体来带走了

 

暴力一点的分割凸多面体方案可以是拿出一个三角面，找和该三角面有公用边的另一个三角面（存在性需要证明，不过目测应该是必然存在的）

这两个三角面构成四面体，为凸，同时得到另外2个新三角面，加入到三角面列表

把所有pair遍历之后应该就能把整个几何体给三角化了

感觉这个三角化有点问题，不过已知顶点集（即输入文件），肯定有三角化的算法，翻一下工具书或者面向github编程一下就可以了吧（

有一说一质心坐标那里我还得研究研究，但是三角化算法应该是没有问题的，因为每一次切下一个四面体，剩余的部分必然还是（一个或两个）闭合的多面体，只不过需要看一下新增的两个三角面是不是已有的边界，如果不是再加入到三角面集合里去

而且用质心坐标的话，怎么解决方块的顶点和中心点都在几何体外，但方块本身却要算进去这种情况呢

（请脑补糖葫芦，山楂是方形的，就是MC中的方块，竹签是那个几何体）

四月 8, 2020，由Mr.K 018修改

[yhz012]

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

有一说一质心坐标那里我还得研究研究，但是三角化算法应该是没有问题的，因为每一次切下一个四面体，剩余的部分必然还是（一个或两个）闭合的多面体，只不过需要看一下新增的两个三角面是不是已有的边界，如果不是再加入到三角面集合里去

我主要担心的就是可能会重复，或者更准确说是切到了几何体外面，因为可能正好这俩三角面是凹进去的，感觉还是有点问题

至于质心坐标，如果已经确定是四面体的话，应该是能找到现成的公式求坐标的

 

四月 8, 2020，由yhz012修改

[yhz012]

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

有一说一质心坐标那里我还得研究研究，但是三角化算法应该是没有问题的，因为每一次切下一个四面体，剩余的部分必然还是（一个或两个）闭合的多面体，只不过需要看一下新增的两个三角面是不是已有的边界，如果不是再加入到三角面集合里去

而且用质心坐标的话，怎么解决方块的顶点和中心点都在几何体外，但方块本身却要算进去这种情况呢

（请脑补糖葫芦，山楂是方形的，就是MC中的方块，竹签是那个几何体）

如果按照我robotics的方案就是暴力分小块……直到一般认为不会再有可能插在中间为止，这是暴力解决方案

 

或者考虑求四面体的4个面对立方体的6个面的交线，如果有交线则应当放置方块

这样的话可以把问题规约到已知两个凸几何体，求两几何体是否相交

需要判定

1. 几何体A的顶点是否在几何体B内→质心坐标可解

2. 几何体B的顶点是否在几何体A内→质心坐标可解

3. 几何体A的面是否与几何体B的面存在交线→求两面相交直线

以上三个任何一个为真，则相交

 

似乎二连了，抱歉

四月 8, 2020，由yhz012修改

[随性而为]

51 分钟前, yhz012 说道:

 

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

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

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

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

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

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

 

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

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

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

[Mr.K 018]

4 分钟前, yhz012 说道:

如果按照我robotics的方案就是暴力分小块……直到一般认为不会再有可能插在中间为止，这是暴力解决方案

 

或者考虑求四面体的4个面对立方体的6个面的交线，如果有交线则应当放置方块

这样的话可以把问题规约到已知两个凸几何体，求两几何体是否相交

需要判定

1. 几何体A的顶点是否在几何体B内

2. 几何体B的顶点是否在几何体A内

3. 几何体A的面是否与几何体B的面存在交线

以上三个任何一个为真，则相交

这个方法我觉得可行，总结一下大概的思路：

1. 将STL中的几何体三角化，分割成一个四面体集；

2. 维护一个放置方块集（初始为空），对四面体集的每一个元素：

2.1 确定要判定的四面体涉及哪些方块（可以通过x,y,z三个轴的最小值、最大值来限定）；

2.2 对每个上一步中得出要考虑的方块，进行求交运算，若相交则入方块集合。

3. 输出方块集合的集合大小，结束。

我原先觉得这个问题应该先考虑表面再填充内部，后来发现这个方法好像不需要填充

 

下一个问题是复杂度，因为我们的目的不是非要找四面体而是找出一个凸的部分即可，现在分成基本的四面体的方法分的是否有些碎呢

[yhz012]

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

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

求环不难，举例来说现在你有集合S为在z面上的所有截取线段集合

circleList = []
while not S[i].isEmpty():
  circle = []
  a, b = S[i].pop()
  circle = circle + [a, b]
  c, d = None, None
  while c != a and d != a:
    for line in S[i]:
      c, d = line
      if c == b:
        S[i] = S[i] - {line}
        circle = circle + [d]
        b = c
      elif d == b:
        S[i] = S[i] - {line}
        circle = circle + [c]
        b = d
  circleList = circleList + [circle]

唯一可能出现的问题是有可能存在类似于“8”这样的环，不过这个在之后再判定一下就好了

四月 8, 2020，由yhz012修改

[Mr.K 018]

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

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

 

7 分钟前, yhz012 说道:

求环不难，举例来说现在你有集合S为在z面上的所有截取线段集合

circleList = []
while not S[i].isEmpty():
  circle = []
  a, b = S[i].pop()
  circle = circle + [a, b]
  c, d = None, None
  while c != a and d != a:
    for line in S[i]:
      c, d = line
      if c == b:
        S = S - {line}
        circle = circle + [d]
        b = c
      elif d == b:
        S = S - {line}
        circle = circle + [c]
        b = d
  circleList = circleList + [circle]

唯一可能出现的问题是有可能存在类似于“8”这样的环，不过这个在之后再判定一下就好了

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

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

[yhz012]

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

这个方法我觉得可行，总结一下大概的思路：

1. 将STL中的几何体三角化，分割成一个四面体集；

2. 维护一个放置方块集（初始为空），对四面体集的每一个元素：

2.1 确定要判定的四面体涉及哪些方块（可以通过x,y,z三个轴的最小值、最大值来限定）；

2.2 对每个上一步中得出要考虑的方块，进行求交运算，若相交则入方块集合。

3. 输出方块集合的集合大小，结束。

我原先觉得这个问题应该先考虑表面再填充内部，后来发现这个方法好像不需要填充

 

下一个问题是复杂度，因为我们的目的不是非要找四面体而是找出一个凸的部分即可，现在分成基本的四面体的方法分的是否有些碎呢

我也在担心这个问题，但是我需要有比较方便的方法判定一个多面体是凸的

当然也有类似地暴力的分割方案，就是像上面说的对z轴（或者x轴y轴，反正选一个）进行切片，切片的坐标在所有输入的z坐标

然后根据该z坐标相邻的三角面的情况进行判断，类似于下图的3D版，不过感觉分情况讨论会有点痛苦……

 

  

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

 

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

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

是的，我是假设了这个几何体是单连通的……

如果是多联通情况，大概是真的要求法向了……

如果确定是单连通，那么即使是大圈套小圈也能确定最外面的圈内一定是放方块，然后里面一层是不放，再里面是放，以此类推

如果是多联通，我的感觉是也会一样的效果，但是我需要仔细考虑下

四月 8, 2020，由yhz012修改

[inuisanaa]

这真的和mc有关系吗，每个字都看得懂，连起来就看不懂了

[随性而为]

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，由随性而为修改

[yhz012]

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

如果是这样的话，我在考虑是不是不用知道环形图形反而方便一些，计算出每个y-z解析式，然后对每个y求出z1，z2……，取 i>=min(z1，z2……)&& i<=max(z1，z2……),然后看(x,y,i)是否在雕塑内简单一些，不过这个太暴力了，渣渣只能想到这么做了……，而且我也不知道如何判断点是不是在封闭空间内

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

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

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

 

 

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

四月 8, 2020，由yhz012修改

[Mr.K 018]

12 分钟前, inuisanaa 说道:

这真的和mc有关系吗，每个字都看得懂，连起来就看不懂了

编程题一般都是题文无关（笑