Nondeterministic results of the facade classification

[vvoovv]

Got different results for the same command line parameters. Also note the edge marked with the magenta color. It isn't classified as the front facade.

[vvoovv]

Edges of the upper buildings facing the street are classified as the front ones in one attempt and the side ones in another attempt.

[polarkernel]

Edges of the upper buildings facing the street are classified as the front ones in one attempt and the side ones in another attempt.

????? Very magic! What was the OSM data file?

[vvoovv]

????? Very magic! What was the OSM data file?

manhattan_01.osm

[vvoovv]

Can you reproduce that result?

[polarkernel]

Can you reproduce that result?

At least I get always the same wrong result, as in the bottom image of your examples. I also know that this issue comes from replacing the way-segment in the function VisibilityInfo.__gt__(). No solution yet, I will treat it with the other tests forseen in this function.

[vvoovv]

The problem is still there:

(karl_marx_allee.osm)

[polarkernel]

The problem is still there:

This time I was able to reproduce your result. The wrong classification appeared once among five runs using the 64-bit interpreter and two times among five with the 32-bit interpreter. I know such issues fromm C++, when a misused pointer is reading data from uninitialized memory, but a far as I understand Python, this should not be able to happen. It is difficult to get hints from the net, as there almost all results refer to AI applications, where random generators are involved. But as far as I know, we do not have random values in our code.

[vvoovv]

There is a question Why is dictionary ordering non-deterministic?. But then in the reply:
From Python 3.7, this order-preserving behaviour is guaranteed

[vvoovv]

It might be also related to multithreaded operations at numpy.

[vvoovv]

More mistery. The same winning way segment, the same visibility, But different results for the building edge. Sorry for the yellow color.

[vvoovv]

More mistery.

If you want to find that building edge during the debugging:
File: berlin_karl_marx_allee.osm
edge.v1[0]==117.37134892782458
edge.v1[1]==1.9161035727416749
edge.v2[0]==132.88107678992375
edge.v2[1]==93.96658735699803

[vvoovv]

I found that avgDist takes different values each time.

[vvoovv]

I didn't dig it in further.
My suspicion is that scipy.spatial.KDTree provides different output each time.

[polarkernel]

I found that avgDist takes different values each time.

Just found the same difference.

I didn't dig it in further.
My suspicion is that scipy.spatial.KDTree provides different output each time.

You may be right. I will get in depth tomorrow, can't continue today.

[polarkernel]

found that avgDist takes different values each time.

Got the bug! The computation of the weighted average distance was made at the end of every loop for a way-segment. But at this time, it was not yet clear, wheter the current way-segment will win. Therefore, this computation had to be shifted to the very end of the visibility computation, where for every edge the winning way-segment is crowned. Then, the result of the classification gets correct and stable. The new version is committed. Probably your skills for optimizations is requested.

However, this would only explain, why the result was wrong, but not the non-determinism. Digging for this issue, I found that either the order of the ways in the loop at line 109 or of the way-segments in the loop at line 110 is non-deterministic. This produced the bug mentioned above, but every time in a different way because of the different order. I don't know, where this non-determinism comes from, but didn't invest a lot of time to find that.

[vvoovv]

Got the bug!

Thank you!

However, this would only explain, why the result was wrong, but not the non-determinism.

I found the reason for the non-determinism. Way categories were defined in defs.way as Python sets. Iteration through the elements of a Python set isn't deterministic. I replaced Python sets with Python lists.