source: subversion/applications/rendering/osmarender4/lines2curves.pl @ 3616

Last change on this file since 3616 was 3616, checked in by frederik, 13 years ago

hack to allow selective disabling of bezier curve hinting

  • Property svn:executable set to *
File size: 16.4 KB
Line 
1#!/usr/bin/perl -w
2#-----------------------------------------------------------------------------
3#
4#  lines2curves.pl
5#
6#  This script post-processes Osmarender output to change lines in ways
7#  into smooth bezier curves.
8#
9#  This is what it does for each 'way' in the svg:
10#     For each pair of lines that make up the way it will replace the two
11#     straight lines with an appropriate bezier curve through the point where
12#     the lines meet. Appropriate means that the curve is more localised the
13#     sharper the angle, and if the angle is less than 90 degrees it will not
14#     introduce a bezier curve.
15#
16#     If the point where the lines meet has other ways that meet it (at a 'T'
17#     junction for example), it leaves those segments untouched (i.e. it
18#     doesn't introduce curves for those segments).
19#
20#  Call it as follows:
21#
22#    lines2curves.pl YourSVGFile.svg >SVGFileWithCurves.svg
23#
24#-----------------------------------------------------------------------------
25#
26#  Copyright 2007 by Barry Crabtree
27#
28#  This program is free software; you can redistribute it and/or modify
29#  it under the terms of the GNU General Public License as published by
30#  the Free Software Foundation; either version 2 of the License, or
31#  (at your option) any later version.
32#
33#  This program is distributed in the hope that it will be useful,
34#  but WITHOUT ANY WARRANTY; without even the implied warranty of
35#  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
36#  GNU General Public License for more details.
37#
38#  You should have received a copy of the GNU General Public License
39#  along with this program; if not, write to the Free Software
40#  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA
41#
42#-----------------------------------------------------------------------------
43
44use strict;
45use Carp;
46use Math::Complex;
47use Math::Vec qw(:terse);
48
49my $min_angle = 0.5;
50my $min_scale = 0;
51#
52# transform linear paths to curves
53#
54# Globals...
55my $line_position = 0; # current line position in the svg file
56my @svg_lines = ();    # the lines from the svg file
57my %point_is_in;       # lookup for 'what ways is this point in?'
58my %to_transform;      # ways that need transforming
59my $last_way_href;     # way last referenced in <use>
60
61# first pass, read in the svg lines, build the %point_is_in @svg_lines &
62# %to_transform structures.
63while (<>) {
64    my $line = $_;
65    $svg_lines[$line_position] = $line;
66    if ( $line =~ m{(<path \s id=\"(?:way|area)_\w+\" \s d=\") # the prefix of the path
67                    ([^\"Z]+)                          # the core path itself
68                    (.*/>)$                           # the rest
69                   }x ) { # found a path
70        my $path_prefix    = $1;
71        my $path_statement = $2;
72        my $path_suffix    = $3;
73        my $path_points_ref = path_points($path_statement);
74        foreach my $point (@$path_points_ref) {
75            my $point_index = $point->[0].$point->[1];
76            my $way_list_ref = $point_is_in{$point_index};
77            push @$way_list_ref, $path_prefix;
78            $point_is_in{$point_index} = $way_list_ref;
79        }
80
81        $to_transform{$path_prefix}
82            = [$line_position, $path_statement, $path_suffix, $path_points_ref];
83       
84    }
85    # the following is a hack to find out whether anything that references
86    # a path is tagged with bezier="no"; if so, then the path is removed
87    # from the "to_transform" list. This makes the assumption that osmarender
88    # creates only the plain path and the one with "t" at the end.
89    elsif ($line =~ /<(use|textPath) xlink:href="#((way|area)_\w+)"/)
90    {
91        my $path_prefix = "<path id=\"$2\" d=\""; # need this as hash key
92        if ($line =~ /bezier="no"/)
93        {
94            # if the "use" or "textPath" contains the bezier=no right away,
95            # then drop it from the to_transform list
96            delete $to_transform{$path_prefix};
97        }
98        else
99        {
100            # otherwise save the id in case the following line is a
101            # <line> instruction that belatedly adds the bezier=no
102            $last_way_href = $path_prefix;
103        }
104    }
105    elsif ($line =~ /<line.*bezier="no"/)
106    {
107        # a <line> instruction with bezier=no; drop previously referenced
108        # way from to_transfrom list
109        delete $to_transform{$last_way_href} if defined($last_way_href);
110    }
111    else
112    {
113        # make sure that the <line> only affects an <use> that came directly
114        # before.
115        undef $last_way_href;
116    }
117    $line_position++;
118}
119
120# Second pass, create the bezier curve versions of all the paths that have
121# been found.
122foreach my $path (keys %to_transform) {
123    # transform path_statment to curves
124    my $path_info_ref  = $to_transform{$path};
125    my $line_index     = $path_info_ref->[0];
126    my $path_statement = $path_info_ref->[1];
127    my $path_suffix    = $path_info_ref->[2];
128
129    my $transformed_path = curvify_path($path_statement, $path);
130    $svg_lines[$line_index] = $path.$transformed_path.$path_suffix."\n";
131}
132
133# print out the transformed svg file.
134foreach my $line (@svg_lines) {
135    print $line;
136}
137
138
139# Get all the points in a path, removing duplicates along the way...
140sub path_points {
141    my $path_string = shift;
142    my $path_points_ref;
143
144    # there may be multiple moves in a path so get each one
145    my @move_segments = split /M\s*/, $path_string;
146
147    foreach my $move_segment (@move_segments) {
148        next if !$move_segment; # there is no pre-seg if there is only 1 'M'
149
150        # get all the points in the path
151        my $tmp_points_ref = [map [split /(?:\s|,)/, $_], split('L', $move_segment)];
152        # stop those occasional divide by zero errors...
153        push @$path_points_ref, @$tmp_points_ref; 
154    }
155
156    my $clean_points_ref = remove_duplicate_points($path_points_ref);
157    return $clean_points_ref;
158}
159
160sub remove_duplicate_points {
161    my $points_ref = shift;
162
163    my $clean_points_ref = [$points_ref->[0]];
164    shift @$points_ref;
165
166    foreach my $point_ref (@$points_ref) {
167        if ($point_ref->[0].$point_ref->[1] eq
168                $clean_points_ref->[-1][0].$clean_points_ref->[-1][1]) {
169                next;
170        }
171
172        push @$clean_points_ref, $point_ref;
173    }
174    if (scalar(@$points_ref)+1 != scalar(@$clean_points_ref)) {
175    } 
176    return $clean_points_ref;
177}
178
179sub remove_spur_points {
180    my $points_ref = shift;
181
182# spur points are when you get a way that goes A->B->A->C. The point 'B' is a
183# spur point & we don't like 'em.
184
185    my $clean_points_ref = [$points_ref->[0]];
186
187    shift @$points_ref;
188
189    for(my $i=0; $i < scalar(@$points_ref)-1; $i++) {
190        if ($clean_points_ref->[-1][0].$clean_points_ref->[-1][1] ne 
191            $points_ref->[$i+1][0].$points_ref->[$i+1][1]
192           ) {
193           push @$clean_points_ref, $points_ref->[$i];
194        }
195    }
196    push @$clean_points_ref, $points_ref->[-1];
197
198    return $clean_points_ref;
199}
200
201sub dup_points {
202    my $points_ref = shift;
203
204    foreach my $p (@$points_ref) {
205        my $count = 0;
206        foreach my $q (@$points_ref) {
207            if (join('', @$p) eq join('', @$q)) {
208                $count++;
209            }
210        }
211        if ($count > 1) {
212            return 1;
213        }
214    }
215    return;
216}
217
218# splits up the path string and calls 'from_lines_to_curves' appropriately to
219# build up a modified path string.
220sub curvify_path {
221    my $path_string = shift;
222    my $way_id      = shift;
223
224    my $tmp_string = $path_string;
225    $tmp_string =~ s/[^L]//g;
226
227    #
228    if (length($tmp_string) < 1) { # cant do much with a single line segment
229        return $path_string;
230    }
231
232    my $bezier_path_string = q{};
233
234    # there may be multiple moves in a path so get each one
235    my @move_segments = split /M\s*/, $path_string;
236
237    foreach my $move_segment (@move_segments) {
238        my $postfix = q{};
239        next if !$move_segment; # there is no pre-seg if there is only 1 'M'
240
241        if ($move_segment =~ s/Z$//) {
242            $postfix = 'Z';
243        }
244        # get all the points in the path
245        my @path_points = map [split /(?:\s|,)/, $_], split('L', $move_segment);
246
247        if ($way_id =~ /way_/ && dup_points(\@path_points)) {
248            $bezier_path_string .= "M$path_string$postfix"; 
249        } else {
250            $bezier_path_string 
251                .= 'M'.from_lines_to_curves(\@path_points, $way_id).$postfix;
252        }
253    }
254
255    return $bezier_path_string;
256}
257
258# When two ways meet at their ends, we need the second point in the 'other'
259# way to get good control points in the bezier curve. This just returns the
260# second point.
261sub get_second_point {
262    my ($start_point, $way_id) = @_;
263
264# uncomment the line below if you don't want the last segment in a way to be
265# curved when it meets another way.
266#
267#    return undef;
268    my $ways_ref = $point_is_in{$start_point};
269
270    if ($way_id =~ /area_/) { # areas are easier...
271        my $way_points = $to_transform{$way_id}->[3];
272        if ($way_points->[0][0].$way_points->[0][1] eq $start_point) {
273            return $way_points->[-1];
274        } else {
275            return $way_points->[0];
276        }
277    }
278
279    # now do normal ways...
280    # more than two ways meet - dont curve these.
281    return undef if @$ways_ref != 2;
282
283    my $otherway = ($ways_ref->[0] eq $way_id && $ways_ref->[1] ne $way_id)? $ways_ref->[1]: $ways_ref->[0];
284
285    # maybe there wasn't another way.
286    return undef if !$otherway;
287    # maybe this way has a loop in it.
288#    return undef if $otherway eq $way_id;
289
290    my $way_points = $to_transform{$otherway}->[3];
291   
292    if ($start_point eq $way_points->[0][0].$way_points->[0][1]) {
293        return $way_points->[1];
294    } elsif ($start_point eq $way_points->[-1][0].$way_points->[-1][1]) {
295        return $way_points->[-2];
296    }
297
298    return undef;
299}
300
301# heavy work here. Takes the set of points in a path and generates a bezier
302# version where appropriate.
303sub from_lines_to_curves {
304    my $points_ref = shift;
305    my $way_id     = shift;
306
307    my $cp_range = 0.5;
308    my $incremental_string = q{};
309
310    # Add a point at either end of the set of points to make it easy to
311    # generate the correct control points. If this way is standalone, then the
312    # ends of the way are extended straight back from the start/end
313    # points. If it joins another way, then use the second point in the
314    # other way as the end point. This will make ways that join connect
315    # smoothly - a point that Jochn Topf noticed.
316    #
317    my $start_point = $points_ref->[0][0].$points_ref->[0][1];
318    my $end_point   = $points_ref->[-1][0].$points_ref->[-1][1];
319
320    my $second_point_ref;
321   
322    if ($start_point eq $end_point && $way_id =~ /area_/) {
323        $second_point_ref = $points_ref->[-2];
324    } else {
325        $second_point_ref = get_second_point($start_point, $way_id);
326    }
327    if ($second_point_ref && $second_point_ref->[0].$second_point_ref->[1] ne
328    $points_ref->[1][0].$points_ref->[1][1]) {
329        unshift @$points_ref, $second_point_ref;
330    } else { # make a dummy point
331        unshift @$points_ref, [ $points_ref->[0][0]
332                               -$points_ref->[1][0] + $points_ref->[0][0],
333                                $points_ref->[0][1]
334                               -$points_ref->[1][1] + $points_ref->[0][1] ];
335    }
336
337    if ($start_point eq $end_point && $way_id =~ /area_/) {
338        $second_point_ref = $points_ref->[1];
339    } else {
340        $second_point_ref = get_second_point($end_point, $way_id);
341    }
342    if ($second_point_ref && $second_point_ref->[0].$second_point_ref->[1] ne
343    $points_ref->[-2][0].$points_ref->[-2][1]) {
344        push @$points_ref, $second_point_ref;
345    } else { # make a dummy point
346        push @$points_ref, [ $points_ref->[-1][0]
347                            +$points_ref->[-1][0] - $points_ref->[-2][0],
348                             $points_ref->[-1][1]
349                            +$points_ref->[-1][1] - $points_ref->[-2][1] ];
350    }
351
352    $points_ref = remove_duplicate_points(remove_spur_points($points_ref));
353    my $points_in_line     = scalar(@$points_ref);
354    my $current_point      = 0;
355    my $path_start_ref     = shift @$points_ref;
356    my $path_mid_ref       = $points_ref->[0];
357    my $path_end_ref       = $points_ref->[1];
358
359    my ($start_v,  $mid_v,  $end_v, $mid_start_v, $mid_end_v );
360    my ($start_mid_nv, $mid_start_nv, $mid_end_nv);
361    my $control_v;
362    my $control_scale;
363
364    my $pl;
365
366    foreach my $p (@$points_ref) {
367        $pl .= "\n\t".join(':', @$p);
368    }
369#    print "$way_id: $pl\n";
370
371    # go round each set of 3 points to generate the bezier points
372    while (@$points_ref >= 3) {
373        if (!$incremental_string) {
374            $incremental_string = q{ }.$path_mid_ref->[0].q{ }.$path_mid_ref->[1];
375        }
376
377        # decide to use real control points or not. We only use real control
378        # points if this node is only referenced in one 'way' or we are at the
379        # beginning/end of a way that only joins with one other way. This makes ways
380        # that 'T' sharp on the join.
381        if ( $path_start_ref->[0].$path_start_ref->[1] ne
382             $path_end_ref->[0].$path_end_ref->[1] &&
383             $path_mid_ref->[0].$path_mid_ref->[1] ne
384             $points_ref->[2][0].$points_ref->[2][1]
385             && ($way_id =~ /area_/
386            || @{$point_is_in{$path_mid_ref->[0].$path_mid_ref->[1]}} == 1
387            || (   $current_point == 0 
388                && @{$point_is_in{$path_mid_ref->[0].$path_mid_ref->[1]}} == 2)
389            || (   $current_point == $points_in_line-3 
390                && @{$point_is_in{$path_mid_ref->[0].$path_mid_ref->[1]}} == 2)
391            )) {
392
393#           print "\n\t->".join(':', @$path_start_ref)." ".join(':',
394#            @$path_mid_ref)." ".join(':',@$path_end_ref)."\n";
395            $incremental_string .= ' C ';
396            # work out control point 1 from $path_start, $path_mid & $path_end
397            $start_v = V($path_start_ref->[0], $path_start_ref->[1]);
398            $mid_v   = V($path_mid_ref->[0], $path_mid_ref->[1]);
399            $end_v   = V($path_end_ref->[0], $path_end_ref->[1]);
400            $start_mid_nv = U( ($mid_v-$start_v) + ($end_v-$mid_v) );
401            $mid_start_v = V($start_v->[0]-$mid_v->[0], $start_v->[1]-$mid_v->[1]);
402            $mid_end_v   = V($end_v->[0]-$mid_v->[0], $end_v->[1]-$mid_v->[1]);
403            $control_scale = normalise_cp($mid_start_v, $mid_end_v);
404            $control_v = $mid_v + V($start_mid_nv->ScalarMult($control_scale*abs($end_v-$mid_v)*$cp_range));
405
406            $incremental_string .= $control_v->[0].','.$control_v->[1].q{ };
407           
408            # move on a segment
409            $path_start_ref = $path_mid_ref;
410            $path_mid_ref   = $path_end_ref;
411            $path_end_ref   = $points_ref->[2];
412            shift @$points_ref;
413   
414#           print "\n\t-->".join(':', @$path_start_ref)." ".join(':',
415#            @$path_mid_ref)." ".join(':',@$path_end_ref)."\n";
416            # work out control point 2 from new $path_start, $path_mid & path_end
417            $start_v = V($path_start_ref->[0], $path_start_ref->[1]);
418            $mid_v   = V($path_mid_ref->[0], $path_mid_ref->[1]);
419            $end_v   = V($path_end_ref->[0], $path_end_ref->[1]);
420            $start_mid_nv = U( ($start_v-$mid_v) + ($mid_v-$end_v) );
421            $mid_start_v = V($start_v->[0]-$mid_v->[0], $start_v->[1]-$mid_v->[1]);
422            $mid_end_v   = V($end_v->[0]-$mid_v->[0], $end_v->[1]-$mid_v->[1]);
423                $control_scale = normalise_cp($mid_start_v, $mid_end_v);
424            $control_v = $mid_v + V($start_mid_nv->ScalarMult($control_scale * abs($mid_v-$start_v)*$cp_range));
425   
426            $incremental_string .= $control_v->[0].','.$control_v->[1].q{ };
427   
428            $incremental_string .= $path_mid_ref->[0].q{ }.$path_mid_ref->[1].q{ };
429        } else { # make a straight line segment
430            $incremental_string .= 'L'.$path_end_ref->[0].','.$path_end_ref->[1].q{};
431            # move on a segment
432            $path_start_ref = $path_mid_ref;
433            $path_mid_ref   = $path_end_ref;
434            $path_end_ref   = $points_ref->[2];
435            shift @$points_ref; 
436        }
437    }
438   
439    return $incremental_string;
440}
441
442
443# if the angle of the control point is less than 90 degrees return 0
444# between 90 & 180 degrees return a number between 0 & 1.
445sub normalise_cp {
446    my ($start_v, $end_v) = @_;
447    my $PI = 3.1415926;
448    my $max_angle = $PI/2; # 180degrees
449    my $angle = $start_v->InnerAngle($end_v);
450
451    $angle = Re($angle);
452   
453    if ($angle < $PI*$min_angle) { # too small, so
454        return 0;
455    }
456
457    # angle is between $PI/4 and $PI/2
458    $angle = $angle - $PI*$min_angle;
459    return $angle / ($PI*$min_angle);
460}
Note: See TracBrowser for help on using the repository browser.