This week's book giveaway is in the Big Data forum. We're giving away four copies of Elasticsearch in Action and have Radu Gheorghe & Matthew Lee Hinman on-line! See this thread for details.

Write a program that calcualtes the area covered by a closed path. The path is specified as a sequence of steps, each step describing the direction (East, West, North, or South) and the units in that direction. You can use command line arguments, standard input, or a file or input. ------------------------------------------------------ Example 1: Input:E2 N1 W2 S1 Output:2 _ _ |_ _| (starting point is bottom-left corner) ------------------------------------------------------ Example 2: Input:S3 E1 N1 E1 N1 E1 N1 W3 Output:6 _ _ _ | _| | _| |_| (starting point is top-left corner) ------------------------------------------------------ P.S. I forgot the name of the book that was full of such questions. It was something like 'graded programs'. Does anyone know?

Sorry if I seem overinquisitive, but just a few questions that come to mind: By "area covered" you mean the inside of the figure only, right? The path itself is not included? Can we assume that every path entered will be a closed figure? Can we assume that the figure splits the plane into exactly two sections (that is, that you can draw a line from any point inside to any other point without crossing any lines)? Should we write a program that can handle an arbitrarily long path, or are there any restrictions on the legal area that the path can cover (i.e. the path will fit onto an NxN grid, or there will be a maximum of N steps)?

Jignesh Malavia
Author
Ranch Hand

Joined: May 18, 2001
Posts: 81

posted

0

Sorry if I seem overinquisitive, but just a few questions that come to mind: No problem :-) By "area covered" you mean the inside of the figure only, right? The path itself is not included? Yes, the area inside the figure. I did not get the second part of your question. The path steps form the bounding edges of the figure. Can we assume that every path entered will be a closed figure? You can start with the assumption that the input will be valid in all respect. We can call this difficulty level 1. Then difficulty level 2 can be added to determine if the input is valid. For example, the path (E2 1N W3 S1) is invalid because it is not a completely closed figure. Another example is (E1 N1 W1 S2 W1 N1 E1). This creates two separate closed squares and should be considered invalid. Should we write a program that can handle an arbitrarily long path, or are there any restrictions on the legal area that the path can cover (i.e. the path will fit onto an NxN grid, or there will be a maximum of N steps)? As I said, you can create your own restrictions to start with, and later, when you find a solution, you can relax some of those restrictions to make the program more flexible and accept a wider range of inputs. Can we assume that the figure splits the plane into exactly two sections (that is, that you can draw a line from any point inside to any other point without crossing any lines)? No. Since we are using only vertical and horizintal lines, having that restriction will limit the input to only rectangles, I think. If we go for even a slightly complicated input, we will always have pairs of points that can cross the bounding lines. The first example that I showed above follows that restriction, but the second example does not (Pardon my online ASCII drawing skills)

Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius - and a lot of courage - to move in the opposite direction. - Ernst F. Schumacher

Cool, I was unfamiliar with java.awt.geom.GeneralPath. Very nice. Some interesting test cases: Path: [S3, E1, N1, E1, N1, E1, N1, W3] Area: 6 Path: [S2, E1, N1, W2, N1, E1] Area: 2 Path: [N1, E1, S1, W1, N1, E1, S1, W1] Area: 1 Path: [S2, E3, N3, W2, S2, E1, N1, W2] Area: 8 Path: [S2, E3, N3, W2, S1, E1, S1, W1, N1, W1] Area: 7 My own solution would have been a simple integration-based approach - but would've had problems with things like a figure 8. (And most of the other tests above.) Now I no longer feel complelled to complete it, since GeneralPath handles those subtleties nicely. Good job, M^2!

"I'm not back." - Bill Harding, Twister

Michael Morris
Ranch Hand

Joined: Jan 30, 2002
Posts: 3451

posted

0

Cool, I was unfamiliar with java.awt.geom.GeneralPath. Knowing all the 2D and some of the 3D Java API goes with the territory around here we do structural steel drawings. My own solution would have been a simple integration-based approach I thought about that myself, but realized that GeneralPath would do the trick so long as the units were integral. For FP units you could still use GeneralPath but would have to select an appropriate granularity to iterate thru the area. At some point though, performance would really suck and then a dead reckoning integration solution would be called for.

Jignesh Malavia
Author
Ranch Hand

Joined: May 18, 2001
Posts: 81

posted

0

That's a pretty neat solution, Michael. And you were fast too. I saw you posted yesterday itself. Actually, like Jim, I too was unfamiliar with the GeneralPath class and was expecting something without the use of any such standard library. But you still deserve full credits for your algorythm: Step1: Find the bounding rectagle. Step2: For each square in that rectangle, check if it falls inside within the closed figure. There are only two problems I could find with your code. First, it accepts open figures as valid input. E.g. it prints area=2 for (S1 E1 N1 E1 N1 W1). Second, the loop iterates one million times even for a simple square path (E1000 N1000 W1000 S1000)

Michael Morris
Ranch Hand

Joined: Jan 30, 2002
Posts: 3451

posted

0

First, it accepts open figures as valid input. E.g. it prints area=2 for (S1 E1 N1 E1 N1 W1). Good catch. I wrote it in about 30 minutes and didn't do much testing. After I posted and went to bed last night, I realized that I should have checked the currentPoint() after iterating thru the path strings. I could have thrown an exception if we didn't wind up at (0,0). Second, the loop iterates one million times even for a simple square path (E1000 N1000 W1000 S1000) No doubt as I mentioned above for large areas or small granularity it is a perfomance pig. But for limited surfaces it's a quick and simple hack.

Jignesh Malavia
Author
Ranch Hand

Joined: May 18, 2001
Posts: 81

posted

0

So no one else is trying? David? Here's my solution.

Advantages: The calculations happen as soon as the steps are read in without being stored for later use. Hence its memory consumption is independent of the number of steps in the input. Does not iterate based on the path distances. Hence the computational time is independent of the units specified. By changing the type from int to float, it should work well with decimal fractions too. Disadvantages: It works only for valid closed inputs. Some of the examples that Jim provided are not completely valid closed figure but Michael's code handles them well. My version does not. It works with 8 shaped figures only if steps/edges do not cut each other. E.g. (S1 E1 S1 E1 N1 W1 N1 W1) is a 8 shaped figure and the program prints area=2 correctly but with (S1 E2 S1 W1 N2 W1) which is exactly the same 8 shaped figure, the program prints 0. However, both cases are handled well by Michael's code.

Michael Morris
Ranch Hand

Joined: Jan 30, 2002
Posts: 3451

posted

0

That's a pretty solution Jignesh. I wouldn't have thought you could solve this in that small amount of code without a geometry API to help out.

Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18671

posted

0

That's pretty much what I have too - it's what I meant by an integrating solution. What were you envisioning, Michael? You can also add a tiny bit of code to track the nort/south coordinate as well, which allows you to check that the endpoint matches the start point. You can also use doubles instead of ints for all distances and the area; the only catch is that you have to check the endpoint more carefully, as it may be a little off from 0, 0 due to roundoff. It works only for valid closed inputs. Some of the examples that Jim provided are not completely valid closed figure but Michael's code handles them well. My version does not. Well, it handles them perfectly well for a certain mathematical definition of area. Just not the once that "common sense" would apply in most cases. Note that all my examples are closed, at least, but it's when the path crosses over itself that strange things happen. And I was thinking about those types of paths before I saw your later definition of valid, so that was the part of the problem I was really interested in. I'm still trying to think of a good way of modifying the integration solution to handle this; we'd need to at least detect each intersection with the previous path. But I'm not entirely sure what we'd do with that info - the test cases I showed seem to required different treatment. Which is why I was impressed with the GeneralPath solution.

Michael Morris
Ranch Hand

Joined: Jan 30, 2002
Posts: 3451

posted

0

What were you envisioning, Michael? My first thought was to find the bounding area and iterate thru the unit areas and subtract each that fell outside the closed area. I've been working with design drawings too long and tend to thing more geometrically than algebraically. That's why GeneralPath came to mind. So I didn't pursue a pure integral solution. I really didn't think it would be that simple. That's why I like JavaRanch, this old dog continues to learn new tricks from the best.

Reminds me of a device I used once in my Mechanical Engineering days and always wondered how it worked... Although it does suggest a discrete version of a continuous device. I mention this since whatever principle this uses could also be converted to solve this problem in a more generic manner. Background: Anyone with experience in basic calculus is aware that on a graph of velocity versus time, the area of the graph is the distance travelled. The same is true with other graphs. On the (from memory) Pressure/Entropy graph for a combustion engine, the area is a closed loop and the area represents the energy produced by the motor. Setup: The measuring device is attached to the table next to a graph of a motor cycle. (both are secured so that they can't move or rotate relative to each other. A pointy bit on the device (stylus?) is placed on an arbitrary start point on the graph, the machine is reset, then the stylus is used to trace the outline of the graph. After a complete cycle, the device gives a measure if the energy in terms of area, which is converted to the correct units based on the units of the graph. The device is completely mechanical, not electrical in any way. Makes you think, doesn't it?

Originally posted by Jignesh Malavia: So no one else is trying? David? Here's my solution. [CODE] public class ClosedPathArea { public static int calc(String[] path) { by Michael's code.

"progster P.", Welcome to JavaRanch. We don't have many rules here, but we do have a naming policy. Please edit your display name to comply with this policy. Thanks in advance and we look forward to seeing you around the Ranch.

I remember some strange curve properties from my maths degree. I think the Von Koch snowflake has a perimeter that approaches infinity, whereas its area tends to a finite limit. Something like that anyway - long time since I graduated.

"....bigmouth strikes again, and I've got no right to take my place with the human race...."<p>SCJP 1.4

Originally posted by David O'Meara: Reminds me of a device I used once in my Mechanical Engineering days and always wondered how it worked... Although it does suggest a discrete version of a continuous device. The device is completely mechanical, not electrical in any way. Makes you think, doesn't it?

If anyone wants to pursue the general case, you might want to consider how the planimeter works. It has a stylus on a fixed arm "A", that arm is connect to another arm "B" of fixed length that is anchored as needed to find the area of figure. Arms A and B can be sized by the rectangle that encloses the figure. If B is to be anchored in the southwest, then A + B must equal the northeast corner of the bounding rectangle. Now the stylus on A can be set at the origin and a triangle is formed. The triangle is stretched as vertex A moves around the figure. At each step along the path, a new triangle is formed. This new area could be summed giving the total at each step. The last step could be consider an approximate position and therefore the actual closure position could be used to avoid precision errors. or can it?

I have my dad's planimeter but have never tried it. He got it when I was very young so it must be 40 years old. He taught college math for 32 years and gave me a solution for finding the area of irregular shapes when I was in high school: cut it out and weigh it. I believe I got credit for that on a test.

A good question is never answered. It is not a bolt to be tightened into place but a seed to be planted and to bear more seed toward the hope of greening the landscape of the idea. John Ciardi