Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have two general parallelograms each defined by four vertices (the corners) in $\mathbb R^2$. I want to find the intersecting area of them. How would I go about doing this? I've thought for awhile, but haven't come up with anything...

P.S. As I am going to use this for a computer program, I cannot accept graphical solutions.

Any help would be appreciated.

share|improve this question
1  
Create equations of sides of parallelogram, find the intersection points. –  hjpotter92 Feb 28 '13 at 9:02
1  
What if one of them is completely inside the other? –  l3utterfly Feb 28 '13 at 11:11
    
In my answer to this previous question I give lots of references to algorithms for computing the intersection of convex polygons. –  Rahul Feb 28 '13 at 20:08
    
None of the answers (including mine) take advantage of the fact that we are working with parallelograms, as opposed to more general polygons. There is probably a simpler algorithm for parallelograms. Not much simpler, maybe, but some. –  bubba Mar 1 '13 at 0:03

4 Answers 4

up vote 0 down vote accepted

Let $a_i$ $\ (1\leq i\leq4)$ be the vertices of the first parallelogram and $$e_i:\ s\mapsto(1-s)a_{i-1}+s a_i\qquad(0\le s\leq 1)$$ its edges, and similarly let $b_j$ $\ (1\leq j\leq4)$ be the vertices of the second parallelogram and $$f_j:\ t\mapsto(1-t)b_{j-1}+t b_j\qquad(0\le t\leq 1)$$ its edges. We assume that both parallelograms lie to the left of their edges.

Intersect each (infinite line) $e_i$ with each (infinite line) $f_j$ by solving a linear system for $s$ and $t$. Keep the found values $s_{ij}$, $t_{ij}$ if both lie in the interval $[0,1]$, otherwise throw them away. If you indeed have found an intersection point of the (actual) edge $e_i$ with the edge $f_j$ compute the sign $$\sigma_{ij}:={\rm sgn}(\dot e_i\wedge\dot f_j)\ ,$$ where $\dot e_i:=a_i-a_{i-1}$, and similarly for $\dot f_j$. If $\sigma_{ij}=1$ then you know that $e_i$ leaves at the parameter value $s=s_{ij}$ the $b$-parallelogram, and $f_j$ enters at the parameter value $t=t_{ij}$ the $a$-parallelogram. Conversely, if $\sigma_{ij}=-1$.

All in all you obtain for each $i$ a subinterval $I_i\subset [0,1]$ (which may be empty or all of $[0,1]$) during which the moving point on the edge $e_i$ is in the interior of the $b$-parallelogram, and similarly for each $j$ a subinterval $J_j\subset[0,1]$, during which the moving point on the edge $f_j$ is in the interior of the $a$-parallelogram. (The case where $I_i=\emptyset$ or $I_i=[0,1]$ requires special attention.)

Now comes the upshot: The intersection $W$ of the two parallelograms is a convex polygon whose sides are the parts $e_i'$ of the $e_i$ and $f_j'$ of the $f_j$ that lie in the respective other parallelogram. One now can use Green's area formula to compute the area of $W$ and obtains $$|W|=\int_{\partial W}\omega={1\over2}\left(\sum_i\int_{e_i'}\omega +\sum_j\int_{f_j'}\omega\right)\ .$$ Here we have used the abbreviation $$\omega:={1\over2}(x\ dy-y\ dx)\ .$$ (The integrals can be computed once and for all, and lead to simple quadratic expressions in terms of the data and the $s_{ij}$, $t_{ij}\ $.)

share|improve this answer

Alternatively, if you don't want to do any of the work yourself, search the web for "code that intersects two convex polygons". Intersecting general polygons is relatively tricky, but intersecting convex ones (like parallelograms) is much easier, so there's lots of code available. I can provide specific links if you tell me what language you prefer.

Joseph O'Rourke's page has code in both C and Java. The specific function is called convconv. If you like it, buy his book.

As with my other answer, if you actually want the area of the intersection, divide into triangles and add up their areas. Or, better, use an explicit formula for the area, as Rahul Narain suggested in the comment below. You can find the formula on this Wikipedia page.

share|improve this answer

Let's call your parallelograms $P_1$ and $P_2$ and let $A_2$ be the area of $P_2$.

You can do this:

1) Take the four sides of $P_1$ and make them infinitely long. This separates the plane in 9 disjoint regions, one of them being $P_1$ and the other 8 being of infinite area. Let's call $r_1,\ldots,r_8$ this eight regions.

2) Let $a_i$ be the area of $r_i\cap A_2$.

Then the area of $P_1\cap P_2$ is just $A_2-\sum_{i=0}^8a_i$.

share|improve this answer

This page has a function called Wm5IntrTriangle2Triangle2.cpp that calculates the intersection of two triangles. Basically, the idea is to split each edge of each triangle wherever it crosses an edge of the other triangle. Then you gather the right pieces of the split edges together to form a polygon. You can use exactly the same approach to intersect two parallelograms.

The result will be a convex polygon.

From your question, I can't tell if you want this polygon itself, or the area of the polygon. If you want the area, split the polygon into triangles, and add up the areas of the triangles. Splitting a convex polygon into triangles is easy -- just choose a point in the interior (like the average of the vertices), and join this point to each of the vertices.

share|improve this answer
    
There is actually a direct formula for the area of any polygon, convex or not. –  Rahul Feb 28 '13 at 20:10
    
@Rahul -- Yes, good point. No need for the triangle business. And the OP still hasn't told us whether he wants the area, anyway. –  bubba Feb 28 '13 at 23:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.