# How to find overlap between two convex hulls,along with the overlap area

I have two boundaries of two planar polygons , say,B1 and B2 of polygons P1 and P2(with m and n points in Boundaries B1 and B2). I want to find out if the Polygons overlap or not.If they overlap,then the area(approx) covered by the common region.

Is there any way to do this.

Thanks, Harsha.

-

How to find overlap between two convex hulls

I want to find out if the Polygons overlap or not

Convex hulls are convex, so you can use a convex polygon collision detection algorithm.

http://content.gpwiki.org/index.php/Polygon_Collision#Separating_Axis

If they overlap,then the area(approx) covered by the common region.

You can find the intersection polygon

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

Then find its area

http://www.mathwords.com/a/area_convex_polygon.htm

-
Thanks .That really Hepled.I used GPC library ...... –  Harsha May 20 '13 at 9:22

This is partial answer. I assume you are dealing with convex polygons. Then you could put all your vertices in a matrix ($M_1$ for $P_1$, $M_2$ for $P_2$). Then for the convex hull to overlap you would need that $M_1 \bar{x}$=$M_2 \bar{y}$ has a solution, where $\bar{x}=(x_1,...,x_m)$ and $\bar{y}=(y_1,...,y_n)$, $x_i,y_i\geq0$ and $\sum_{i=1}^mx_i=1$, and $\sum_{i=1}^ny_i=1$. Then if you can perform the same row operations on both matrices such that one row becomes negative in one matrix and the corresponding row positive in the other matrix then you have shown that the polytopes do not overlap. This is equivalent to performing a change of basis to put one polytope on the positive side of a hyperplane and the other on the negative side of the same hyperplane.

-

Conceptually, if you don't care about speed, take an algorithm that decomposes $N$-gons into $N-2$ "disjoint" (modulo common edges) triangles -- for convex polygons this is trivial -- and then, for each pair of triangles (one from $P1$ and one from $P2$), apply an algorithm that computes the overlap, if any, of two triangles. This shows the complexity is at worst $O(mn)$, at least in the convex case. One question might be, how does this compare with the approaches in the answers already given by meij and Stephen Sturgeon?

Added later: It occurs to me I might be under a misimpression as to how the polygons are being specified. I am assuming that to "have the boundaries" means, in effect, that you have a listing of the vertices as you go around the boundary. If it means something else, then what I described above requires a prefatory step that produces such a list. (Also, if the OP really wants the overlaps of the convex hulls of $P1$ and $P2$, then lists of the hulls' vertices need to be ascertained.)

-

If you care about speed, then there is a linear-time algorithm specifically tuned to intersecting two convex polygons, described in the book, Computational Geometry in C, with downloadable code.

(I took the above snapshot from an illegal scan of the book!)

-
does the linear time require the vertices to have already been sorted? –  meij May 14 '13 at 18:36
@meij: Yes! But of course that is the usual result of the convex hull computation. –  Joseph O'Rourke May 14 '13 at 18:46