issue with medial axis not being straight

[vivekbharadhwajsa]

Hey,
in the pics attached below,

here is the medial axis

in this particular slice, the medial axis is not a straight line but is comprised of points which form a zig-zag medial axis. Can you tell me why the trimesh.path.polygons.medial_axis yields a zig-zag medial axis like the one in this figure?

in this above pics, at the region of the red marking, the medial axis is supposed to be a straight line. But i don't understand why i get a zig-zag medial axis.
Thanks

[mikedh]

Oh, the medial axis function returns the approximate medial axis calculated by sampling the boundary and then computing a furthest-site voronoi diagram. If you pass a higher resolution the artifacts should be correspondingly smaller:

In [1]: import trimesh

In [2]: from shapely.geometry import Point

In [3]: polygon = Point([0,0]).buffer(1.0).difference(Point([0,0]).buffer(.9))

In [4]: polygon
Out[4]: <shapely.geometry.polygon.Polygon at 0x7f66b7accfd0>

In [5]: trimesh.path.polygons.medial_axis?
Signature: trimesh.path.polygons.medial_axis(polygon, resolution=None, clip=None)
Docstring:
Given a shapely polygon, find the approximate medial axis
using a voronoi diagram of evenly spaced points on the
boundary of the polygon.

Parameters
----------
polygon : shapely.geometry.Polygon
  The source geometry
resolution : float
  Distance between each sample on the polygon boundary
clip : None, or (2,) int
  Clip sample count to min of clip[0] and max of clip[1]

Returns
----------
edges : (n, 2) int
  Vertex indices representing line segments
  on the polygon's medial axis
vertices : (m, 2) float
  Vertex positions in space
File:      /dropbox/drop/Dropbox/robotics/trimesh/trimesh/path/polygons.py
Type:      function

In [6]: 

In [6]: axis = trimesh.path.polygons.medial_axis(polygon, resolution=0.01)

[vivekbharadhwajsa]

Hey,
I tried different resolutions. I used a resolution of 0.01 and 0.00001 but the medial axis is still a zig-zag line.

slice

calculated medial axis

zoomed in version

Is it possible to calculate the exact medial axis? (i mean, to get straight lines in the medial axis)

[mikedh]

Hey, happy to take PR's with an implementation of exact medial axis but only the approximation is currently implemented. This method looks reasonable.

You could also just keep decreasing the resolution until it is "smooth enough" for your needs.

[vivekbharadhwajsa]

Hey,
I tried a very small resolution(0.0000000001) and it was still a zig-zag medial axis as in the pic above. But it is a problem for me when the medial axis is zig-zag because, when manufacturing that slice, the robot needs to move very small distances of the medial axis in a zig-zag pattern and it is not efficient and also it takes a lot of time. So, I was looking for a smooth medial axis which is a straight line as it becomes more efficient and less time consuming for the robot. Do you have any suggestions to refine the approximate medial axis to achieve this task?
Thanks

[mikedh]

Yeah an exact medial axis calculation would be better, but there are a number of ways to smooth jagged results like that. The two easiest are shapely's built in simplification and b-spline resampling:

import trimesh
import numpy as np

from shapely.geometry import Polygon, LineString

import matplotlib.pyplot as plt


if __name__ == '__main__':

    trimesh.util.attach_to_log()

    ## create sample data of a thin rotated rectangle
    rect = np.array([[0,0], [1,0],[1,1],[0,1],[0,0]],
                    dtype=np.float64)
    hole = (rect * 0.9) + 0.05
    matrix = trimesh.transformations.planar_matrix(
        theta=np.radians(12))
    p = Polygon(
        shell=trimesh.transform_points(rect, matrix),
        holes=[trimesh.transform_points(hole, matrix)])

    # get the medial axis
    edges, vertices = trimesh.path.polygons.medial_axis(
        p, resolution=0.0002)

    # get traversals
    dfs = trimesh.graph.traversals(edges, mode='dfs')
    # make sure every consecutive index in DFS
    # traversal is an edge in the source edge list                       
    dfs_connected = trimesh.graph.fill_traversals(dfs, edges=edges)

    # simplify result using shapely
    smooth = 0.01
    for c in dfs_connected:
        line = LineString(vertices[c]).simplify(smooth)
        plt.plot(*line.xy)
    plt.title('Shapely Simplify')
    plt.show()

    # simplify using b-spline resampling
    smooth  = 0.0005
    for c in dfs_connected:
        if len(c) > 3:
            line = trimesh.path.simplify.resample_spline(
                vertices[c], smooth=smooth)
            plt.plot(*line.T)
        else:
            plt.plot(*vertices[c].T)
    plt.title('Spline Simplify')
    plt.show()

[mikedh]

I'll add "exact medial axis" implementation to feature requests and close this for now.