所以,今天我一直在努力解决一个坦率的现在真气的问题.
给定平面上三角形的一组顶点(仅3个点,6个自由参数),我需要计算该三角形与{0,0}和{1,1}定义的单位平方的交点区域.(我之所以选择这个,是因为2D中的任何方形都可以转换为此方,同一个转换可以移动3个顶点).
所以,现在问题简化为只有6个参数,3个点......我认为这个问题很短,我愿意编写完整的解决方案/找到完整的解决方案.
(如果可能的话,我想在GPU上运行超过200万个三角形,每个<0.5秒.至于需要简化/没有数据结构/库)
就我对解决方案的尝试而言,我已经...列出了我想出的方法,其中没有一个看起来很快或者......特定于好的情况(太笼统).
选项1:找到封闭的多边形,它可以是从三角形到6格的任何东西.通过在我发现的O(n)时间算法中使用一些凸多边形的交叉来做到这一点.然后我会按CW或CCw顺序对这些交点(新顶点,最多7个O(n log n))进行排序,这样我就可以在点上运行一个简单的区域算法(基于格林函数)( O(n)再次).对于与另一个m-gon相交的任意凸n-gon,这是我能提供的最快速度.但是......我的问题绝对不是那么复杂,它是一个特例,所以它应该有一个更好的解决方案......
选项2:因为我知道它是一个三角形和单位正方形,所以我可以用更强力的方式找到交叉点列表(而不是使用一些算法......坦率地说实施起来有点令人沮丧,如上所列)
只有19分要检查.4个点是三角形内的正方形角.正方形内有三角三角形.然后对于三角形的每条线,每条线将与正方形相交4条线(例如,y = 0,y = 1,x = 0,x = 1条线).那是另外12点.所以,12 + 3 + 4 = 19点检查.一旦我有了这个交叉点,最多6个,最少3个点,我可以跟进我能想到的两种方法中的一种.
2a:通过增加x值对它们进行排序,然后简单地将形状分解为其子三角形/ 4-gon形状,每个形状都有一个基于限制顶部和底部线的简单公式.总结一下这些地区.
或2b:再以某种循环方式对交点进行排序,然后根据绿色函数计算区域.
不幸的是,就我所知,这仍然是最复杂的.为了找到交点,我可以开始分解所有的情况,因为我知道它的正方形只有0和1,这使得数学删除了一些条款..但它不一定简单.
选项3:根据各种条件开始分离问题.例如.正方形内的0,1,2或3个三角形点.然后针对每种情况,遍历所有可能数量的交叉点,然后针对每个多边形形状的情况,唯一地记下区域解决方案.
选项4:一些具有重载步骤功能的配方.这是我最想要的那个,我怀疑它会有点......很大,但也许我很乐观这是可能的,并且一旦我有了公式,这将是计算最快的运行时间.
---总的来说,我知道可以使用一些高级库(例如限幅器)来解决它.我还意识到,在使用各种数据结构(链表,然后对其进行排序)时,编写通用解决方案并不是那么难.如果我只需要这样做几次,所有这些情况都可以.但是,因为我需要将它作为一个图像处理步骤运行,每张图像大约> 9*1024*1024次,我正在拍摄图像...让我说1 fps(技术上我会想要推动这个速度尽可能快地上升,但是下限是1秒来计算这些三角形交叉区域问题中的900万个).这在CPU上可能是不可能的,这很好,我可能最终会在Cuda中实现它,但我确实想要在这个问题上推动速度限制.
编辑:所以,我最终选择了2b.由于可能只有19个交叉点,其中最多6个将定义形状,我首先找到3到6个顶点.然后我按循环(CCW)顺序对它们进行排序.然后我通过计算该多边形的面积来找到该区域.
这是我写的测试代码(这是为了Igor,但应该是可读的伪代码)不幸的是它有点长啰嗦,但是......我认为除了我糟糕的排序算法(不应该超过20掉期) ,所以编写更好的排序没有那么多开销)...除了排序之外,我认为我不能让它更快.尽管如此,我对选择此选项时可能有的任何建议或疏忽持开放态度.
function calculateAreaUnitSquare(xPos, yPos)
wave xPos
wave yPos
// First, make array of destination. Only 7 possible results at most for this geometry.
Make/o/N=(7) outputVertexX = NaN
Make/o/N=(7) outputVertexY = NaN
variable pointsfound = 0
// Check 4 corners of square
// Do this …