Area of intersection of two polygons

Question

How to calculate the area of intersection between two polygons? For example:

a = matrix(c(0 ,0 ,2 ,0 ,2 ,2 ,0 , 2, 0, 0), byrow = T, ncol = 2)
b = matrix(c(.5, 0 ,1 , 1, 1.5, 0, .5, 0), ncol = 2, byrow = T)

The first column represents the x axis and the second the y axis, the polygon is closed.

Answer 1

You can get an approximation using Monte Carlo method:

a = matrix(c(0 ,0 ,2 ,0 ,2 ,2 ,0 , 2, 0, 0), byrow = T, ncol = 2)
b = matrix(c(.5, 0 ,1 , 1, 1.5, 0, .5, 0), ncol = 2, byrow = T)

library(sp)

interseccao <- function(a,b, n = 100000){
  xmin <- min(a[,1], b[,1])
  xmax <- max(a[,1], b[,1])
  ymin <- min(a[,2], b[,2])
  ymax <- max(a[,2], b[,2])

  x_aleatorio <- runif(n, min = xmin, max = xmax)
  y_aleatorio <- runif(n, min = ymin, max = ymax)

  pontos_em_a <- point.in.polygon(x_aleatorio, y_aleatorio, pol.x = a[,1], pol.y = a[,2])
  pontos_em_b <- point.in.polygon(x_aleatorio, y_aleatorio, pol.x = b[,1], pol.y = b[,2])

  proporcao_intersec <- mean(pontos_em_a == 1 & pontos_em_b == 1)

  area_intersec <- (xmax-xmin)*(ymax - ymin)*proporcao_intersec

  return(area_intersec)
}

interseccao(a,b)
[1] 0.50368

In the Monte Carlo Method, random dots are generated in an area from which you already know the area. Then we determine the proportion of points that occur in the area you want to calculate, in this case, at the intersection of polygons. This proportion multiplied by the area in which the points were generated, returns the desired area.

Of course there must be an algorithm that calculates the exact area, but if an approximation is enough for you, it’s here.

Answer 2

Finally I was able to calculate.

Datum

a1 = matrix(c(0 ,0 ,2 ,0 ,2 ,2 ,0 , 2, 0, 0), byrow = T, ncol = 2)
b1 = matrix(c(.5, 0 ,1 , 1, 1.5, 0, .5, 0), ncol = 2, byrow = T)

Another example

a2 = matrix(c(0,0,2,0,2,2,0,2), ncol = 2, byrow = T)
b2 = matrix(c(1.5,.5,3,0,2.25,2), ncol = 2, byrow = T)

Intersection

library(sp)
interseccao <- function(a,b){
  a1 = as(a, "gpc.poly")
  b1 = as(b, "gpc.poly")
  res = intersect(a1, b1)
  res = as(res, "matrix")
  res
}

Applying the function interseccao we have the polygon coordinates.

Area

The function that calculates the area of any convex polygon is given by the Shoelace equation counterclockwise.

area_poligono = function(poligono){
  a = poligono[,1]
  b = poligono[,2]
  area1 = area2 = 0
  for(i in 1:length(a)){
    if(i < length(a)){ 
      area1 = area1 + (a[i]*b[i+1] - a[i+1]*b[i])
    }
    else{
      area2 = area2 + (a[i]*b[1] - a[1]*b[i])
    }
  }
  area = .5*(area1 + area2) 
  area
  }

Answer 3

As the link below, access master’s dissertation of Sergio Lifschitz which deals with it, and which I will use as an example to explain what you can do.

Master’s dissertation - Sergio Lifschitz

The figure below refers to Page 53, Figure [A3-2].

What you need to do with the algorithm in question is find the coordinates of the intersections, and by exclusion, be only with the resulting polygons (as if everything were a single figure) to calculate the total area.

As coordinates of intersections between polygons can be found through the calculation of the coordinates of the intersection of two lines, which is simple once you have generated the equation of each line (which is also simple) and this can be done with each set of four coordinates, a pair for each line.

For the calculation of the total area you need, can be done by means of triangles, by connecting the coordinates so that all divide the final figure as a whole into triangles, as I represented below:

SUGGESTION:

See that there being coincidental coordinates (exactly equal of the two polygons, you can consider them as one, and so, in the end you will get every coordinate of the complete figure.

Afterward, by the internal areas of the polygons (in the dissertation and in other publications there are indications of how to identify the inner part of the polygon), generate each triangle and calculate each area in the sequence.

The equation of area of a triangle is:

A = (b x h) / 2

Where:

To = triangle area

b = base of the triangle

h = triangle height

Just calculate the size of the base and the same for the height.

I hope to have helped, or at least presented a way. Good luck!