Java PathIterator - How do I find the correct perimeter of an area?

Question

The premise

I am randomly generating a two-dimensional mazelike structure. It boils down to randomly generating a bunch of rooms in the grid, then randomly connecting these rooms with corridors using A*. The rooms have walls that take up an entire square in the grid. The issue I'm having is with the creation of these walls.

To decide where to put the randomly generated rooms, I start off dividing the grid in a bunch of rectangular cells of varying sizes, these cells are adjacent to eachother, using cells with size 1 to fill up the remaining gaps between them. After that, I select a random bunch of these cells to end up as rooms. If any of the selected cells are adjacent to eachother, they are combined to form a single room. Up to this point, the algorithm works perfectly.

Example

The issue

The issue I am having is when I want to iterate through every square defining the wall of one of the rooms. What happens now is, I create an Area for each room, and add every cell required to that room's Area. I successfully used the PathIterator to iterate through the Area's outline. The only problem is that the result of that iterator is not the result I want.

For example, suppose a rectangle with coördinate (5, 5), and size (4, 6). The resulting points I would want to iterate over are the following:

• Line 1 from (5, 5) to (8, 5)
• Line 2 from (8, 5) to (8, 10)
• Line 3 from (8, 10) to (5, 10)
• Line 4 from (5, 10) to (5, 5)

Instead, I end up with the following:

• Line 1 from (5, 5) to (9, 5)
• Line 2 from (9, 5) to (9, 11)
• Line 3 from (9, 11) to (5, 11)
• Line 4 from (5, 11) to (5, 5)

In other words, every line that can be considered to be above or to the left of the inside of the Area, are inclusive to the Area, and every line considered below or to the right of the Area, are exclusive to the Area (as returned by the Area.contains function).

Now fixing this may seem trivial when dealing with simple squares, but once I started trying to fix this for an Area in general, all sorts of annoying special cases started popping up from every angle I tried fixing it.

Some stuff I tried or considered:

• Graham's Scan algorithm. Failed when I realized what 'convex hull' means and how my rooms are not that
• Consider each consecutive line in the path, check if it is largely inside or outside the Area, if it is outside, move it one unit. Failed when trying to execute with the smallest possible lines (length 2 - 3)
• Consider each consecutive set of 3 points in the path, check what type of corner they make (what direction + is it a concave or convex corner), then adapt the middle of those three points depending on the type of corner. Failed because I can't seem to find a reliable method of checking which corner the points make up to be

So I am wondering, is there something obvious I'm completely missing here? Is this something I simply will not be able to do with the PathIterator and I need to implement my own 'polygon creation' algorithm? If so, is there anything out there of the kind? I have been wracking my brain over this thing for days now. I can't seem to find any help on the internet either.

---

Ok, I just thought of something so unbelievably obvious I'm a bit ashamed at how complicated I was trying to make this. I think I was just staring myself blind on this issue.

• Iterate over all points of the bounding rectangle
• If the polygon contains the point, create a translated version of the point in every direction.
• If the polygon does not contain one of the translated points, that means the point is part of the polygon's wall.

This is an unbelievably obvious and simply mechanism, which means at least I'm saved for now, but it is clearly terribly inefficient, so if anyone has a better algorithm it is still very welcome!