Apple Interview Question
Developer Program EngineersAs a graphics guy with good computation geometry & rasterization knowledge I'm not clear on what the question wants; but here's how I would do the following (if I didn't have to use triangulation) :
*Run line-sweep algorithm on the polygon [ex: top -> bottom] (see wikipedia ) with an active edge list
*Stop at every intersection OR vertex and compute the area described by the sum of the area for the parallelogram generated by the cut from OldY to Y.
If you already have a triangulation; it seems like a pretty silly question since the problem devolves to computing the area of a set of triangles. And that's nothing less than the 0.5*determinant of the matrix populated with the row-vectors produced by taking any 2 pair of points for the triangle (think cross product)
we can divide the polygon into triangle.
- anonymous October 06, 2010consider a f(n)
if n==3,it is just a triangle,just return the area of S(n)
if (n>3),for each two edges adjacent ,we can create a triangle with it,
then we can get n/2 triangles and another polygon with n-(n/2)*2+n/2 edges.
then we can use recursion