Propositions for optimizations

[polarkernel]

This issue shall be used to discuss propositions for optimizations of the project.

[polarkernel]

The skeletonization code stores polygon and hole edges in the class LineSegment2, constructed in the method from_polygon() of the class _LAV and collected in the class _LAVertex. Whenever a unit vector of an edge is required, it gets computed applying the method normalized() on the direction vector v in LineSegment2, which is very inefficient.

We could provide the line segments of polygon and holes already as input to skeletonize() and compute the unit vector only once per segment and store it in LineSegment2. It would then be available within the computation of the skeleton and also as output of polygonize().

How should the output of polygonize() look like to be convenient for the usage in blender-osm?

[vvoovv]

I suggest to add input additional parameters:

• unitVectors (a Python list), the order of unitVectors for the polygon edges is the same as the order of vertices in the input Python list verts. Should it be an optional or obligatory parameter?
• edgeLengths (a Python list). Are edge lengths used inside polyskel.skeletonize(..) method?

[polarkernel]

I suggest to add input additional parameters:

• unitVectors (a Python list), the order of unitVectors for the polygon edges is the same as the order of vertices in the input Python list verts. Should it be an optional or obligatory parameter?

• edgeLengths (a Python list). Are edge lengths used inside polyskel.skeletonize(..) method?

• unitVectors: OK. Can be optional for callers that didn't yet compute unitVectors, just to make the function run in this case. But I don't propose to return them as a result. When required by the caller, they should get computed there.
• edgeLengths: Not required, edge lengths are used nowhere in polyskel.skeletonize(..) method.

I dont think it makes any sense to return unit vectors for the skeleton edges on calling polyskel.polygonize(..), as their direction is different for different faces?

[vvoovv]

• unitVectors: OK. Can be optional for callers that didn't yet compute unitVectors, just to make the function run in this case. But I don't propose to return them as a result. When required by the caller, they should get computed there.

Ok, agreed

• edgeLengths: Not required, edge lengths are used nowhere in polyskel.skeletonize(..) method.

Ok. No edge lengths as inputs.

I dont think it makes any sense to return unit vectors for the skeleton edges on calling polyskel.polygonize(..), as their direction is different for different faces?

Unit vectors for the skeleton edges aren't needed by the addon. Only the ones for the polygon edges (including holes) are needed by the addon.

[polarkernel]

OK, then the new signature will be

bpypolyskel.polygonize(verts, firstVertIndex, numVerts, unitVectors=None, numVertsHoles=None, height=0., tan=0., faces=None)

I will update the new code soon.

[vvoovv]

I updated the first message at #2.

[polarkernel]

I will update the new code soon.

This has been done now, the new code is commited to the repository.

[vvoovv]

Thank you! I'll test it in the coming days.

[polarkernel]

Do we need logging in bpypolyskel.py? From the original code of skeletonize(), we actuall import a logger and use many instructions like

    log.info("%.2f Peak event at intersection %s from <%s,%s,%s> in %s", event.distance,
                 event.intersection_point, event.vertex_a, event.vertex_b, event.vertex_a.prev, lav)

Additionally, every class, also those in the euclid replacement, needs to implement __str__() and __repr__() like

    def __str__(self):
        return "LAV {}".format(id(self))
    def __repr__(self):
        return "{} = {}".format(str(self), [vertex for vertex in self])

which provide string representations of the object.

During my 'exercise' in computational geometry I preferred to debug using mathplotlib in order to see what's going on. I know, it's not very much code, but we could save some memory.

[vvoovv]

Hi @polarkernel,

I think it's ok to remove the logging code.

[polarkernel]

In #5 (comment) I mentioned that using double-precision floating point computations in cross- and dot-products increased the quality of the skeleton. At this time it was unknown, how much the performance decreases by this change. I did now some tests to get an impression of this subject.

As an example, I used the data of potsdam_grosse_weinmeisterstrasse_49d, which is some kind of average sized building. On my computer, one execution of polygonize() with this data requires 10.8 ms (average of 500 runs). Note that on a Windows computer the timing is not very accurate, but I think it will be enough to get an idea. In this example, 436 cross-products and 293 dot-products were computed for one run.

The setup for my measurements for cross- and dot-products was as follows:

    from mathutils import Vector
    a = Vector((1.7,5.8))
    b = Vector((9.1,3.7))
    def dot(a, b):
        return a.x * b.x + a.y * b.y
    def cross(a, b):
        return a.x * b.y - a.y * b.x

Then I used three different test snippets to measure the execution time (here shown for the cross-product and similar for the dot-product):

    1)  c = a.cross(b)              # mathutils
    2)  c = cross(a,b)              # function call
    3)  c = a.x * b.y - a.y * b.x   # inline

The results were as follows:

1. One single execution required 0.16 µs for each of the two products (average of 1e6 runs). Multiplying them by the number of executions and adding the results gives the total execution time of 114.74 µs. This is the reference for this comparison.
2. Using the function call, the cross-product required 1.40 µs and the dot-product 1.43 µs. The total time becomes 1.028 ms, nearly 10-times that of mathutils!
3. The inline snippet required 0.33 µs for the cross-product and 0.34 µs for the dot-product. The total time for this solution is 242.75 µs, 128.01 µs more than for mathutils.

Conclusions:

• It's terrifying how much a function call costs in Python! Solution 2) is completely inadequate.
• The additional 128.01 µs of the inline snippet corrspond to an increase of about 1.19% of the total execution time. I think this would be affordable for the increase of quality.
• Therefore I propose to update the code using inline versions of cross- and dot-products.
• Pro: Less weird results. For instance the example prague_wenzigova_458 looks well when using double-precision floating point computation.
• Cons: More memory for code and less readable code (but this could be improved by comments).

Note: Using double precision will not solve the issues of floating point precision for computational geometry, it will only shift them to another level.

EDIT: It is not true that prague_wenzigova_458 looks better than with single-precision arithmetic. I forgot to remove a decreased mergeRange in my test code of bpypolyskel.py with double-precision cross- and dot-products. I like to postpone this proposition for now.

[vvoovv]

Anyway, it would be good to have several variants of calculations in the bpypolyskel library if there will be more than one of them.