c++ - 实现自动线段缩放算法

Question

我收到以下几点作为输入:

Point A(200 ; 400)
Point B(400 ; 400)
Point C(400 ; 200)
Point D(600 ; 200)
Point E(700 ; 500)
Point F(500 ; 700)
Point G(200 ; 600)

这些点构成了要绘制的线段AB，BC，CD，DE，EF，FG和GA
那样:



现在，我受命编写一个自动缩放算法，该算法基于
确定实际片段长度的最接近的数字:



由于必须自己决定约束条件，因此我决定尽力而为
保持 Angular 完整。首先，我确定最长的段
建立一个比例(即“标记长度6” = 250px，然后标记
长度1〜= 41.7)。

然后，我将下一段更短地处理，从其中心重新缩放，然后应用
与其相邻 vector 的翻译相同。

这是我现在可以获得的最佳输出:



但是这种方法最终会陷入无限循环，或者实际上是不准确的
在其他情况下，尤其是当线条是手工绘制的而不完美时
直行。

有众所周知的算法可以解决这种情况吗？我没头绪
搜索某些几何库(例如GEOS)时从哪里开始，
libigl，...

Answer 1

如果您深入研究这是一个非常困难的问题。通过乘以常数来进行天真缩放是不可能的，因为这会改变形状， Angular 等。

为了放大和缩小多边形，最好的方法是使用沿垂直方向向内/向外移动边并随后修复连接点的方法。但是请注意这里的一些基本问题:

draw outline for some connected lines

How can I create an internal spiral for a polygon?

在此之上的问题会增加未知的边长。与纸盒切割SW技术非常相似(但更为简单)。因此，从我的 Angular 来看，您应该:

以极性编码对多边形进行编码

因此，不仅要使用笛卡尔坐标，还要使用极线。多边形被编码为一组连接的线(循环)。每行都需要以下信息:

float angle;
float length;
int flag;
float x0,y0,x1,y1; // computed endpoints for rendering

可以通过angle计算atan2(y1-y0,x1-x0)，并且长度很明显sqrt((x1-x0)^2+(y1-y0)^2)。该标志可以存储哪个值是最终的(测量值)。

设置测量值

因此，更改您知道的边的长度并相应地设置其标志

再次重新计算端点

line[i].x0=line[i-1].x1;
line[i].y0=line[i-1].y1;
line[i].x1=line[i].lengths*cos(line[i].angle);
line[i].y1=line[i].lengths*sin(line[i].angle);

其中第一行的x0,y0将是多边形的原点。为了计算一条线，必须计算先前的线段，并且必须设置实际线的所有值。因此，请计算所有可能的行，并在无法计算更多行时停止。

如果您没有上一行的位置信息，则应将其标记为 float 位置并盲目选择(例如(0,0))。

拟合

将会有一堆未计算的线(未设置实际长度/ Angular )。如果计算前后的行，则可以简单地使用其x0,y0,x1,y1
如果您计算了一行并且下一行被标记为 float ，则重新计算它及其所有跟随者，直到未计算或命中同一行。

真正的问题将是连接的未计算线的集合。对于那些，您可以通过乘以常量+转换来缩放，或者更改第一行和最后一行的长度，直到它们加入计算的部分。取决于要保留的形状的属性。

正如您所看到的那样，这不是一件容易的事，最有可能是我忘了处理一些极端情况。

可缩放的纸盒形状基于缩放方程。线的每个尺寸都由字符串而不是数字定义，并且它可以使用线的极坐标和笛卡尔(可切换)表示。该字符串可以保存数字，预定义的大小常数或公式。这样，只需更改一些系数(通常是盒子的高度，宽度，深度，纸张厚度)，整个形状就可以重新缩放，而无需进行任何调整。但是创建这样的几何图形并不是一件容易的事。有诸如BoxMaker之类的Box制制机(切割和划线/压印绘图仪)用软件，但这些制版机通常需要连接昂贵的机器才能运行，并且不能免费使用。

如果要采用这种方式，则需要实现表达式求值，请参见:

Sign of a symbolic algebraic expression