Improvement for rectangular or, in general, constant width polygons

[esuig]

Hello,
Really a great piece of code! the idea behind is so simple and so smart at the same time!

I have a question, maybe is an obvious one, but I'd like to know your opinion.
I've noted that when using this algorithm on rectangular polygons (or constant width polygons, see images below), it takes much more time than one would expect looking at the shape(inependently from the number of points). I mean, I know that this is related to how the algorithm works, but does someone have an idea on how to address and improve calculation time in this specific cases? I post two images, just as an example. I would like to study this aspect.