2

What are the mathematical constraints required for a polyline, i.e., a piecewise linear curve, to appear as a smooth curve to human vision? I've discovered one document that specifies only that the change of direction at each vertex must be less than 3°. It seems to me that there also needs to be a limit on degrees turned per curve length, but that's a simple enhancement.

My main question is about how the maximum direction change angle is affected by segment length. If you have two long segments connected at 3° then the change will be (to my eye anyway) much more visible than a 3° angle between short segments. Is anyone aware of any studies in this area?

In case it matters, my application is in polyline generalization for GIS.

James Ashton
  • 21
  • 1
  • A piecewise linear curve is not smooth by standard definitions. Smoothness usually implies $C^k$ or $G^k$, $k>0$. It may look smooth, when seen at a specific scale, but you can always fund a scale such that it is not. If you want true smoothness use a spline for example. – lightxbulb Feb 28 '19 at 08:32
  • @lightxbulb For drawing your spline will, at the end of the day, be discretized into linear pieces too, the amount of which is again a difficult decision to make. What the asker is after, though, is some kind of quality measurement for determining *how* linear is *too* linear based on human perception of the result. That sure is dependent on a lot of things, but saying "use a smooth curve" is only shifting away the problem. – Christian Rau Mar 01 '19 at 00:51
  • @ChristianRau There's a very big difference between a piecewise linear curve and a smooth curve even if you discretize the smooth one. The point is that at a specific scale your piecewise linear curve will not be smooth, whereas the same does not hold for the smooth curve as long as you discretize correctly, thus his requirement is not achievable unless he specifies that he cares only about a specific scale. Considering the fact that he mentioned GIS, I assumed he cares about things like the curve remaining smooth under different scales, I just wanted to point out that it is infeasible then. – lightxbulb Mar 01 '19 at 01:06
  • I would just assume they want to know how to determine what will look smooth at a given scale. Presumably when the user zooms in or out, the scale will change and they will want to recalculate the curve. – user1118321 Mar 01 '19 at 03:54
  • 1
    Yes, I'm trying to come up with a definition of smooth for a line generalisation algorithm in GIS. Beziers are drawn in Postscript and PDF renderers by repeatedly dividing them up into straight line segments (using the flattenpath operator) until the maximum distance error of the approximation is small enough. The problem with this distance-based approach is that curves with jagged fine detail can remain jagged after flattening. Splines are more complex and GIS software tends to handle only polylines. And splines are converted back to polyines for rendering anyway. – James Ashton Mar 01 '19 at 10:07
  • @JamesAshton So I take it you're using splines after all and not piecewise linear curves. In that case smoothness of the discretized curve can be achieved by simply making sure that the discretisation has subpixel precision. If you want to relax that you can use additionally curvature information to decide how densely to discretize, then you can even quantify the error of your approximation. – lightxbulb Mar 01 '19 at 12:06
  • Having a point on the curve that maps to screen coordinates $(x,y)$ find the closest intersection with the lines $x+1, x-1, y+1, y-1$, thus you will get pixel precision, you can even go as far as subpixel precision, this is obviously unnecessary where the curvature is low enough (curvature = 0 - you can do a straight line). So it's a mix of screen space length and curvature (note that curvature changes at different scales, as does length). – lightxbulb Mar 01 '19 at 12:15
  • 1
    @lightxbulb I'm still using polylines. This is printed graphics, so very high res, up to 2540ppi. Think printing coasts, roads, or contours with curves that are smooth to human vision. Often the source polyline is very detailed, but GIS "generalization" means removing unnecessary detail with minimum inaccuracy. – James Ashton Mar 02 '19 at 08:04
  • @JamesAshton So you simply want to remove vertices/edges such that you minimize the error? Take a look at this: https://www.sciencedirect.com/science/article/pii/S092577210800028X – lightxbulb Mar 02 '19 at 19:11

0 Answers0