algorithm - 缩放一个多边形以接触另一个多边形

Question

我正在寻找缩放一个凹多边形(具体来说，将缩放仿射变换 相对于形状的质心位置 应用于两个轴)，使其与另一个凹多边形相交/接触。每个多边形都由一组坐标定义。
下图显示了一种迭代方法:逐渐缩放多边形，直到两个多边形的最近点之间的距离为零(为此我使用了 JTS 库的 DistanceOp.nearestPoints())。
有没有一种非迭代的方法来做到这一点？一种无需迭代缩放和检查即可立即生成所需缩放因子的方法？

Answer 1

我是这样看的:

顶部三角形是要缩放的三角形，底部是要触摸的三角形。让我们先定义一些热。让缩放的多边形(顶部)为 A底部是 B令缩放中心为 P0 (A里面的红点)有2种情况(左右)。对于在 A 和 B 中获得接触点/边缘(A、B 中的蓝色物质)位置都足以计算比例。

A 的边缘B的触摸顶点(左)
简单地从 P0 转换光线通过 A 的每个顶点然后对于 A 的每条边计算 A 的选定边之间的垂直距离和 B 的顶点即在饼图切片内(两条射线通过 A 端点的选定边缘转换。记住最近的一条。

A的顶点触摸 B 的边缘或顶点(右)
简单地从 P0 转换光线通过 A 的每个顶点并找到与 B 最近的交点(到 P0 的距离)。

所以现在我们有一个可能的触摸列表，我们需要选择一个最小比例的触摸。因此，对于每个这样的触摸，我们需要知道 P0 和选定顶点或边缘之间的距离(称之为 da)以及 P0 之间的距离。和接触点 B (姑且称之为 db )。从那里应用规模改变了 da我们想要 da = db所以:

da' = da*scale = db
scale = db/da

在某些情况下 A 的边缘可以触摸 B的边缘但是，这种情况由 #1,#2 处理因为 B 的任一边缘完全是 A 的内侧边缘所以 B的顶点打那里太或边缘 B与射线相交，再次相交是相同的。