如何计算二维矢量形状的中轴? [英] How do I calculate the medial axis for a 2D vector shape?

问题描述

我有一个 2D 形状作为路径元素存储在 SVG 中.形状由贝塞尔曲线和线段组成.

I have a 2D shape stored as a path element in an SVG. The shapes consist of Bezier curves and line segments.

我在生成的形状上也有一组等距点使用弧长参数化.

I also have a set of equally space points along the shape that I am generating using arc length parameterization.

如何使用 SVG 或这些点来确定形状的中轴?

How can I use either the SVG or these points to determine the medial axis of the shape?

我正在使用 Python，但任何类型的伪代码或算法建议将不胜感激.

I am using Python, but any sort of pseudocode or algorithm advice would be much appreciated.

以下是我正在处理的形状类型的示例，红点是我沿曲线的采样点.

The following is an example of the types of shapes I am dealing with, and the red dots are my sampled points along the curve.

推荐答案

有点晚了，但这里是:

上图显示:(我已经使用在线工具将 OP 的图像转换为 SVG因此，参差不齐的边界是红点的人工制品)1. 叠加的中轴和尺度轴变换(MAT 和 SAT).2. 仅缩放轴变换.3. 仅中轴变换.4. 许多2-prongs 之一(见下文).5. SAT 中的单个 3-prog(MAT 中有很多).

The pictures above shows: (I've converted the OP's image to SVG with an online tool hence the ragged boundary that is an artifact of the red dots) 1. Superimposed Medial and Scale Axis Transform (MAT and SAT). 2. Scale Axis Transform only. 3. Medial Axis Transform only. 4. One of many 2-prongs (see below). 5. The single 3-prong in the SAT (there are many in the MAT).

要找到中轴 (MA) 或 中轴变换 (MAT)(上图中的紫色曲线)，请使用以下算法可以使用(基于论文作者:Choi、Choi、Moon 和 Wee - 在 此处查看演示实现还处理相交的形状和带孔的形状).其他算法也存在.

To find the Medial Axis (MA) or Medial Axis Transform (MAT) (purple curves in above image) the following algorithm can be used (based on a paper by Choi, Choi, Moon and Wee - see a demo implementation here that also handles intersecting shapes and shapes with holes). Other algorithms also exist.

该算法比查找二进制图像(例如位图)骨架更难实现(a.k.a.grassfire 或离散变换)但有几个优点(例如具有解析性).为了简单起见，下面的讨论只处理简单的情况没有孔的(非相交)形状.

The algorithm is much harder to implement than finding a binary image (e.g. bitmap) skeleton (a.k.a. grassfire or discrete transform) but has several advantages (such as being analytic). To simplify things, the discussion below only handles the case of simple (non-intersecting) shapes without holes.

• Curve - 参数为 t ∈ [0,1] 的参数贝塞尔曲线.换句话说，矢量图形中使用的典型曲线.
• Shape (Ω) - (定义直接取自论文) - 连接的闭合ℝ² 中的有界开放子集由有限数量的互不相交简单的闭合曲线."为了这个答案的目的，可以进一步假设形状没有孔.简单来说就是被包围的区域由许多曲线给出的边界 - 上图中填充的灰色部分.
• Boundary - 形状的边界.换句话说，曲线的索引序列使得 t=0 处的任何曲线的起点对应于之前的t=1 处的曲线端点.边界被假定为正向(即通过沿逆时针方向的边界走，形状永远在你的左边).
• 边界点 - 形状边界上的任何点完全由标识曲线和t曲线参数的索引.
• 最大磁盘 - 形状内的磁盘未被任何其他磁盘遮挡也在形状之内.可以识别每个最大磁盘由 1 个或多个(通常为 2 个)边界点及其中心点组成.
• n-prong - 最大圆盘在 n 处切向接触形状边界点.
• 分支点 - 一个 n 叉 最大圆盘中心，其中 n >= 3.换句话说MA 上的一个点，在 MA 平面树中形成一个顶点.
• 中轴 (MA) - 所有 n 叉 中心的联合.
• 中轴变换 (MAT) - 所有 n-prongs 的结合.换句话说，最大圆盘的半径包含在定义中.
• 接触点 (cp) - 边界点链接到唯一的最大磁盘已经找到了.
• 尖角 - 边界点，通常在曲线参数 t = 0 或t = 1，不可微(不平滑)，形成一个内部角度＜180°.
• 暗角 - 与尖角相同，但角度 > 180°.
• Cp 图 - 顶点为的图(不一定是平面图)联系点因此也包含有关所有找到的信息最大磁盘以及整个MAT.图中的每个顶点 (cp)有以下边:
  • next - 从当前接触点步行找到的第一个接触点围绕边界逆时针旋转.
  • prev - 从当前接触点步行找到的第一个接触点围绕边界顺时针旋转.
  • next-around - 第一个接触点逆时针方向的最大圆盘.
  • prev-around - 第一个接触点最大磁盘顺时针方向.我们可以将上面的每一个都看作一个联系点返回的操作符 (.)另一个接触点沿着一条边，例如如果a是联系点，然后a.下一个是另一个联系点.
  • Curve - A parametric bezier curve with parameter t ∈ [0,1]. In other words, a typical curve as used in vector graphics.
  • Shape (Ω) - (Definition taken directly from the paper) - "the closure of a connected bounded open subset in ℝ² bounded by a finite number of mutually disjoint simple closed curves." For the purposes of this answer it can be further assumed that the shape has no holes. In simple terms it is the area enclosed by the boundary given by a number of curves - the filled gray part in the image above.
  • Boundary - The boundary of the shape. In other words, an indexed sequence of curves such that the starting point of any curve at t=0 corresponds to the previous curve's endpoint at t=1. The boundary is assumed positively oriented (i.e. by walking along the boundary in an anti-clockwise direction the shape will always be to your left).
  • Boundary point - Any point on the shape boundary fully identified by an index identifying the curve and a t curve paramter.
  • Maximal disk - Disks within the shape not occluded by any other disk also within the shape. Every maximal disk can be identified by 1 or more (usually 2) boundary points and its center point.
  • n-prong - A maximal disk touching the shape boundary tangentially at n points.
  • Branch point - An n-prong maximal disk center with n >= 3. In other words a point on the MA that forms a vertex in the MA planar tree.
  • Medial Axis (MA) - The union of the centers of all n-prongs.
  • Medial Axis Transform (MAT) - The union of all n-prongs. In other words, the radius of the maximal disks are included in the definition.
  • Contact point (cp) - A boundary point linked to a unique maximal disk that has already been found.
  • Sharp corner - A boundary point, usually at curve parameter t = 0 or t = 1, that is not differentiable (not smooth) and that forms an interior angle < 180°.
  • Dull corner - Same as a sharp corner except the angle > 180°.
  • Cp graph - A graph (not necessarily planar) with vertices being contact points thus also containing information regarding all found maximal disks and in turn the entire MAT. Each vertex (cp) in the graph has the following edges:
    • next - The first contact point found from the current one by walking anti-clockwise around the boundary.
    • prev - The first contact point found from the current one by walking clockwise around the boundary.
    • next-around - The first contact point found by going around the maximal disk in an anti-clockwise direction.
    • prev-around - The first contact point found by going around the maximal disk in a clockwise direction. We can view each of the above as an operator (.) on a contact point returning another contact point by following an edge, e.g. if a is a contact point, then a.next is another contact point.
    • 中轴变换形成一棵无根平面树，树叶位于每个1-prong中心(包括尖角)；如果形状有孔那么 MAT 是一个平面图.
    • 您可以通过应用程序消除形状边界上的噪声将轴变换 (SAT)(上图中的红色曲线)缩放到 MAT.这demo 实现了这样的转换，基于这个研究.但是，该演示通过确保 SAT 是一个子集来改进算法MAT 并保证拓扑保留.
    • The Medial Axis Transform forms an unrooted planar tree with tree leaves at every 1-prong center (including sharp corners); if the shape has holes then the MAT is a planar graph.
    • You can remove noise on the shape boundary by applying a Scale Axis Transform (SAT) (red curves in above image) to the MAT. The demo implements such a transform, based on this research. However, the demo improves the algorithm by ensuring the SAT is a subset of the MAT and guarantees topology preservation.
    1. 找到所有1-prongs；它们正是中轴树叶.这些是尖角和1-prongs接触边界点最大局部向内曲率.将1-prongs的接触点添加到cp-graph.请注意，由于 1-prong 只有一个 接触点，边缘 next-aroundprev-around 只会再次返回找到的联系点.
    2. 对于一组具有代表性的边界点(例如OP给出的那些红点)，计算他们的最大磁盘.它们通常是2 爪.(请参阅下面的寻找 2 爪").通过连接适当的边将他们的接触点添加到cp-graph.笔记在这种情况下，由于我们找到了 2-progs，如果 next-around(或prev-around)被跟踪两次，其中一个将回到同一个联系点.

    3. 最后找到 n >= 3 的 n-prongs.从每个 接触点开始:

    1. Find all 1-prongs; they are exactly the Medial Axis tree leaves. These are the sharp corners and the 1-prongs touching a boundary point with maximum local inward curvature. Add the contact points of the 1-prongs to the cp-graph. Note that since 1-prongs have one contact point only, the edges next-around and prev-around will just return the found contact point again.
    2. For a representative set of boundary points (such as those red dots given by the OP), calculate their maximal disks. They will generally be 2-prongs. (See 'finding a 2-prong' below). Add their contact points to the cp-graph by connecting the appropriate edges. Note that in this case, since we found 2-prongs, if next-around (or prev-around) is followed twice one will be back at the same contact point.

    3. Finally find the n-prongs for n >= 3. Starting from each contact point:

    1. 从一个接触点(比如cp1)开始遍历cp-graph，然后重复应用 cp1.next.next-around 直到你回到cp1.

    2. 如果上述情况发生 1 或 2 次迭代，则移动到下一个接触点在边界上(使用next).但是，如果需要 3 次或更多次迭代，可以证明3-prog 分支点存在并且应该在每个边界之间插入接触点cp1 和 cp1.next.

    1. traverse the cp-graph by starting with a contact point (say cp1) and applying cp1.next.next-around repeatedly until you are back at cp1.

    2. If either 1 or 2 iterations of the above occured move to the next contact point on the boundary (using next). If, however, 3 or more iterations were required, it can be proved that a 3-prong branch point exists and should be inserted with contact points on each boundary piece between cp1 and cp1.next.

    在这种情况下，插入 3-prong(有关如何找到这些内容，请参见下文)并返回到第 1 步，再次从 cp1 开始.

    In that case, insert the 3-prong (see below on how to find these) and go back to step 1, again starting from cp1.

  • 现在已经隐式地找到了 MAT 的结构.要提取MAT，需要遍历cp-graph.任意选择联系点(称为cp1)作为根(为简单起见，我们假设它链接到2-prong)，并应用next(称之为cp2).现在可以从 cp1 的链接 最大磁盘 绘制一条线以cp2为中心.这条线是 MA 子集的近似值.通过点之间的插值获得更好的近似值因为我们知道接触点的边界切线.让两条线端点是二次贝塞尔曲线的端点.由于 MA 在两个最大圆盘中心是准确已知的(通过 2 个边界切线的平均值)我们有端点处的二次贝塞尔曲线的导数，我们可以构造点之间的最佳近似二次贝塞尔曲线.如果 cp2 链接到 3 叉，则意味着平面树形成由 MA 分叉(即分支或分叉)，我们需要同时遵循 MA边缘(例如，通过使用堆栈或递归).另一方面，如果cp2 链接到 1-prong 已经到达 MA 的叶子并且该边的遍历停止.事实上，由于 MA 形成了一个平面树的遍历算法本质上与任何其他算法相同树状数据结构.
  • The structure of the MAT has now been found implicitly. To extract the MAT one needs to traverse the cp-graph. Choose any contact point (call it cp1) as the root (for simplicity let's assume it to be linked to a 2-prong), and apply next (call it cp2). A line can now be drawn from cp1's linked maximal disk center to that of cp2. This line is an approximation of a subset of the MA. A much better approximation is obtained via interpolation between the points since we know the boundary tangents at the contact points. Let the two line endpoints be the endpoints of a quadratic bezier curve. Since the orientation of the MA at the two maximal disk centers are known exactly (via the average of the 2 boundary tangents) we have the derivatives of the quadratic beziers at the endpoints too and we can construct a best approximation qudratic bezier curve between the points. If cp2 is linked to a 3-prong it implies that the planar tree formed by the MA bifurcates (i.e. branches ot forks) and we need to follow both MA edges (by using, for example, a stack or recursion). If, on the other hand, cp2 is linked to a 1-prong a leaf of the MA has been reached and the traversal stops for that edge. In fact, since the MA forms a planar tree the traversal algorithm is essentialy the same as that of any other tree data structure.

  找到一个二叉

  1. 我将在这里总结，但 Choi 等人的论文.相当解释这部分清晰易懂.

  1. I will summarize here but the paper by Choi et al. explains this part quite clearly and is easy to follow.

  在边界上选择一个点作为第一个接触点我们的 2-prong 并称之为 bp1.绘制一条向内的法线形成边界点(即要找到的 2 爪 的第一个爪").现在迭代:

  Choose a point on the boundary that will be the first contact point of our 2-prong and call it bp1. Draw an inward normal ray form the boundary point (i.e the first 'prong' of the 2-prong to be found). Now iterate:

  1. 选择一个点，p1，(与 bp1 相距 d1此射线)具有 d1 大到足以形成一个圆(在 bp1 处切线绘制)以射线为中心)将在至少一个点上切割边界.
  2. 找到最接近p1的边界点，称之为bp2.最后，找到射线上与 bp1 和 bp2 等距的点，称为 p2.
  3. 使用 p2 新的 p1 返回第 2 步.
  4. 重复步骤 2 和 3，直到 p1 到两者的距离边界点s 等于在一些容差范围内.2 爪有现在已发现 bp1 和 bp2 的两个接触点和p1 其中心.
  1. Select a point, p1, (at a distance d1 from bp1 along this ray) with d1 large enough such that a circle (drawn tangentially at bp1 with center on the ray) will cut the boundary in at least one more point.
  2. Find the closest boundary point to p1, call it bp2. Finally, find the point on the ray equidistant from bp1 and bp2 and call it p2.
  3. Go back to step 2 with p2 the new p1.
  4. Repeat steps 2 and 3 until the distance from p1 to the two boundary points are equal to within some tolerance. The 2-prong has now been found with bp1 and bp2 its two contact points and p1 its center.

  寻找三叉戟

  这里我们通过构造一个外接圆而不是与论文有所不同使用势函数.

  Finding a 3-prong

  Here we deviate a bit from the paper by constructing a circumcircle as opposed to using a potential function.

  1. 选择边界点(cp1的)链接的最大磁盘中心作为对三叉中心待发现.称之为p.
  2. 分别找到 3 个最接近 p 的点，分别到 3 个以上的边界块s.
  3. 构造这些点的外接圆并将其中心作为新的点p.
  4. 重复第 2 步和第 3 步，直到 p 到 3 个边界块的距离等于在某个容差范围内.
  5. 将这样找到的 3 个边界点标记为三爪的接触点.点p 是3 爪 的中心.
  1. Select the boundary point's (cp1's) linked maximal disk center as an initial guess to the 3-prong center to be found. Call it p.
  2. Find the 3 closest points to p seperately to each of the 3+ boundary pieces.
  3. Construct the circumcircle of those points and use its center as the new point p.
  4. Repeat steps 2 and 3 until the distance to the 3 boundary pieces from p is equal to within some tolerance.
  5. Mark the 3 boundary points thus found as contact points of the 3-prong. The point p is the center of the 3-prong.

  如果有什么不清楚的，请随时提问.

  Please feel free to ask if anything is unclear.

  这篇关于如何计算二维矢量形状的中轴?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！