11

I'm working on an automatic elevation contour labeling algorithm and one of the factors that I want to take into account when deciding the positions of labels is how "straight" a particular segment of a contour is. The more straight it is, the more likely it is to be used to place the label on that segment.

Each contour is represented by a polyline (but with points close together as to look like a curve to a naked eye). I then have a fixed length (width of a label), say, 100 pixels. If I randomly (or otherwise) choose a contour segment with the width of 100 pixels, I want to be able to get a numerical quantitative value of its straightness (say zero for a totally straight contour segment, some value larger than zero for a not so straight segment, and this value increasing as the crookedness increases).

Improve this question

5 Answers 5

Reset to default
9

The answer depends on context: if you will be investigating only a small (bounded) number of segments, you might be able to afford a computationally expensive solution. However, it seems likely that you will want to incorporate this calculation within some kind of search for good label points. If so, it is of great advantage to have a solution that either is computationally fast or allows for rapid updating of a solution when the candidate line segment is varied slightly.

For instance, suppose you intend to conduct a systematic search across an entire connected component of a contour, represented as a sequence of points P(0), P(1), ..., P(n). This would be done by initializing one pointer (index into the sequence) s = 0 ("s" for "start") and another pointer f (for "finish") to be the smallest index for which distance(P(f), P(s)) >= 100, and then advancing s for as long as distance(P(f), P(s+1)) >= 100. This produces a candidate polyline (P(s), P(s+1) ..., P(f-1), P(f)) for evaluation. Having evaluated its "fitness" to support a label, you would then increment s by 1 (s = s+1) and proceed to increase f to (say) f' and s to s' until once more a candidate polyline exceeding the minimum span of 100 is produced, represented as (P(s'), ... P(f), P(f+1), ..., P(f')). In so doing, vertices P(s)...P(s'-1) are dropped from the preceding candidate and vertices P(f+1), ..., P(f') are added to it. It is highly desirable that the fitness could be rapidly updated from knowledge of only the dropped and added vertices. (This scanning procedure would be continued until s = n; as usual, f must be allowed to "wrap around" from n back to 0 in the process.)

This consideration rules out many possible measures of fitness (sinuosity, tortuosity, etc.) that otherwise might be attractive. It leads us to favor L2-based measures, because they typically can be updated quickly when the underlying data change slightly. Taking an analogy with Principal Components Analysis suggests we entertain the following measure (where small is better, as requested): use the smaller of the two eigenvalues of the covariance matrix of the point coordinates. Geometrically, this is one measure of the "typical" side-to-side deviation of the vertices within the candidate section of the polyline. (One interpretation is that its square root is the smaller semi-axis of the ellipse representing the second moments of inertia of the polyline's vertices.) It will equal zero only for sets of collinear vertices; otherwise, it exceeds zero. It measures an average side-to-side deviation relative to the 100 pixel baseline created by the start and end of a polyline, and thereby has a simple interpretation.

Because the covariance matrix is only 2 by 2, the eigenvalues are quickly found by solving a single quadratic equation. Moreover, the covariance matrix is a sum of contributions from each of the vertices in a polyline. Thus, it is rapidly updated when points are dropped out or added, leading to a O(n) algorithm for an n-point contour: this will scale well to the highly detailed contours envisioned in the application.

Here is an example of the result of this algorithm. The black dots are vertices of a contour. The solid red line is the best candidate polyline segment of end-to-end length greater than 100 within that contour. (The visually obvious candidate in the upper right is not quite long enough.)

Figure

Improve this answer
4
  • Wow, you got me lost there :). You're right about the systematic search, I already have to do that to get the tangent of each polyline/polygon vertex (horizontal labels are preferred to vertical ones), so in theory I could extend this search to cover other measurements. BTW: did you produce the sample plot using an actual algorithm or manually?
    – Igor Brejc
    Oct 30, 2011 at 6:32
  • 1
    The illustration is real, but the implementation I used does not use the covariance updating procedure and therefore is not computationally optimal.
    – whuber
    Oct 30, 2011 at 16:32
  • 2
    The graph at end makes this answer even more awesome
    – Ragi Yaser Burhum
    Oct 30, 2011 at 16:59
  • 2
    Igor, I should mention that the label direction comes for free: it is given by the direction of the major axis of the ellipse (the eigenvector associated with the larger eigenvalue). You therefore can simultaneously search in an efficient manner for the best combination of label orientation and contour section linearity.
    – whuber
    Oct 30, 2011 at 19:47
4

In the computer graphics community, it is often necessary to find a bounding box around an object. Consequently, that is a well-studied problem, with fast algorithms. E.g., see Wikipedia's Minimum bounding box algorithms article. You could find the minimum-area rectangle surrounding your polyline, and then use the rectangle's aspect ratio, height/length. To get a more precise measure, you could look at the deviation of the polyline from the centerline of this bounding rectangle.

Improve this answer
4
  • 1
    I've thought about using min. bounding boxes, but I see two problems: a) computational complexity of calculating a box that would really be a minimum (and thus rotated), b) two curve segments with the same aspect ratio can have a very different curvature (think of a sinusoidal curve with the same amplitude but different wave periods).
    – Igor Brejc
    Oct 29, 2011 at 19:19
  • 1
    It's nice to see you here on the GIS pages, Joseph!
    – whuber
    Oct 30, 2011 at 1:57
  • 1
    Yes, I have your "Computational Geometry in C" book in my hands right now :)
    – Igor Brejc
    Oct 30, 2011 at 6:37
  • 1
    Thanks for the welcome, everyone! :-) I realize my suggestion is not the ideal measure, but the coding is off-the-shelf (if you have the right shelf). This type of problem has been studied quite a bit in manufacturing contexts, where they need to measure the quality of a machined part.
    – Joseph O'Rourke
    Oct 31, 2011 at 17:48
3

The easiest approach I can think of is the ratio between the actual path length between start and end and the shortest distance (straight line) from the start to the end point. Straight lines will have ratios close to one while very curved lines will have a very high ratio.

This should be a really easy to implement solution.

Update: As Mike noticed correctly, this would equal Sinuosity.

enter image description here

Improve this answer
5
  • Just what came to my mind after reading Rex's answer :)
    – Igor Brejc
    Oct 29, 2011 at 18:23
  • 5
    basically the reciprocal of sinuosity
    – Mike T
    Oct 29, 2011 at 20:24
  • exactly :) ....
    – underdark ♦
    Oct 29, 2011 at 20:29
  • 3
    You're right that this would be easy to implement, because updating the length as one searches for appropriate segments to label is as simple as adding and subtracting lengths between successive vertices. However, sinuosity doesn't effectively capture the sense in which a curve can depart from linearity. For instance, compare a semicircle of diameter 100 to a linear sequence of semicircles of diameter 1: both curves have the same sinuosity, but the side-to-side deviation of the first is 100 times that of the second (which would be nice base for a label).
    – whuber
    Oct 30, 2011 at 17:49
  • Take into account that if your polyline draw a circle this method will give you an infinite sinuosity which is perhaps not the desired result.
    – obchardon
    May 22, 2018 at 15:17
3

What if you place a circle of a particular radius on your contour line. That circle will intersect the contour line in at least two places. The straighter the line, the shorter the distance along the contour line between the two intersection points. The longer the distance along the contour line between the intersection points, the more curved the line is. If there are more than two intersection points, the contour line is way too curvy.

You could figure out what length would give the best indicator of straightness and set up a routine to step along each contour line and where it was straight enough, place the label.

I'm sure this doesn't help too much, and what I say in English is a lot more difficult in whatever programming language you're using, but it might be a start.

Improve this answer
1
  • Interesting idea. To make it more simple, you could calculate the ratio between the length of the segment on one side and the distance between the starting and ending points. It's not that precise, but it's quick to calculate. And your idea of using a circle would enable a more precise calculation of the straightness.
    – Igor Brejc
    Oct 29, 2011 at 18:21
1

By searching "curvature" and "polyline", I got this info How can I find the curvature of a polyline?. There he suggested using go back to definition of curvature - K= DF/Ds. Here by F he means phi, or T in wikipedia's notation here (http://en.wikipedia.org/wiki/Curvature).

Say you have a sequence three points, p0, p1 and p2. calculate distance s between p0 and p1, which is delta of s (Ds), assuming points are close enought to each other. Then you need delta of T (DT), which is change in unit tangential vector between p0 and p1. there may be sophisticated way but the crude method i can think of of to take two bectors p0->p1, p1->p2, normalize each to have length of one, then take vector subtraction of those two then determine the magnitude. That is DT. Division yield a curvature K0_1. grab p1, p2 and p3 to calculate K1_2 and so on.

I am wondering though if you get hold of the contour as a polyline, not as a rendered pixels. You said 100px so that make me worry a bit.

Improve this answer
2
  • Thanks for the link, I will have to study the maths behind it. I mentioned 100px simply because the rendered label text has a certain width (in pixels), 100px was just an example.
    – Igor Brejc
    Oct 29, 2011 at 18:58
  • Thinking of curvature is a nice idea. Curvature across heavily smoothed contour sections of sufficient length might be appropriate, but curvature itself is not: a single little zig-zag would have extremely high curvature, for instance, but would be inconsequential overall. Thus, in effect, you would be using some statistical summary of deviation from linearity across sections of the polyline. Among the likely candidates, curvature would be one of the more complex calculations to perform.
    – whuber
    Oct 30, 2011 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.