source: subversion/applications/rendering/tilesAtHome_unstable/lines2curves.pl @ 10813

Last change on this file since 10813 was 10813, checked in by jttt, 11 years ago

Do not create bezier curvers for one segment lines. Workarounds #615

  • Property svn:executable set to *
File size: 15.5 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::Trig;
47use Math::Complex;
48use Math::Vec qw(:terse);
49
50my $min_angle = 0.5;
51my $min_scale = 0;
52#
53# transform linear paths to curves
54#
55# Globals...
56my $line_position = 0; # current line position in the svg file
57my @svg_lines = ();    # the lines from the svg file
58my %point_is_in;       # lookup for 'what ways is this point in?'
59my %to_transform;      # ways that need transforming
60
61my %no_bezier_ids;      # id with no bezier hinting
62
63# first pass, read in the svg lines, build the %point_is_in @svg_lines &
64# %to_transform structures.
65
66while (<>) {
67    my $line = $_;
68    $svg_lines[$line_position] = $line;
69    if ( $line =~ m{<use \s xlink:href=\"\#(?:way|area)_(\S+)\" \s class=\" # get path name
70                    .*no\-bezier.*/>$   
71                    }x ) {
72                $no_bezier_ids{$1} = 0;
73        }
74
75    if ( $line =~ m{(<path \s id=\"(?:way|area)_(\S+)\" \s d=\") # the prefix of the path
76                    ([^\"Z]+)                          # the core path itself
77                    (.*/>)$                           # the rest
78                   }x ) { # found a path
79        my $path_prefix    = $1;
80        my $path_id        = $2;
81        my $path_statement = $3;
82        my $path_suffix    = $4;
83        my $path_points_ref = path_points($path_statement);
84        foreach my $point (@$path_points_ref) {
85            my $point_index = $point->[0].$point->[1];
86            my $way_list_ref = $point_is_in{$point_index};
87            push @$way_list_ref, $path_prefix;
88            $point_is_in{$point_index} = $way_list_ref;
89        }
90
91        $to_transform{$path_prefix}
92            = [$line_position, $path_statement, $path_suffix, $path_points_ref, $path_id];
93       
94    }
95    $line_position++;
96}
97
98# Second pass, create the bezier curve versions of all the paths that have
99# been found.
100foreach my $path (keys %to_transform) {
101    # transform path_statment to curves
102    my $path_info_ref  = $to_transform{$path};
103    my $line_index     = $path_info_ref->[0];
104    my $path_statement = $path_info_ref->[1];
105    my $path_suffix    = $path_info_ref->[2];
106    my $path_id        = $path_info_ref->[4];
107
108    if (!exists $no_bezier_ids{$path_id}) {
109        my $transformed_path = curvify_path($path_statement, $path);
110        $svg_lines[$line_index] = $path.$transformed_path.$path_suffix."\n";
111    } else {
112        $svg_lines[$line_index] = $path.$path_statement.$path_suffix."\n";
113    }
114}
115
116# print out the transformed svg file.
117foreach my $line (@svg_lines) {
118    print $line;
119}
120
121
122# Get all the points in a path, removing duplicates along the way...
123sub path_points {
124    my $path_string = shift;
125    my $path_points_ref;
126
127    # there may be multiple moves in a path so get each one
128    my @move_segments = split /M\s*/, $path_string;
129
130    foreach my $move_segment (@move_segments) {
131        next if !$move_segment; # there is no pre-seg if there is only 1 'M'
132
133        # get all the points in the path
134        my $tmp_points_ref = [map [split /(?:\s|,)/, $_], split('L', $move_segment)];
135        # stop those occasional divide by zero errors...
136        push @$path_points_ref, @$tmp_points_ref; 
137    }
138
139    my $clean_points_ref = remove_duplicate_points($path_points_ref);
140    return $clean_points_ref;
141}
142
143sub remove_duplicate_points {
144    my $points_ref = shift;
145
146    my $clean_points_ref = [$points_ref->[0]];
147    shift @$points_ref;
148
149    foreach my $point_ref (@$points_ref) {
150        if (($point_ref->[0] == $clean_points_ref->[-1][0]) &&
151            ($point_ref->[1] == $clean_points_ref->[-1][1])) {
152                next;
153        }
154
155        push @$clean_points_ref, $point_ref;
156    }
157    if (scalar(@$points_ref)+1 != scalar(@$clean_points_ref)) {
158    } 
159    return $clean_points_ref;
160}
161
162sub remove_spur_points {
163    my $points_ref = shift;
164
165# spur points are when you get a way that goes A->B->A->C. The point 'B' is a
166# spur point & we don't like 'em.
167
168    my $clean_points_ref = [$points_ref->[0]];
169
170    shift @$points_ref;
171
172    for(my $i=0; $i < scalar(@$points_ref)-1; $i++) {
173        if ($clean_points_ref->[-1][0].$clean_points_ref->[-1][1] ne 
174            $points_ref->[$i+1][0].$points_ref->[$i+1][1]
175           ) {
176           push @$clean_points_ref, $points_ref->[$i];
177        }
178    }
179    push @$clean_points_ref, $points_ref->[-1];
180
181    return $clean_points_ref;
182}
183
184sub dup_points {
185    my $points_ref = shift;
186
187    foreach my $p (@$points_ref) {
188        my $count = 0;
189        foreach my $q (@$points_ref) {
190            if (join('', @$p) eq join('', @$q)) {
191                $count++;
192            }
193        }
194        if ($count > 1) {
195            return 1;
196        }
197    }
198    return;
199}
200
201# splits up the path string and calls 'from_lines_to_curves' appropriately to
202# build up a modified path string.
203sub curvify_path {
204    my $path_string = shift;
205    my $way_id      = shift;
206
207    my $tmp_string = $path_string;
208    $tmp_string =~ s/[^L]//g;
209
210    #
211    if (length($tmp_string) <= 1) { # cant do much with a single line segment
212        return $path_string;
213    }
214
215    my $bezier_path_string = q{};
216
217    # there may be multiple moves in a path so get each one
218    my @move_segments = split /M\s*/, $path_string;
219
220    foreach my $move_segment (@move_segments) {
221        my $postfix = q{};
222        next if !$move_segment; # there is no pre-seg if there is only 1 'M'
223
224        if ($move_segment =~ s/Z$//) {
225            $postfix = 'Z';
226        }
227        # get all the points in the path
228        my @path_points = map [split /(?:\s|,)/, $_], split('L', $move_segment);
229
230        if ($way_id =~ /way_/ && dup_points(\@path_points)) {
231            $bezier_path_string .= "$path_string"; 
232        } else {
233            $bezier_path_string 
234                .= 'M'.from_lines_to_curves(\@path_points, $way_id).$postfix;
235        }
236    }
237
238    return $bezier_path_string;
239}
240
241# When two ways meet at their ends, we need the second point in the 'other'
242# way to get good control points in the bezier curve. This just returns the
243# second point.
244sub get_second_point {
245    my ($start_point, $way_id) = @_;
246
247# uncomment the line below if you don't want the last segment in a way to be
248# curved when it meets another way.
249#
250#    return undef;
251    my $ways_ref = $point_is_in{$start_point};
252
253    if ($way_id =~ /area_/) { # areas are easier...
254        my $way_points = $to_transform{$way_id}->[3];
255        if ($way_points->[0][0].$way_points->[0][1] eq $start_point) {
256            return $way_points->[-1];
257        } else {
258            return $way_points->[0];
259        }
260    }
261
262    # now do normal ways...
263    # more than two ways meet - dont curve these.
264    return undef if @$ways_ref != 2;
265
266    my $otherway = ($ways_ref->[0] eq $way_id && $ways_ref->[1] ne $way_id)? $ways_ref->[1]: $ways_ref->[0];
267
268    # maybe there wasn't another way.
269    return undef if !$otherway;
270    # maybe this way has a loop in it.
271#    return undef if $otherway eq $way_id;
272
273    my $way_points = $to_transform{$otherway}->[3];
274   
275    if ($start_point eq $way_points->[0][0].$way_points->[0][1]) {
276        return $way_points->[1];
277    } elsif ($start_point eq $way_points->[-1][0].$way_points->[-1][1]) {
278        return $way_points->[-2];
279    }
280
281    return undef;
282}
283
284# heavy work here. Takes the set of points in a path and generates a bezier
285# version where appropriate.
286sub from_lines_to_curves {
287    my $points_ref = shift;
288    my $way_id     = shift;
289
290    my $cp_range = 0.5;
291    my $incremental_string = q{};
292
293    # Add a point at either end of the set of points to make it easy to
294    # generate the correct control points. If this way is standalone, then the
295    # ends of the way are extended straight back from the start/end
296    # points. If it joins another way, then use the second point in the
297    # other way as the end point. This will make ways that join connect
298    # smoothly - a point that Jochn Topf noticed.
299    #
300    my $start_point = $points_ref->[0][0].$points_ref->[0][1];
301    my $end_point   = $points_ref->[-1][0].$points_ref->[-1][1];
302
303    my $second_point_ref;
304   
305    if ($start_point eq $end_point && $way_id =~ /area_/) {
306        $second_point_ref = $points_ref->[-2];
307    } else {
308        $second_point_ref = get_second_point($start_point, $way_id);
309    }
310    if ($second_point_ref && $second_point_ref->[0].$second_point_ref->[1] ne
311    $points_ref->[1][0].$points_ref->[1][1]) {
312        unshift @$points_ref, $second_point_ref;
313    } else { # make a dummy point
314        unshift @$points_ref, [ $points_ref->[0][0]
315                               -$points_ref->[1][0] + $points_ref->[0][0],
316                                $points_ref->[0][1]
317                               -$points_ref->[1][1] + $points_ref->[0][1] ];
318    }
319
320    if ($start_point eq $end_point && $way_id =~ /area_/) {
321        $second_point_ref = $points_ref->[1];
322    } else {
323        $second_point_ref = get_second_point($end_point, $way_id);
324    }
325    if ($second_point_ref && $second_point_ref->[0].$second_point_ref->[1] ne
326    $points_ref->[-2][0].$points_ref->[-2][1]) {
327        push @$points_ref, $second_point_ref;
328    } else { # make a dummy point
329        push @$points_ref, [ $points_ref->[-1][0]
330                            +$points_ref->[-1][0] - $points_ref->[-2][0],
331                             $points_ref->[-1][1]
332                            +$points_ref->[-1][1] - $points_ref->[-2][1] ];
333    }
334
335    $points_ref = remove_duplicate_points(remove_spur_points($points_ref));
336    my $points_in_line     = scalar(@$points_ref);
337    my $current_point      = 0;
338    my $path_start_ref     = shift @$points_ref;
339    my $path_mid_ref       = $points_ref->[0];
340    my $path_end_ref       = $points_ref->[1];
341
342    my ($start_v,  $mid_v,  $end_v, $mid_start_v, $mid_end_v );
343    my ($start_mid_nv, $mid_start_nv, $mid_end_nv);
344    my $control_v;
345    my $control_scale;
346
347    my $pl;
348
349    foreach my $p (@$points_ref) {
350        $pl .= "\n\t".join(':', @$p);
351    }
352#    print "$way_id: $pl\n";
353
354    # go round each set of 3 points to generate the bezier points
355    while (@$points_ref >= 3) {
356        if (!$incremental_string) {
357            $incremental_string = q{ }.$path_mid_ref->[0].q{ }.$path_mid_ref->[1];
358        }
359
360        # decide to use real control points or not. We only use real control
361        # points if this node is only referenced in one 'way' or we are at the
362        # beginning/end of a way that only joins with one other way. This makes ways
363        # that 'T' sharp on the join.
364        if ( $path_start_ref->[0].$path_start_ref->[1] ne
365             $path_end_ref->[0].$path_end_ref->[1] &&
366             $path_mid_ref->[0].$path_mid_ref->[1] ne
367             $points_ref->[2][0].$points_ref->[2][1]
368             && ($way_id =~ /area_/
369            || @{$point_is_in{$path_mid_ref->[0].$path_mid_ref->[1]}} == 1
370            || (   $current_point == 0 
371                && @{$point_is_in{$path_mid_ref->[0].$path_mid_ref->[1]}} == 2)
372            || (   $current_point == $points_in_line-3 
373                && @{$point_is_in{$path_mid_ref->[0].$path_mid_ref->[1]}} == 2)
374            )) {
375
376#           print "\n\t->".join(':', @$path_start_ref)." ".join(':',
377#            @$path_mid_ref)." ".join(':',@$path_end_ref)."\n";
378            $incremental_string .= ' C ';
379            # work out control point 1 from $path_start, $path_mid & $path_end
380            $start_v = V($path_start_ref->[0], $path_start_ref->[1]);
381            $mid_v   = V($path_mid_ref->[0], $path_mid_ref->[1]);
382            $end_v   = V($path_end_ref->[0], $path_end_ref->[1]);
383            $start_mid_nv = U( ($mid_v-$start_v) + ($end_v-$mid_v) );
384            $mid_start_v = V($start_v->[0]-$mid_v->[0], $start_v->[1]-$mid_v->[1]);
385            $mid_end_v   = V($end_v->[0]-$mid_v->[0], $end_v->[1]-$mid_v->[1]);
386            $control_scale = normalise_cp($mid_start_v, $mid_end_v);
387            $control_v = $mid_v + V($start_mid_nv->ScalarMult($control_scale*abs($end_v-$mid_v)*$cp_range));
388
389            $incremental_string .= $control_v->[0].','.$control_v->[1].q{ };
390           
391            # move on a segment
392            $path_start_ref = $path_mid_ref;
393            $path_mid_ref   = $path_end_ref;
394            $path_end_ref   = $points_ref->[2];
395            shift @$points_ref;
396   
397#           print "\n\t-->".join(':', @$path_start_ref)." ".join(':',
398#            @$path_mid_ref)." ".join(':',@$path_end_ref)."\n";
399            # work out control point 2 from new $path_start, $path_mid & path_end
400            $start_v = V($path_start_ref->[0], $path_start_ref->[1]);
401            $mid_v   = V($path_mid_ref->[0], $path_mid_ref->[1]);
402            $end_v   = V($path_end_ref->[0], $path_end_ref->[1]);
403            $start_mid_nv = U( ($start_v-$mid_v) + ($mid_v-$end_v) );
404            $mid_start_v = V($start_v->[0]-$mid_v->[0], $start_v->[1]-$mid_v->[1]);
405            $mid_end_v   = V($end_v->[0]-$mid_v->[0], $end_v->[1]-$mid_v->[1]);
406                $control_scale = normalise_cp($mid_start_v, $mid_end_v);
407            $control_v = $mid_v + V($start_mid_nv->ScalarMult($control_scale * abs($mid_v-$start_v)*$cp_range));
408   
409            $incremental_string .= $control_v->[0].','.$control_v->[1].q{ };
410   
411            $incremental_string .= $path_mid_ref->[0].q{ }.$path_mid_ref->[1].q{ };
412        } else { # make a straight line segment
413            $incremental_string .= 'L'.$path_end_ref->[0].','.$path_end_ref->[1].q{};
414            # move on a segment
415            $path_start_ref = $path_mid_ref;
416            $path_mid_ref   = $path_end_ref;
417            $path_end_ref   = $points_ref->[2];
418            shift @$points_ref; 
419        }
420    }
421   
422    return $incremental_string;
423}
424
425
426# if the angle of the control point is less than 90 degrees return 0
427# between 90 & 180 degrees return a number between 0 & 1.
428sub normalise_cp {
429    my ($start_v, $end_v) = @_;
430    my $PI = pi;
431    my $max_angle = $PI/2; # 180degrees
432    my $angle = $start_v->InnerAngle($end_v);
433
434    $angle = Re($angle);
435   
436    if ($angle < $PI*$min_angle) { # too small, so
437        return 0;
438    }
439
440    # angle is between $PI/4 and $PI/2
441    $angle = $angle - $PI*$min_angle;
442    return $angle / ($PI*$min_angle);
443}
Note: See TracBrowser for help on using the repository browser.