Maths: Perpendicular lines

[ne555]

Cross product ?
No need for triangulation, and it works with concave polygons

[Kyon]

Does it also work for complex polygons?
(Polygons that can have overlapping sides.)

[ne555]

I don't see why not. As long as the boundary is C⁰ there should not be problem.
For holes, you will need to threat them separately.

[hamsterman]

Could you explain (link to) how that works?

[ne555]

You've got a triangle defined by 3 points in the plane (A, B, C)
Compute the signed area with cross product:

(B-A) x (C-A) = 
| i j k |
| dx dy 0 |= dx*ey-dy*ex
| ex ey 0 |

= 2*signed Area Triangle

To compute the area of an arbitrary polygon:
_Pick a point that you know is inside the polygon. By instance a vertex.
_Compute the signed area against every segment
_Sum all the areas

Magic
(a variant will allow to know if a point is inside the polygon)

Edit: Yep, it seems that the reference point could be anyone.

[hamsterman]

Oh. That's pretty smart.
Though why does the point have to be inside the polygon? It seems to work fine either way..