Intersection area of two polygons

11

How to calculate the area of the 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.

    
asked by anonymous 04.06.2016 / 01:11

3 answers

6

I finally managed to calculate.

Given

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 has the coordinates of the polygon.

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
  }
    
06.06.2016 / 02:39
7

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 Monte Carlo Method, random points are generated in an area of which you already know the area. Then determine the proportion of points that occur in the area you want to calculate, in this case, the intersection of the polygons. This ratio multiplied by the area in which the points were generated, returns the desired area.

Of course there should be an algorithm that computes the exact area, but if an approximation is enough for you, you are here.

    
04.06.2016 / 16:57
6

According to the link below, you can access the Master's Dissertation from Sergio Lifschitz that deals with this, and I'll use an example to explain what you can do.

Master's Dissertation - Sergio Lifschitz

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

WhatyouneedtodowiththealgorithminquestionisFindintersectioncoordinates,andbyexclusion,getonlytheresultingpolygonseverythingwasasinglefigure)tocalculatethetotalarea.

Thecoordinatesofintersectionsbetweenpolygonscanbefoundbycalculatingtheintersectionoftwolines,whichissimpleonceyouhavegenerated.

The equation of the area of a triangle is:

A = (b x h) / 2

Where:

A = 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 I have helped, or at least presented a path. Good luck!

    
04.06.2016 / 03:26