在我目前的项目中，我需要计算三角形的交叉区域和无限网格中的单位正方形 .
对于每个三角形（由三对浮点数给出），我需要知道它与其相交的每个方格共有的区域（在区间 (0,1] 中） .
现在我将两者（三角形和正方形）转换为多边形并使用Sutherland-Hodgman polygon clipping来计算交叉多边形，然后我将其用于calculate its area .
现在，这种方法在我的应用程序中显示出性能瓶颈 . 我想更专业（分析）算法会更快 . 是否有针对此问题的标准解决方案，或者您有任何想法吗？我只需要区域，而不是交叉点的形状 .
4 回答
你的多边形是凸的 . 凸多边形的算法比一般多快 . 我've used O' Rourke算法成功（code from his book here，我相信存在很好的描述） . 请注意，某些值可能会为您的方块预先计算 .
如果您的多边形不总是相交，那么您可能首先检查与分离轴方法相交的事实 .
尝试Liang-Barski algorithm用于按平方剪切每个三角形边的另一个选项 .
Edit: 您可以使用algorthm of Amanatides and Woo（example in grid traversal section here）快速找到三角形边的所有交点
为了以高性能处理此任务，我建议对Vatti线扫描剪辑进行一些修改 . http://en.wikipedia.org/wiki/Vatti_clipping_algorithm
从三角形的最小Y顶点步进，可以执行以下步骤：
按Y坐标排序顶点
步高Y到MIN（nextVertex.Y，nextGridBottom）
计算网格与边缘的交点 .
收集当前的梯形
从步骤2开始重复，直到具有最高Y坐标的顶点 .
如果需要，按X坐标分割梯形 .
这里是X方向的梯形化的例子http://www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/PolyPart/polyPartition.htm
它说明了线扫描算法的主要思想 . 祝好运 .
你没有提到你想要的精度 . 如果你正在寻找一种分析方法，请忽略这个答案，但如果你只是想做抗锯齿，我建议由Kiia Kallio做一个scanline edge-flag algorithm . 我已经使用了几次，它非常快，可以设置非常高的精度 . 如果你有兴趣，我有一个java实现 .
您可以利用常规的正方形图案 .
我假设这是一个瓶颈的原因是因为你必须等待你的算法找到所有正方形与任何三角形相交并计算所有交叉区域 . 因此，我们将计算所有区域，但是为了从最少的计算中获取最多信息，每个三角形都会批量计算 .
首先，正如其他人所解释的，对于三角形的每个边，您可以找到边穿过的正方形序列，以及它穿过正方形的每个垂直或水平边的点 .
对所有三个方面执行此操作，保留您遇到的所有方块的列表，但每个方块只保留一个副本 . 将正方形存储在多个列表中可能很有用，这样给定行上的所有正方形都保存在同一列表中 .
当您找到所有正方形时，三角形的边缘通过，如果其中两个正方形位于同一行，则这两个之间的任何不在列表中的正方形都完全在三角形内，因此每个正方形的100％是覆盖 .
对于其他正方形，面积的计算可以取决于三角形在正方形（0,1,2或3）中的顶点数量，以及三角形边缘与正方形边相交的位置 . 您可以在一些铅笔纸图纸中总结所有案例，并为每个案例进行计算 . 例如，当三角形边缘与正方形的两侧交叉时，正方形的一个角落在边缘的“外侧”侧，该角落是一个小角度的一个角，由较大的边缘“切断”三角形;使用正方形边上的交点来计算小三角形的面积，并从正方形区域中扣除它 . 如果两个点而不是一个是“外部”，则有一个梯形，其两个基本长度从交点出发，其高度为正方形的宽度;从广场上扣除它的面积 . 如果三个点在外面，则扣除正方形的整个区域，然后添加小区域三角形 .
正方形内部的大三角形的一个顶点，该角度外的正方形的三个角：从剩余的角线到三角形的顶点绘制一条线，因此您有两个小三角形，扣除整个正方形并添加这些三角形的区域 . 角度外的正方形的两个角，向顶点绘制线以获得三个小三角形等 .
我正在措辞这样你总是假设你从正方形的整个区域开始，并根据三角形的边缘与正方形相交的方式将面积减少一些 . 这样，在三角形的边缘与正方形相交两次以上的情况下 - 例如，一条边切割正方形的一个角，另一条边穿过另一个角，您可以直接扣除被切割的区域 . 第一个边缘，然后扣除第二个边缘切断的区域 .
这将是相当多的特殊情况，尽管你可以利用对称性;例如，您不必编写四次“在一个角落切掉一个三角形”的完整计算 .
你会编写更多的代码，而不是你把一个人的凸多边形库从架子上拿下来，你会想要测试它的生活日光，以确保你不会忘记编码任何情况，但是一旦你让它工作，它不应该花费太多的努力来使它合理快速 .