C＃中的Graphicspath Polygon拟合

Question

我需要将任意形状的图形路径“拟合”到定义的空间（几乎总是矩形或圆圈）中。

我目前使用矩阵对象扩展图形路径，并且缩放效果很好，但是问题是获得了比例因素。

我能想到的最好的技术是将图形路径转换为一个区域，将矩形或圆圈转换为区域，并执行A：

rgnShape.Intersect(rgnCircle);

然后检查是否：

rgnShape.IsEmpty()

但是，这只是告诉我形状是否太大而无法合适，因此有必要缩放形状，然后重试（可能很多次）。

是否有一种简单的方法可以立即计算缩放因子以拟合多边形图形路径，以使其完全拟合到一个圆圈中。结果应该是最大的多边形，仍然完全适合圆圈。

Answer 1

看 http://en.wikipedia.org/wiki/smallest_circle_problem 为了根据点而不是路径来讨论这个问题，Simon发现。

1. 所以，这样做，使用 rgnShape.Intersect(rgnCircle); 检查它是否有效。如果失败，请沿每条曲线抓住距离您发现的圆的中心最远的点（对于任何给定区域，可能有一个以上的点）。

2. 将它们添加到您的点列表中，重新应用算法。您无需从头开始；您无需考虑不在边界上的要点（即，忽略原始调用算法的“ set q”中的点）。

请注意，这不再是线性的，因为对于ITH点，生成递归调用的概率不再是1/i。

您必须明确处理一个边缘条件。如果在步骤1的第一次迭代中发现的区域之外发现的一条曲线是完全圆形并触摸外圈的，则“ set q”内将有无限的点，并且该算法将惨败。因此，申请后 rgnShape.Intersect(rgnCircle); 您应该第一次明确检查任何完美的圆曲线，以了解这种情况。例如，如果您的形状为 (} 您应该明确检查 () （就此讨论的目的，假装 () 是一个圆） ( 在第一次迭代期间发现的区域之外。

这仍然很糟糕，但是比改变更好 每一个 弯曲到点。

Answer 2

我不明白为什么需要二进制搜索。

一旦获得形状的边界矩形，并且您拥有要适合形状的目标矩形，则可以比较两个比率 targetHeight / shapeHeight 和 targetWidth / shapeWidth.

采用较小的比率，并将其用作缩放形状的缩放因素。

如果目标是圆而不是矩形，则可以通过采用比率来使用类似的解决方案 targetCircleDiameter / boundingRectangleDiagonal 并将其作为缩放因素。

Answer 3

您可以在GraphicsPath和该区域上使用GetBounds，然后比较矩形的大小至少使您接近。

如果定义的空间是应该准确的正方形。

如果定义的空间还有其他东西，那至少会让您接近。然后，您可以使用二进制搜索来找到实际的缩放量。

Answer 4

您不能计算图形路径的中心和半径吗？

您可以计算重心中心（平均坐标），并添加2倍标准偏差 - 这应该使您的图表约为92％ - 大多数时间都很好，但是如果您的图形具有最大的“重量”，则会失败一端。

您还可以计算点的中心 - 贯穿所有点，在所有方向上获取最大/分钟点，例如计算边界箱时，以此为中心，并将最长距离（最大/分钟）作为半径。

如果您寻找边界球体算法，您可能会发现更复杂的算法 - 但是，如果只是显示一些东西，您可以进行一些交易。如果您要进行碰撞检测，也存在一些快速算法:)

Answer 5

使用简单的数学如何采取相反的方式？即，获取路径的边界框/圆，计算预定义的矩形高度/宽度的矩形比，将其与BB相同的值进行比较（例如，如果预定义的额定配给小于1，则BB是水平拉伸的在垂直方面以匹配相同的比率），最后将整个物体扩展到预定义的矩形尺寸。现在的比例因子只是预定义高度除以BB高度和预定义宽度除以BB宽度之间的最小值。 （对于边界圆，无需调整其尺寸。）