OJ Board

Input: a set of n triangles
(x1i, y1i), (x2i, y2i), (x3i, y3i)

Output: Area of union of the triangles

Sample Input:
2
0 0 2 0 1 2
0 0 2 0 1 1
Sample Output
2.0000

Hi,

Naive method:

1. Calculate polygon formed by union of all the triangles in the set.
2. Calculate area of the polygon.

Regards,
Suman.

Sumankar,
I didnt exactly understand your solution. The polygon might have some area that is not in any triangle too.

So you would have to be very careful in finding the various polygons first, something like finding the components in a graph where the nodes are represented by the traingles and the edges say whether the two nodes overlap. Find the area of each polygon ( connected component ) and sum them to get the answer.
I think the above solution is naive. Maybe we will get better ideas in this thread.

bye.

ps: I dont know what kind of help the creator of this thread wanted

Sorry

I'm not good in English so i think i should write as short as possible

There is an O(n^3) solution:

Sort x coordinates of (all end points of triangles and intersection points )

Then go through interval x[1]-x[2]; x[2]-x[3]; x[3]-x[4]; ....

For each interval, find intersection of triangles and the strips, they are trapezoids. Maintain the trapezoids such that they're all disjoint. So now it's easy to compute the area.

Could the above solution be improved?

Is there an O(n^2) solution? I've heard about topologically sweeping, arrangement, ... but i haven't understood them yet. Could anyone explain me?