我需要实现一个 Minkowski 求和函数，它可以返回 2 个圆、2 个凸多边形或一个圆和一个凸多边形的 Minkowski 和。我发现this线程解释了如何对凸多边形执行此操作，但我不确定如何对圆形和多边形执行此操作。另外，我该如何表示答案？!我希望算法在 O(n) 时间内运行，但乞丐不能选择。
最佳答案
圆很简单——只需添加中心点，然后添加半径即可。 Circle + ConvexPoly 几乎同样简单:将每个线段垂直向外移动圆半径，并使用以原始多边形顶点为中心的圆弧连接相邻线段。通过圆心平移整体。
至于如何表示答案:嗯，这取决于您想用它做什么。如果您只想使用矢量绘图库进行绘制，则可以将其转换为 NURBS。如果您只想要多边形近似，则可以使用折线近似圆弧。或者你可以按原样存储它——“这个多边形，按这样那样的半径扩展”。例如，对于光线转换之类的事情来说，这将是最佳选择。或者作为折衷方案，您可以线性连接相邻线段而不是圆弧，并将其存储为(新)凸多边形和顶点处的圆列表的并集。
哦，关于 ConvexPoly + ConvexPoly。这是最棘手的一个，但仍然很简单。基本思想是，获取每个多边形的线段向量列表(从某个特定的极值点开始，例如每个多边形上具有最低 X 坐标的点)，然后将两个列表合并在一起，保持按角度排序。将您开始的两个点相加，然后应用合并向量列表中的每个向量来生成其他点。
关于time-complexity - 计算圆和凸多边形的 Minkowski 差值，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20060675/