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

[yhz012]

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

 

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

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

四月 8, 2020，由yhz012修改

[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修改

[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修改

[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修改

[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修改

[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修改

[yhz012]

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

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

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

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

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

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

四月 8, 2020，由yhz012修改