多边形相交区域的算法

Question

<分区>

Answer 1

判断两个多边形是否相交的算法。

假设:多边形是凸的。 (这些适用于凸多边形。) 你可以查看这个link了解更多信息。

To be able to decide whether two convex polygons are intersecting (touching each other) we can use the Separating Axis Theorem. Essentially:

• If two convex polygons are not intersecting, there exists a line that passes between them.
• Such a line only exists if one of the sides of one of the polygons forms such a line.

The first statement is easy. Since the polygons are both convex, you'll be able to draw a line with one polygon on one side and the other polygon on the other side unless they are intersecting. The second is slightly less intuitive. Look at figure 1. Unless the closest sided of the polygons are parallel to each other, the point where they get closest to each other is the point where a corner of one polygon gets closest to a side of the other polygon. This side will then form a separating axis between the polygons. If the sides are parallel, they both are separating axes.

So how does this concretely help us decide whether polygon A and B intersect? Well, we just go over each side of each polygon and check whether it forms a separating axis. To do this we'll be using some basic vector math to squash all the points of both polygons onto a line that is perpendicular to the potential separating line (see figure 2). Now the whole problem is conveniently 1-dimensional. We can determine a region in which the points for each polygon lie, and this line is a separating axis if these regions do not overlap.

If, after checking each line from both polygons, no separating axis was found, it has been proven that the polygons intersect and something has to be done about it.

注意:这个SO问题很好地描述了这部分。我已经使用了这部分 question

重叠时公共(public)区域覆盖的面积(大约)

算法就是这样工作的

The algorithm begins with an input list of all vertices in the subject polygon. Next, one side of the clip polygon is extended infinitely in both directions, and the path of the subject polygon is traversed. Vertices from the input list are inserted into an output list if they lie on the visible side of the extended clip polygon line, and new vertices are added to the output list where the subject polygon path crosses the extended clip polygon line.

有关更多详细信息，请访问此链接

• http://gamedevelopment.tutsplus.com/tutorials/understanding-sutherland-hodgman-clipping-for-physics-engines--gamedev-11917

• https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm

凸多边形的面积

坐标(x1, y1), (x2, y2), (x3, y3), . . . , (xn, yn) 一个凸多边形排列在下面的行列式中。坐标必须围绕多边形按逆时针顺序获取，起点和终点在同一点。

             | x1 y1 |
             | x2 y2 |
             | x3 y3 |
Area= (1/2)* | .. .. |
             | .. .. |
             | xn yn |
             | x1 y1 |

    = (1/2)[(x1*y2+x2*y3+...xn*y1)- (y1*x2+y2*x3+...+yn*x1)]

这些是解决问题必须执行的步骤。希望对您有所帮助。