绘制折线中的扭结检测
用户可以使用一个非常简单的工具（按住 LMB 移动鼠标）在我的应用程序中绘制草图。这会导致一系列鼠标移动事件，我记录每个事件的光标位置。生成的折线曲线往往相当密集，几乎每隔一个像素就有记录点。我想平滑这条像素化折线，但我不想平滑预期的扭结。那么我如何找出问题所在呢？
该图像显示了记录的轨迹（红色像素）和人类所理解的“隐含”形状。人们在拐角处往往会放慢速度，因此这里的噪音通常比直道上的噪音更大。
折线跟踪器 http://www.freeimagehosting.net/uploads/c83c6b462a.png
Users can sketch in my app using a very simple tool (move mouse while holding LMB). This results in a series of mousemove events and I record the cursor location at each event. The resulting polyline curve tends to be rather dense, with recorded points almost every other pixel. I'd like to smooth this pixelated polyline, but I don't want to smooth intended kinks. So how do I figure out where the kinks are?
The image shows the recorded trail (red pixels) and the 'implied' shape as a human would understand it. People tend to slow down near corners, so there is usually even more noise here than on the straight bits.
Polyline tracker http://www.freeimagehosting.net/uploads/c83c6b462a.png
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
您所描述的内容可能与手势识别技术有关，因此您可以在其中搜索想法。
显而易见的方法是应用曲线拟合，但这会产生平滑所有有趣的细节和扭结的效果。建议的另一种方法是查看速度和加速度，但这可能会变得很麻烦（方向变化可能非常快或非常慢并且是故意的）
一个相当基本但有效的方法是将样本直接简化为折线。
例如，依次处理样本（例如，从样本 1 到样本 4），并检查所有 4 个样本是否都位于 1 和 4 之间直线的合理误差范围内。 4. 如果是，则将其扩展到点 1..5 并重复，直到从起点到终点的直线不再为这些样本定义的曲线提供合理的近似值。创建一条直到前一个采样点的线段，并开始累积新的线段。
当样本彼此太接近时，您必须小心设置阈值，因此在考虑彼此距离小于 4-5 像素的样本时，您可能需要调整灵敏度。
这将为您提供一组相当准确地遵循原始路径的直线。
如果您需要额外的平滑，或者想要创建可缩放的矢量图形，那么您可以从折线进行曲线拟合。首先，识别扭结（折线中一条线与下一条线之间的角度锐利的位置 - 例如，超过 140 度的任何内容都被视为平滑曲线，小于该值的任何内容都被视为扭结）并在这些不连续处断开折线。然后对原始手势的每个子部分进行曲线拟合以平滑它们。这将具有使光滑的东西变得光滑并锐化扭结的效果。 （您可以更进一步，插入小的光滑角圆角而不是这些尖锐的接头，以减少接头的锋利度）
蛮力，但它可能只是达到您想要的效果。
What you're describing may be related to gesture recognition techniques, so you could search on them for ideas.
The obvious approach is to apply a curve fit, but that will have the effect of smoothing away all the interesting details and kinks. Another approach suggested is to look at speeds and accelerations, but that can get hairy (direction changes can be very fast or very slow and deliberate)
A fairly basic but effective approach is to simplify the samples directly into a polyline.
For example, work your way through the samples (e.g.) from sample 1 to sample 4, and check if all 4 samples lie within a reasonable error of the straight line between 1 & 4. If they do, then extend this to points 1..5 and repeat until such a time as the straight line from the start point to the end point no longer provides a resonable approximation to the curve defined by those samples. Create a line segment up to the previous sample point and start accumulating a new line segment.
You have to be careful about your thresholds when the samples are too close to each other, so you might want to adjust the sensitivity when regarding samples fewer than 4-5 pixels away from each other.
This will give you a set of straight lines that will follow the original path fairly accurately.
If you require additional smoothing, or want to create a scalable vector graphic, then you can then curve-fit from the polyline. First, identify the kinks (the places in your polyline where the angle between one line and the next is sharp - e.g. anything over 140 degrees is considered a smooth curve, anything less than that is considered a kink) and break the polyline at those discontinuities. Then curve-fit each of these sub-sections of the original gesture to smooth them. This will have the effect of smoothing the smooth stuff and sharpening the kinks. (You could go further and insert small smooth corner fillets instead of these sharp joints to reduce the sharpness of the joins)
Brute force, but it may just achieve what you want.
您是否考虑过查看数据传入的时间，而不是尝试根据结果数据来执行此操作？如果鼠标明显停止或减慢，您可以使用自上次“扭结”（鼠标上次减慢时）以来的趋势来确定行进方向。如果用户转向新的方向，您将其称为扭结，否则，您将忽略当前的放缓趋势并开始等待下一个趋势。
Rather than trying to do this from the resultant data, have you considered looking at the timing of the data as it comes in? If the mouse stops or slows noticably, you use the trend since the last 'kink' (the last time the mouse slowed) to establish the direction of travel. If the user goes off in a new direction, you call it a kink, otherwise, you ignore the current slowing trend and start waiting for the next one.
好吧，一种方法是使用真正的曲线拟合算法。生成贝塞尔曲线（具有精确的端点，使用 Catmull-Rom 或类似的东西），然后优化并生成贝塞尔曲线。递归细分（使用距实际线点的距离作为成本度量）。不过，这对于您的用例来说可能太复杂了。
Well, one way would be to use a true curve-fitting algorithm. Generate a bezier curve (with exact endpoints, using Catmull-Rom or something similar), then optimize & recursively subdivide (using distance from actual line points as a cost metric). This may be too complicated for your use-case, though.
记录像素的绘制顺序。然后，计算“接近”但不“接近”的像素之间的斜率。我猜测像素（i）和像素（i+7）之间的斜率图可能会在曲线中的扭结周围表现出易于识别的“跳跃”。
Record the order the pixels are drawn in. Then, compute the slope between pixels that are "near" but not "close". I'm guessing a graph of the slope between pixel(i) and pixel(i+7) might exhibit easily identifable "jumps" around kinks in the curve.