Quirky problem: calculating the area of an irregular shape programmatically

[MGMorden]

This is more of a math/programming question.

I'm trying to rewrite a certain legacy system we have that I don't have access to the source code. It's an OLD COBOL program (20+ years old) that calculates building information. The floor area of the building was specified in a weird way though.

For rectangular shapes, it was simple: 50x25 would naturally calculate to 1250 square feet. However, for irregular shapes it took in input in a strange fashion. You told it the up and down movements on how to draw the shape, and it then calculated the area. U for up, D for down, R for right, L for left, followed by a digit. So for example you could have:

U10R5D5R10U10R5D15L8U1L4D1L8

This draws a fairly odd shape. Now, by hand, finding the area of this thing is easy. I draw it out, it breaks down into 5 rectangles of different size, and I calculate the area of each and add them all together (the above example is 171 square feet). Problem is, for the life of me I can't figure out any way to solve that problem algorithmically without drawing out the shape.

Am I missing some obviously simple solution here, or is it as complex as it looks?

Thanks.

 

[Cogman]

you'll probably want something along the lines of a tessellation algorithm. That will break down your polygon into triangles, then you can calculate the area for each triangle and be done with it.

(You will have to plot out all of the points)

 

[CycloWizard]

Cogman's method will work. You can break it into triangles using Delaunay triangulation, then simply sum the area of the triangles. There are other ways that are much simpler that may work, depending on the complexity of your shape. Will the portions always be rectangular? Will the input be given in the same format as it was for the old program?

 

[MGMorden]

Yes, the portions will always be rectangular, and the input will always be given in the same format. EVENTUALLY I may look at converting it to use an XML based drawing in which case I'll convert the old data, but for now I'm hoping to do this is smaller stages.

 

[KIAman]

If thats the case, you can make a simple algorithm that does 4 things. (lots of psuedocode)

1. Split input into pair coordinates
- U10R5
- D5R10
- etc.

2. Verify that the shape is enclosed
- add up all U and subtract out all D = 0
- add up all R and subtract out all L = 0

3. Determine direction of coordinates
- if first pair has U, then U = positive, D = negative
- else if first pair has D, then D = positive, U = negative
- if first pair has R, then R = positive, L = negative
- else if first pair has L, then L = positive, R = negative

4. Multiply coordinates along with their sign and add them up together
- reference point is the beginning coordinate set
- U10R5, store U=10 10x5 = 50 AREA
- D5R10, U-5 = 5x10 = 50 AREA store U = 5
- U10R5, U+10 = 15x5 = 75 AREA, store U = 15
- D15L8, U-15 = 0x-8 = 0 AREA, store U = 0
- U1L4, U+1 = 1x-4 = -4 AREA, store U = 1
- D1L8, U-1 = 0x8 = 0 AREA

Total AREA = 50+50+75+0-4+0 = 171

Testing this shape backwards, the input is as follows. D15L8,U1,L4,D1,L8,U10,R5,D5,R10,U10,R5

step2: U-D = 0, R-L = 0
step3: D = positive, U = negative, L = positive, R = negative
step4:
15x8 = 120 AREA store D = 15
14x4 = 56 AREA store D = 14
15x8 = 120 AREA store D = 15
5x-5 = -25 AREA store D = 5
10x-10 = -100 AREA store D = 10
0x5 = 0 AREA

Total AREA = 120+56+120-25-100-0 = 171

 

[MGMorden]

Thanks a million KIA. That's basically what I was looking for.