多边形相交面积算法 [英] Algorithm for area of polygons intersection

问题描述

我有两个简单的多边形，用顶点列表定义.

我需要计算它们相交的面积.我需要一个算法来做到这一点

解决方案

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

假设:多边形是凸的.(这些适用于凸多边形.)您可以查看此

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

凸多边形的面积

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

<代码> |x1 y1 ||x2 y2 ||x3 y3 |面积= (1/2)* |.. .. ||.. .. ||xn y ||x1 y1 |= (1/2)[(x1*y2+x2*y3+...xn*y1)- (y1*x2+y2*x3+...+yn*x1)]

这些是您必须执行的步骤才能解决问题.希望有帮助.

I have two simple polygons, defined wlith the lists of vertices.

I need to compute the area of their intersection. I need an algorithm to do that

解决方案

Algorithm to decide whether two polygons intersect.

Assumption: The polygons are convex. (These are applicable for convex polygons.) You can check this link for further information.

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.

Note: This SO question described this part wonderfully. I have used this part from this question

The area covered by common region (approx) if overlap

The algorithm works simply this way

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.

For more detail visit this links

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

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

Area of Convex Polygon

The coordinates (x1, y1), (x2, y2), (x3, y3), . . . , (xn, yn) of a convex polygon are arranged in the "determinant" below. The coordinates must be taken in counterclockwise order around the polygon, beginning and ending at the same point.

             | 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)]

These are the steps you have to perform to get the problem solved. hope it helps.

这篇关于多边形相交面积算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！