Help

paulmcvn · Post by **paulmcvn** » Fri Feb 04, 2005 10:59 am

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

sumankar · Post by **sumankar** » Fri Feb 04, 2005 2:32 pm

Hi,

Naive method:

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

Regards,
Suman.

ranjit · Post by **ranjit** » Fri Feb 04, 2005 3:33 pm

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

paulmcvn · Post by **paulmcvn** » Fri Feb 04, 2005 4:38 pm

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?