Autogeometry convex decomposition

[gaorkl]

Hi!

Amazing library, thanks!

I am trying to get the convex decomposition to work, but I am having the following issue:
I am creating a + shaped polygon, and then try to decompose it.
However it returns the convex hull.

Do you know what I might be doing wrong?

from pymunk.autogeometry import convex_decomposition
vertices = [(-45, 0), (-40, 4), (-5, 4), (-4, 40), (0, 45), (4, 40), (5, 4), (40, 4), (45, 0 ), (40, -4), (5, -4), (4, -40), (0, -45), (-4, -40), (-4, -5), (-40, -4)]
new_vert = convex_decomposition(vertices, tolerance = 0.1)

print(new_vert)

# [[Vec2d(-45.0, 0.0),  Vec2d(0.0, -45.0),Vec2d(45.0, 0.0),Vec2d(0.0, 45.0), Vec2d(-45.0, 0.0)]]

Cheers

Michael

[viblo]

It is because the "winding" of the polygon is wrong. If you reverse the order it will work.

>>> from pymunk.autogeometry import convex_decomposition
>>> vertices = [(-45, 0), (-40, 4), (-5, 4), (-4, 40), (0, 45), (4, 40), (5, 4), (40, 4), (45, 0 ), (40, -4), (5, -4), (4, -40), (0, -45), (-4, -40), (-4, -5), (-40, -4)]
>>> vertices = list(reversed(vertices))
>>> print(vertices)
[(-40, -4), (-4, -5), (-4, -40), (0, -45), (4, -40), (5, -4), (40, -4), (45, 0), (40, 4), (5, 4), (4, 40), (0, 45), (-4, 40), (-5, 4), (-40, 4), (-45, 0)]
>>> new_vert = convex_decomposition(vertices, tolerance = 0.1)
>>> print(new_vert)
[[Vec2d(-4.945945945945946, 5.945945945945958), Vec2d(0.9999999999999978, 7.105427357601002e-15), Vec2d(5.0, 4.0), Vec2d(4.0, 40.0), Vec2d(0.0, 45.0), Vec2d(-4.0, 40.0), Vec2d(-4.945945945945946, 5.945945945945958)], [Vec2d(0.9999999999999978, 7.105427357601002e-15), Vec2d(5.0, -4.0), Vec2d(40.0, -4.0), Vec2d(45.0, 0.0), Vec2d(40.0, 4.0), Vec2d(5.0, 4.0), Vec2d(0.9999999999999978, 7.105427357601002e-15)], [Vec2d(-4.0, -40.0), Vec2d(0.0, -45.0), Vec2d(4.0, -40.0), Vec2d(5.0, -4.0), Vec2d(1.0617283950617293, -0.06172839506172423), Vec2d(-4.0, -5.0), Vec2d(-4.0, -40.0)], [Vec2d(-40.0, -4.0), Vec2d(-4.5011583011582985, -4.986078936078936), Vec2d(-5.0, 4.0), Vec2d(-40.0, 4.0), Vec2d(-40.0, -4.0)], [Vec2d(-5.0, 4.0), Vec2d(-4.5011583011582985, -4.986078936078936), Vec2d(-4.0, -5.0), Vec2d(1.0617283950617293, -0.06172839506172423), Vec2d(-4.945945945945946, 5.945945945945958), Vec2d(-5.0, 4.0)]]
>>>

You can check if the order is correct by calculating the area of the polygon with pymunk.area_for_poly. If the area is negative the polygon is "inside out" and need to be reversed.

>>> vertices = [(-45, 0), (-40, 4), (-5, 4), (-4, 40), (0, 45), (4, 40), (5, 4), (40, 4), (45, 0 ), (40, -4), (5, -4), (4, -40), (0, -45), (-4, -40), (-4, -5), (-40, -4)]
>>> pymunk.area_for_poly(vertices)
-1368.0

Its not very easy to catch this issue.. The convex_decomposition is supposed to have an assert that checks this, so that you would get a warning when its wrong, but seems like it is not working. I will keep this issue opened until Ive had time to look into why and hopefully fix it.