快速计算三角形和单位正方形的相交面积 [英] fast calculation of the intersection area of a triangle and the unit square

问题描述

在我当前的项目中，我需要计算无限网格中三角形和单位正方形的相交面积.

In my current project I need to calculate the intersection area of triangles and the unit squares in an infinite grid.

对于每个三角形(由三对浮点数给定)，我需要知道与每个正方形相交的面积(在区间(0,1]中).

For every triangle (given by three pairs of floating point numbers) I need to know the area (in the interval (0,1]) it has in common with every square it intersects.

现在，我将(三角形和正方形)都转换为多边形，并使用 Sutherland-Hodgman多边形裁剪计算交集多边形，然后将其用于计算其面积.

Right now I convert both (the triangle and the square) to polygons and use Sutherland-Hodgman polygon clipping to calculate the intersection polygon, which I then use to calculate its area.

现在，这种方法显示出我的应用程序中的性能瓶颈.我猜想更专业的(分析)算法会更快.是否有针对此问题的标准解决方案，或者您有任何想法?我只需要区域，而不需要交叉点的形状.

This approach now shows to be a performance bottleneck in my application. I guess a more specialized (analytical) algorithm would be much faster. Is there a standard solution for this problem, or do you have any idea? I only need the areas, not the shape of the intersections.

推荐答案

您可以利用正方形的常规图案.

You can take advantage of the regular pattern of squares.

我假设这是一个瓶颈，是因为您必须等待算法找到与任何三角形相交的所有平方并计算所有相交面积.因此，我们将对所有面积进行计算，但要为每个三角形分批进行计算，以便从最少的计算中获得最多的信息.

I'm assuming the reason this is a bottleneck is because you have to wait while your algorithm finds all squares intersecting any of the triangles and computes all the areas of intersection. So we'll compute all the areas, but in batches for each triangle in order to get the most information from the fewest calculations.

首先，正如其他人所解释的那样，对于三角形的每个边缘，您可以找到该边缘所经过的正方形的序列，以及与该正方形的每个垂直或水平边缘相交的点.

First, as explained by others, for each edge of the triangle, you can find the sequence of squares that edge passes through, as well as the points at which it crosses each vertical or horizontal edge of a square.

对所有三个面都执行此操作，保留您遇到的所有正方形的列表，但每个正方形仅保留一个副本.将正方形存储在多个列表中可能会很有用，以便将给定行上的所有正方形都保留在同一列表中.

Do this for all three sides, keeping a list of all the squares you encounter, but keep only one copy of each square. It may be useful to store the squares in multiple lists, so that all squares on a given row are all kept in the same list.

找到所有正方形后，三角形的边缘会通过，如果其中两个正方形在同一行上，则这两个不在列表中的正方形完全在三角形内，因此每个正方形的100％这些正方形被覆盖了.

When you've found all squares the triangle's edges pass through, if two of those squares were on the same row, any squares between those two that are not in the list are completely inside the triangle, so 100% of each of those squares is covered.

对于其他正方形，面积的计算可以取决于正方形中有多少个三角形的顶点(0、1、2或3)以及三角形的边缘与正方形的边相交的位置.您可以用几张铅笔画的图纸来总结所有案例，并为每个案例得出计算结果.例如，当三角形的边缘与正方形的两侧交叉时，正方形的一个角位于边缘的外侧"，则该角是小三角形的一个角，该三角形被较大的那个边缘切掉"三角形;使用正方形侧面的交点计算小三角形的面积，并从正方形的面积中扣除.如果有两个点而不是一个点在外部"，则您有一个梯形，该梯形的两个基本长度是从相交点处找到的，其高度是正方形的宽度；从广场上减去它的面积.如果外面有三个点，则减去正方形的整个面积，然后加上小三角形的面积.

For the other squares, the calculation of area can depend on how many vertices of the triangle are in the square (0, 1, 2, or 3) and where the edges of the triangle intersect the sides of the square. You can summarize all the cases in a few pencil-and-paper drawings, and come up with calculations for each one. For example, when an edge of triangle crosses two sides of the square, with one corner of the square on the "outside" side of the edge, that corner is one angle of a small triangle "cut off" by that edge of the larger triangle; use the points of intersection on the square's sides to compute the area of the small triangle and deduct it from the area of the square. If two points instead of one are "outside", you have a trapezoid whose two base lengths are found from the points of intersection, and whose height is the width of the square; deduct its area from the square. If three points are outside, deduct the entire area of the square and then add the area of the small triangle.

正方形内的大三角形的一个顶点，在该角度之外的正方形的三个角:从剩余的角到三角形的顶点画一条线，所以您有两个小三角形，减去整个正方形并添加这些三角形的地区.角外的正方形的两个角，在顶点处画线以获得三个小三角形，等等.

One vertex of the large triangle inside the square, three corners of the square outside that angle: draw a line from the remaining corner to the triangle's vertex, so you have two small triangles, deduct the entire square and add those triangles' areas. Two corners of the square outside the angle, draw lines to the vertex to get three small triangles, etc.

我要这样表述，以便您始终假设您从正方形的整个区域开始，并根据三角形的边缘与正方形的相交方式将区域减小一定量.这样，在三角形的边缘与正方形相交两次以上的情况下(例如，一条边缘切过正方形的一个角，而另一条边缘切过另一个角)，您只需扣除被三角形切去的面积即可.第一条边，然后减去第二条边切除的区域.

I'm phrasing this so that you always assume you start with the entire area of the square and reduce the area by some amount depending on how the edge of the triangle intersects the square. That way, in the case where the edges of the triangle intersect the square more than twice--such as one edge cuts across one corner of the square and another edge cuts across a different corner, you can just deduct the area cut off by the first edge, then deduct the area cut off by the second edge.

这将是相当多的特殊情况，尽管您可以利用对称性.例如，您不必为在一个角上切掉一个三角形"编写四次完整的计算.

This will be a considerable number of special cases, though you can take advantage of symmetry; for example, you don't have to write the complete calculation for "cut off a triangle in one corner" four times.

与仅仅将某人的凸多边形库从货架上拿走相比，您将编写更多的代码，并且您将要测试其中的活泼日光，以确保您不会忘记编写任何案例，但是一旦它开始工作，就不需花费太多精力就可以使其变得相当快.

You'll write a lot more code than if you just took someone's convex-polygon library off the shelf, and you will want to test the living daylights out of it to make sure you didn't forget to code any cases, but once you get it working, it shouldn't take much more effort to make it reasonably fast.

这篇关于快速计算三角形和单位正方形的相交面积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！