How to find the length of the union of Isosceles triangles

Question

I am given N number of right angles triangles all of which are also Isosceles triangles. For each triangle, I am told where they start on a number line and where they end on a number line with end being strictly greater than start. The set forms a non-degenerate polygon from the union of the triangles in the set. Some triangles however may be contained in others (start[x] <= start[y] and end[x] >= end[y] where x and y are two distinct triangles) as shown below

The Picture above better explains the situation. There are three distinct triangles in the example. 1st is 0 - 5, 2nd is 3 - 9, and 3rd is 4 - 6; I am required to determine the length of the border of the polygon, shown above in bold.

My Approach: My variable is length which is initially = 0

• I sort the set of triangles from the lowest starting point to the largest starting point
• I remove all triangles whose start and end are contained in another triangle from the same set. For example in the picture above, i'd remove the last triangle 4 to 6

• Then for each start and end in the remaining set I'd do the following:

• I calculate the sum of each side, T, of the triangle as: (halfBase / Cos(45)) * 2; where halfbase = |(finish - start)| / 2, and add T to total length

• Then I search for the first previous triangle X whose finish > than this present triangles start and whose finish is < this present triangles finish.
• lastly, I deduct T of the triangle formed as a result of the union between this present triangle and triangle X (shown above as 3 to 5)

This approach works fine and gives me the correct answer every time. But I feel I am doing more work than is actually necessary to compute this length. I need help deriving a better algorithm to help compute this length.

preciate the help.

Answer 1

First of all note that your polygonal chain can be reduced to two line segments being legs of isosceles right triangle covering the whole given set.

The only requirement for such generalisation to be possible is the triangles actually make a connected union. If they don't, however, the upper border is not well defined (what happens inside the hole?)

so I assume we can treat this case either as non-existing or as an error.

Luckily this can be easily detected during building the union.

Each triangle is identified by an interval defining its base, and the union is equivalent to a triangle defined by the union of those intervals. There are many implementations of finding a union of intervals, some of them can be found at StackOverflow just by searching for 'union of intervals'.

Here is a possible algorithm:

1. sort the list of intervals by ascending start value
2. pick the first interval (one with minimal start value), and remove it from the set; this will be the initial approximation of the union – its start and end values define an interval, which we hopefully will expand in following steps
3. while there are other intervals in the list
   1. pick the first interval not tested yet
   2. if it overlaps the current union, it either is contained in the union or it extends past the current end; keep or extend the union appropriately;
   3. OTOH if it doesn't ovelap the union, no other triangle does, hence the union is not connected → break the processing with an error.

After exhausting the list the upper bound of the 'generalised triangle' is simply $\sqrt 2$ times the union length.

However, if you want to solve the disconnected case as a sum of connected subproblems, you can just start building a new union of intervals each time you encounter the 3.3 case, then apply the above multiplier to a sum of lengths of all intervals unions.