找出闭合的二维均匀三次B样条曲线的面积 [英] finding the area of a closed 2d uniform cubic B-spline

问题描述

我有一个二维点列表，它们是闭合均匀三次B样条曲线的控制顶点(Dx).我假设一条简单的曲线(非自相交，所有控制点都不同).

I have a list of 2d points which are the control vertices (Dx) for a closed uniform cubic B-spline. I am assuming a simple curve (non-self-intersecting, all control points are distinct).

我试图找到曲线所包围的区域:

I am trying to find the area enclosed by the curve:

如果我计算结点(Px)，则可以将曲线视为多边形；那么我只是"需要找到实际曲线和连接结点的直线之间每个分段的剩余增量区域.

If I calculate the knot points (Px), I can treat the curve as a polygon; then I "just" need to find the remaining delta areas, for each segment, between the actual curve and the straight line joining the knot points.

我了解到Bspline的形状(以及面积)在旋转和平移时是不变的-因此，对于每个段，我可以找到一个平移以将t = 0结置于原点，并找到一个旋转以将t置于+1在+ x轴上结:

I understand that the shape (and therefore area) of a Bspline is invariant under rotation and translation - so for each segment, I can find a translation to put the t=0 knot at the origin and a rotation to put the t=1 knot on the +x axis:

我可以通过将点插入并重新分组来找到曲线的方程式:

I can find the equation for the curve by plugging the points in and re-grouping:

P(t) = (
    (t**3)*(-Dm1 + 3*D0 - 3*D1 + D2)
    + (t**2)*(3*Dm1 - 6*D0 + 3*D1)
    + t*(-3*Dm1 + 3*D1)
    + (Dm1 + 4*D0 + D1)
) / 6.

但是我想把头发撕成碎片-我可以做到

but I'm tearing my hair out trying to integrate it - I can do

 1
/
| Py(t) dt
/
t=0

但是那没有给我面积.我认为我需要的是

but that doesn't give me area. I think what I need is

 Px(t=1)
/
| Py(t) (dPx(t) / dt) dt
/
x = Px(t=0)

但是在我进一步之前，我真的很想知道:

but before I go further, I'd really like to know:

1. 这是对面积的正确计算吗?理想情况下，解析解决方案将使我为之开心！

1. Is this the correct calculation for area? Ideally, an analytic solution would make my day!

找到该区域后，如何确定是否需要从基本多边形(第一张图中的红色区域与绿色区域)相加或相减?

Once I find this area, how can I tell whether I need to add or subtract it from the base poly (red vs green areas in the first diagram)?

是否有任何Python模块可以为我执行此计算? Numpy有一些评估三次Bspline的方法，但似乎没有一个可以处理面积的方法.

Are there any Python modules which would do this calculation for me? Numpy has some methods for evaluating cubic Bsplines, but none which seem to deal with area.

是否有更简单的方法来做到这一点?我正在考虑也许在一堆点上评估P(t)-类似于t = numpy.arange(0.0, 1.0, 0.05)-并将整个事物视为多边形.知道需要多少细分才能保证给定的准确性(我希望误差< 1％)吗?

Is there an easier way to do this? I am thinking about maybe evaluating P(t) at a bunch of points - something like t = numpy.arange(0.0, 1.0, 0.05) - and treating the whole thing as a polygon. Any idea how many subdivisions are needed to guarantee a given level of accuracy (I'd like error < 1%)?

推荐答案

1. 选择任意点作为枢轴 p ₀ (例如原点(0,0))
2. 沿曲线选择一些点 p ₁ = (x，y)
3. 微分该点的曲线，以获得速度 v =< vx，vy >
4. 从这三个点组成一个三角形，然后

1. Pick some arbitrary point as pivot p₀ (e.g. the origin (0,0))
2. Pick some point along the curve p₁ = (x,y)
3. Differentiate the curve at that point, to get a velocity v = <vx,vy>
4. Form a triangle from the three points, and calculate the area. Easiest done with a cross product between the vectors p₀p₁ and v, and dividing by two.
5. Integrate this area over t, from 0 to 1.

您得到的结果是整个曲线的一部分的面积.有些将是消极的，因为它们面临相反的方向.如果对所有线段的面积求和，就可以得出整个曲线的面积.

The result you get is the area for one segment of the whole curve. Some will be negative, as they face the opposite direction. If you sum up the areas for all segments, you get the area of the whole curve.

结果是:

面积 _i =(31 x _{i -1} y _i + 28 x _{i -1} y _{i +1} + x _{i - 1} y _{i +2} -31 x _i y _{i -1} + 183 x _i y _{i +1} + 28 x _i y _{i +2} -28 x _{i +1} y _{i -1} -183 x _{i +1} y _i + 31 x _{i +1} y _{i +2} - x _{i +2} y _{i -1} -28 x _{i +2} y _i -31 x _{i +2} y _{i +1} )/720

Area_i = (31 x_i-1 y_i + 28 x_i-1 y_i+1 + x_i-1 y_i+2 - 31 x_i y_i-1 + 183 x_i y_i+1 + 28 x_i y_i+2 - 28 x_i+1 y_i-1 - 183 x_i+1 y_i + 31 x_i+1 y_i+2 - x_i+2 y_i-1 - 28 x_i+2 y_i - 31 x_i+2 y_i+1) / 720

如果将其转换为矩阵形式，则会得到:

If you convert it into matrix form, you get:

面积 _i =< x _{i -1}   x _i   x _{i +1}   x _{i +2} > · P · < y _{i -1}   y _i   y _{i +1}   y _{i +2} > ^T

Area_i = <x_i-1   x_i   x_i+1   x_i+2> · P · <y_i-1   y_i   y_i+1   y_i+2>^T

其中 P 是

[    0   31   28    1]
[  -31    0  183   28] / 720
[  -28 -183    0   31]
[   -1  -28  -31    0]

---

如果控制点为[(0,0) (1,0) (1,1) (0,1)]，则结果区域将变为:

---

If the control points are [(0,0) (1,0) (1,1) (0,1)], the resulting areas become:

[(0,0), (1,0), (1,1), (0,1)] -> 242/720
[(1,0), (1,1), (0,1), (0,0)] -> 242/720
[(1,1), (0,1), (0,0), (1,0)] ->   2/720
[(0,1), (0,0), (1,0), (1,1)] ->   2/720

总和为488/720 = 61/90.

The sum is 488/720 = 61/90.

这篇关于找出闭合的二维均匀三次B样条曲线的面积的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！