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.