Recent Posts

Ok, that kinda makes me a little happier.  This was the same problem I was having when implementing the Python code in Java.  I thought it was a problem with the language conversion, but it seems to be in the algorithm itself.

btw, here's a picture of what the shapes look like if it will help you step through your code:

Without doing extensive head bashing, I'm voting for the recursive method.

Very interesting. If I change the sort order of the hash (technically this is not possible but I can take the hash keys and sort them any way I'd like), I can get different results and I always get multiple lists. This is because I'm not recursively following the overlapping shapes and when the non-recursive method hits a shape it hasn't touched before it starts a new list. I'm going to see if I can approach a non-recursive solution that will always generate the correct result.

I see a problem. Investigating...

Code:

$ python test.py
> non-recursive()
set(['shape13', 'shape12', 'shape11', 'shape10', 'shape3', 'shape1', 'shape7', 'shape6', 'shape5', 'shape9'])
set(['shape3', 'shape12', 'shape1', 'shape5'])
set(['shape2', 'shape8', 'shape6', 'shape10', 'shape4'])
> recursive()
set(['shape13', 'shape12', 'shape11', 'shape10', 'shape3', 'shape2', 'shape1', 'shape7', 'shape6', 'shape5', 'shape4', 'shape9', 'shape8'])

Hummm...Party...Clannies...Allies     
if not what's the use in being in a clan

I guess that would work too ha

Damn. Now I'm going to have to get a 7th account so i can get full xp on all my characters. ha

Hummm...Party...Clannies...Allies     
if not what's the use in being in a clan

Damn. Now I'm going to have to get a 7th account so i can get full xp on all my characters. ha

Fred, try this with your (non-recursive) function.  How many lists does it end up creating?

shapes = {
     'shape1': ['shape3', 'shape12'],
     'shape2': ['shape4', 'shape6', 'shape8'],
     'shape3': ['shape1', 'shape5'],
     'shape4': ['shape2', 'shape6'],
     'shape5': ['shape3', 'shape7', 'shape11'],
     'shape6': ['shape2', 'shape4', 'shape8', 'shape10'],
     'shape7': ['shape5', 'shape9', 'shape11'],
     'shape8': ['shape2', 'shape6'],
     'shape9': ['shape7', 'shape11'],
     'shape10': ['shape6', 'shape13'],
     'shape11': ['shape5', 'shape7', 'shape9', 'shape13'],
     'shape12': ['shape1', 'shape13'],
     'shape13': ['shape10', 'shape11', 'shape12'],

Very good sir. Here are the results without L48 if shape in shapeList check. An improvement. I think for your purposes, either method works fine.

Code:

$ python test.py
method 1: 13.74416
method 2: 15.41061

[if shape in shapeList:]

I think you can remove line 48: if shape in shapeList:.  The corresponding line 10 in my program if (shapeList.get(shape) != null) returns the values of the shape key (the list of overlapping shapes) and specifically checks for a null case, since you can't iterate over a null list in Java.  I think your line is just checking if the shape is in the list, which it always will be.  This may speed up your algorithm slightly.

Here's a slightly modified version that will make more sense:

Code:

1 public HashSet<Shape> getOverlappingShapes(Shape shape, HashSet<Shape> touchedList,
 2 HashMap<Shape, LinkedList<Shape>> shapeList) {
 3
 4 if (touchedList.contains(shape)) {
 5 return null;
 6 }
 7 touchedList.add(shape);
 8 HashSet<Shape> list = new HashSet<Shape>();
 9 list.add(shape);
10 LinkedList<Shape> overlappingList = shapeList.get(shape);
11 if (overlappingList != null) {
12 for (Shape s : overlappingList) {
13 HashSet<Shape> shapes = getOverlappingShapes(s, touchedList, shapeList);
14 if (shapes != null) {
15 list.addAll(shapes);
16 }
17 }
18 }
19 return list;
20 }

Running 677 shapes through takes an average of 11ms.  This is probably many more shapes than what will typically be used; I would think at the most a user may have 30-40 shapes.

Here are the screen shots of the 677 shape test I was using.  The outlines on these shapes are 0.12" away from the shapes.