Algorithm for area of polygons intersection [closed]

Question

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

Answer 1

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.