Efficient Computation of Complex Polygon Areas?

[SonyAD]

Hello. Nice to be here.

If I may, I would like to inquire about the enclosed area of complex polygons. Is there a general formula that will work for these and reduce/cancel out partly for simple/non self-intersecting polygons for a correct enclosed area of theirs as well?

I need to compute the area of a hexagon that may or may not be complex, depending on the circumstances. I don't know whether it is going to be complex or not beforehand and I wouldn't want to test for that because I want a simple and fast algebraic solution of the 'inside in' enclosed area of the polygon. I only really care about the 'inside in' enclosed areas but anything would work better than the 'inside in' - 'inside out' areas I can work out by triangulating the polygon.

For example, when triangulating, there is one possible case when the hexagon degenerates into something akin to the symbol for radiation and then the core will have positive area and the leafs negative areas. I don't know whether the 'inside out' regions will overlap between themselves or the 'inside in' region. If they overlap with the 'inside in' region then they seem to also have positive area, which stacks.

I tried finding a formula for the area of a quadrilateral that will work regardless whether it is complex in the hope of breaking the hexagon up into two quadrilaterals and computing its true area as the sum of theirs.

No luck.

I could use some advice.

This is the last or penultimate roadblock to something potentially very big. :)

 

[SonyAD]

Ok, so this is what I mean:

[PLAIN]http://img337.imageshack.us/img337/2050/hexagon2.png

By triangulating the hexagon I can compute its area:

A_{123} + A_{134} + A_{145} + A_{156}
=
\frac{x_{3}(y_{2}-y_{4}) +<br /> x_{4}(y_{3}-y_{5}) +<br /> x_{5}(y_{4}-y_{6}) +<br /> x_{6}(y_{5}-y_{1}) +<br /> x_{1}(y_{6}-y_{2}) +<br /> x_{2}(y_{1}-y_{3})}{2}

But for the complex hexagon the area yielded is the green minus the red. I need the green area...

What can I do?

Should I try to find a formula that works out the area of simple and complex quadrilaterals, if there is such a thing, and break the hexagon into 2 quadrilaterals then add their areas?

 

[SonyAD]

Ok then.

[PLAIN]http://img444.imageshack.us/img444/6765/patrulater.png

Ok, so it occurred to me that I can compute the area of any quadrilateral in this fashion:

\frac{A_{512} + A_{523} + A_{534} + A_{541} + | A_{512} | + | A_{523} | + | A_{534} | + | A_{541} | }{2}

I don't know whether this can be used to quadulate more complicated self-intersecting polygons for purposes of computing the area.

This will nicely cancel out the red patches and will also work for complex quads.

Which, alas, brings me to my next question:

How would I go about computing P₅ (5.x & 5.y) ?

As can be discerned from the figure, I can't just very well barge on ahead and compute the intersection [P₁,P₃] ∩ [P₂,P₄].

I need to compute 5.x and 5.y as a function of all the 4 vertices themselves, not anyone intersection of sides and/or diagonals.

Any suggestions will be appreciated. Thanks.