# Area covered by a closed path

Ranch Hand

------------------------------------------------------

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?

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)?

Ranch Hand

**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)

Sheriff

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*

**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.

*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

Ranch Hand

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)

**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.

*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

Ranch Hand

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.

*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

Sheriff

**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.

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

**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.

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?

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.

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?

The device you speak of is a "planimeter". I used one of these many years ago. If you want to see an Applet that model a real one, go to http://www.leinweb.com/snackbar/planimtr/planimtr.htm.

Ranch Hand

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