Avoid bitrot
[darcs-mirror-distanceview.git] / distanceview.py
1 #!/usr/bin/python
2 # -*- coding: utf-8 -*-
3
4 #
5 # © 2008 Joachim Breitner <mail@joachim-breitner.de>
6 #
7 #     This program is free software: you can redistribute it and/or modify
8 #     it under the terms of the GNU General Public License as published by
9 #     the Free Software Foundation, either version 3 of the License, or
10 #     (at your option) any later version.
11
12 #     This program is distributed in the hope that it will be useful,
13 #     but WITHOUT ANY WARRANTY; without even the implied warranty of
14 #     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 #     GNU General Public License for more details.
16
17 #     You should have received a copy of the GNU General Public License
18 #     along with this program.  If not, see <http://www.gnu.org/licenses/>.
19 #
20 #
21 # TODO:
22 # * Faster geometric algorithms (nearest point, containing facet)
23 # * Faster drawing (copying pixbufs to the X server)
24 # * Better morphs
25 # * Better interpolation
26
27
28
29 import pygtk
30 import gtk
31 import gtk.glade
32 import gobject
33
34 import numpy.oldnumeric
35 import math
36 import pickle
37 import time
38 import os.path
39
40 selection_distance = 10
41
42 # wir = (294, 123)
43 # feth = (256, 203)
44 # gack = (267, 252)
45 # mitte = (394, 186)
46 # vor_inge = (370,107)
47 # klspieli = (396, 32)
48 # fuchs = (318, 49)
49 # polizeimensch = (360,225)
50 # doelker = (390,261)
51 # preiss_oben = (402,324)
52 # tunnel = (518,356)
53
54 # start = mitte
55
56 # points = [
57 #     wir,
58 #     feth,
59 #     gack,
60 #     mitte,
61 #     klspieli,
62 #     fuchs,
63 #     polizeimensch,
64 #     doelker,
65 #     preiss_oben,
66 #     tunnel,
67 #     ]
68
69 # graph = [
70 #     (wir,feth),
71 #     (feth,gack),
72 #     (gack,polizeimensch),
73 #     (polizeimensch,mitte),
74 #     (mitte,vor_inge),
75 #     (vor_inge,klspieli),
76 #     (fuchs,klspieli),
77 #     (fuchs,wir),
78 #     (polizeimensch,doelker),
79 #     (doelker,preiss_oben),
80 #     (preiss_oben, tunnel),
81 #     (tunnel,mitte),
82 #     ]
83
84 def dist2((x1,y1),(x2,y2)):
85     return ((x1-x2)**2 + (y1-y2)**2)
86
87 def dist((x1,y1),(x2,y2)):
88     return math.sqrt((x1-x2)**2 + (y1-y2)**2)
89
90 def length((x1,y1)):
91     return math.sqrt(x1**2 + y1**2)
92
93 def dist((x1,y1),(x2,y2)):
94     return math.sqrt((x1-x2)**2 + (y1-y2)**2)
95
96 def find_footpoint((p1,p2),(x,y)):
97     if p1 == p2:
98         return p1
99
100     (x1,y1) = p1
101     (x2,y2) = p2
102     u = float((x-x1)*(x2-x1) + (y-y1)*(y2-y1)) / float((x1-x2)**2 + (y1-y2)**2)
103     return (int(round(x1 + u*(x2-x1))), int(round(y1 + u*(y2-y1))))
104
105 def convex(r, (r1,g1,b1), (r2,g2,b2)):
106     return ((1-r) * r1 + r * r2,
107             (1-r) * g1 + r * g2,
108             (1-r) * b1 + r * b2)
109
110 class Graph(object):
111     def __init__(self):
112         self.vertices = []
113         self.edges = []
114         self.start = None
115         
116         self.grid_size = 4 # 16x16
117
118     def dump(self):
119         return (self.vertices, self.edges, self.start)
120
121     def load(self,dump):
122         (self.vertices, edges, self.start) = dump
123         self.edges = []
124         for (p1,p2) in edges:
125             if p1 in self.vertices and p2 in self.vertices:
126                 self.edges.append((p1,p2))
127         self.update_edgelists()
128
129     def nearest_point(self, p):
130         if self.vertices:
131             return min(self.vertices, key=lambda v: dist2(p,v))
132         else:
133             return (-100,-100)
134
135     def near_edges(self,p):
136         return self.face_to_edges(self.on_face(p))
137
138     def on_face(self,p):
139         if not self.in_bbox(p, self.max_bounds):
140             if not self.outer_face:
141                 return self.vertices
142             else:
143                 return self.faces[self.outer_face]
144         
145         (x,y) = p
146         (bx,_,by,_) = self.max_bounds
147         for t, i in self.tri_grid[x - bx >>self.grid_size][ y - by >>self.grid_size]:
148             if self.in_triangle(p, t):
149                 return self.faces[i]
150
151         # not contained in anything? probably outer face:
152         return self.faces[self.outer_face]
153
154     def alone(self,p):
155         for (p1,p2) in self.edges:
156             if p1 == p or p2 == p:
157                 return False
158         return True
159
160     def delete_vertex(self,p):
161         assert self.alone(p)
162         self.vertices.remove(p)
163
164         self.update_edgelists()
165
166     def add_vertex(self, p):
167         assert not p in self.vertices
168         assert type(p[0]) == int and type(p[1]) == int
169         if not self.vertices:
170             self.start = p
171         self.vertices.append(p)
172
173         self.update_edgelists()
174
175     def has_edge(self,(p1,p2)):
176         return (p1,p2) in self.edges or (p2,p1) in self.edges
177
178     def toggle_edge(self,(p1,p2)):
179         assert p1 in self.vertices and p2 in self.vertices
180         if (p1,p2) in self.edges:
181             self.edges.remove((p1,p2))
182         elif (p2,p1) in self.edges:
183             self.edges.remove((p2,p1))
184         else:
185             self.edges.append((p1,p2))
186
187         self.update_edgelists()
188
189     def update_edgelists(self):
190         self.edgelist = {}
191         for (p1,p2) in self.edges:
192             self.edgelist.setdefault(p1,[]).append(p2)
193             self.edgelist.setdefault(p2,[]).append(p1)
194         for (x,y),l in self.edgelist.iteritems():
195             # order edges by direction, counterclockwise starting from North
196             l.sort(key = lambda (x2,y2): math.atan2(x2-x,y2-y))
197
198         self.faces = []
199         edges_to_try = self.edges[:]
200         edges_to_try.extend(map(lambda (p1,p2):(p2,p1), self.edges))
201         while edges_to_try:
202             (f,t) = edges_to_try[0]
203             first_edge = None
204             face = []
205             while (f,t) != first_edge:
206                 if not first_edge:
207                     first_edge = (f,t)
208                     #print "First edge: ",first_edge
209                 face.append(f)
210                 incoming_index = self.edgelist[t].index(f)
211                 next_index = (incoming_index-1) % len(self.edgelist[t])
212                 (f,t) = (t, self.edgelist[t][next_index])
213                 #print "to try: ", edges_to_try, " going to ",(f,t)
214                 edges_to_try.remove((f,t))
215             self.faces.append(face)
216
217         self.max_bounds = self.bbox(self.vertices)
218
219         self.bounding_boxes = map(self.bbox, self.faces)
220
221         self.outer_face = None
222         for i, face in enumerate(self.faces):
223             north_point_index = min(range(len(face)), key=lambda j:face[j][1])
224             north_point = face[north_point_index]
225             next = face[(north_point_index+1) % len(face) ]
226             prev = face[(north_point_index-1) % len(face) ]
227             if not self.turn_left(prev, north_point, next):
228                 # this seems to be an outer face
229                 self.outer_face = i
230
231         self.triangulation = []
232         for facenum, face in enumerate(self.faces):
233             # From http://citeseer.ist.psu.edu/164823.html
234             if facenum != self.outer_face:
235                 points = face[:]
236
237                 # Remove points with only one neighbor
238                 i = 0
239                 while i<len(points)-2:
240                     if points[i] == points[i+2]:
241                         points.remove(points[i+1])
242                     else:
243                         i += 1
244                 if len(points) <= 2:
245                     continue
246
247                 points.extend(points[:2])
248
249                 concaves = []
250                 for i in range(1,len(points)-1):
251                     if not self.turn_left(*points[i-1:i+2]):
252                         concaves.append(points[i])
253
254                 i = 2
255                 while points[i] != points[0]:
256                     is_ear = False
257                     if not concaves:
258                         is_ear = True
259                     else:
260                         if points[i-1] not in concaves:
261                             is_ear = True
262                             for p in concaves:
263                                 if self.in_triangle(p,points[i-2:i+1]):
264                                     is_ear = False
265                         else:
266                             is_ear = False
267
268                     if is_ear: # and len(points) > 4:
269                         self.triangulation.append((tuple(points[i-2:i+1]), facenum))
270                         if points[i-2] in concaves and\
271                             self.turn_left(points[i-3],points[i-2],points[i]):
272                             concaves.remove(points[i-2])
273                         if points[i] in concaves and\
274                             self.turn_left(points[i-2],points[i],points[i+1]):
275                             concaves.remove(points[i])
276                         points.remove(points[i-1])
277                         if points[i-1] == points[0]:
278                             i = i+1
279                     else:
280                         i = i+1
281                 self.triangulation.append((tuple(points[:3]), facenum))
282
283         # Square grid for faster location querys, hopefully
284         (bx1,bx2,by1,by2) = self.max_bounds
285         cache_width =  ((bx2-bx1+1 >> self.grid_size)+1)
286         cache_height = ((by2-by1+1 >> self.grid_size)+1)
287         self.tri_grid = [[[] for i in range(cache_height)] for j in range(cache_width)]
288         for td in self.triangulation:
289             (((x1,y1),(x2,y2),(x3,y3)),i) = td
290             for x in range( min(x1,x2,x3)-bx1 >> self.grid_size,
291                             (max(x1,x2,x3)-bx1 >> self.grid_size)+1):
292                 for y in range( min(y1,y2,y3)-by1 >> self.grid_size,
293                                 (max(y1,y2,y3)-by1 >> self.grid_size)+1):
294                     self.tri_grid[x][y].append(td)
295
296     def turn_left(self, (x1,y1), (x2,y2), (x3,y3)):
297         alpha = math.atan2((x2-x1),(y2-y1))
298         beta = math.atan2((x3-x1),(y3-y1))
299         return 0 <= beta-alpha <= math.pi or beta - alpha <= -math.pi
300
301     def bbox(self, points):
302         return (min(map(lambda (x,y):x, points)),
303                 max(map(lambda (x,y):x, points)),
304                 min(map(lambda (x,y):y, points)),
305                 max(map(lambda (x,y):y, points)))
306
307     def in_bbox(self,(x,y),(min_x,max_x,min_y,max_y)):
308         return min_x <= x <= max_x and min_y <= y <= max_y
309
310     def in_triangle(self,(x,y),((x1,y1),(x2,y2),(x3,y3))):
311         # from http://www.blackpawn.com/texts/pointinpoly/default.html
312
313         if ((x < x1 and x < x2 and x < x3) or\
314             (y < y1 and y < y2 and y < y3) or\
315             (x > x1 and x > x2 and x > x3) or\
316             (y > y1 and y > y2 and y > y3)):
317             return False
318
319         vx0 = x3-x1
320         vy0 = y3-y1
321         vx1 = x2-x1
322         vy1 = y2-y1
323         vx2 = x-x1
324         vy2 = y-y1
325
326         dot00 = vx0*vx0 + vy0*vy0
327         dot01 = vx0*vx1 + vy0*vy1
328         dot02 = vx0*vx2 + vy0*vy2
329         dot11 = vx1*vx1 + vy1*vy1
330         dot12 = vx1*vx2 + vy1*vy2
331         
332         denom = dot00 * dot11 - dot01 * dot01
333         u = dot11 * dot02 - dot01 * dot12
334         v = dot00 * dot12 - dot01 * dot02
335         return u * denom > 0 and v * denom > 0 and u + v < denom
336
337     def face_to_edges(self, face):
338         return zip(face, face[1:] + [face[0]])
339         
340         
341 class DistanceView:
342     def __init__(self):
343         self.width = 300
344         self.height = 300
345         
346         self.selected_d = 0
347         self.last_update = 0
348         self.point_selected = None
349         self.hover_vertex = None
350         self.last_mouse_pos_orig = None
351         self.last_mouse_pos_moved = None
352
353         self.image = gtk.DrawingArea()
354         self.image.set_size_request(self.width, self.height)
355         self.image.add_events(gtk.gdk.BUTTON_PRESS_MASK |
356                         gtk.gdk.BUTTON_RELEASE_MASK |
357                         gtk.gdk.EXPOSURE_MASK |
358                         gtk.gdk.POINTER_MOTION_MASK)
359         self.image.connect("expose_event",self.do_expose_event_orig)
360         self.image.connect("button_press_event",self.do_button_press_event)
361         self.image.connect("motion_notify_event",self.do_motion_orig)
362
363         self.moved = gtk.DrawingArea()
364         self.moved.set_size_request(self.width, self.height)
365         self.moved.add_events(gtk.gdk.BUTTON_PRESS_MASK |
366                         gtk.gdk.BUTTON_RELEASE_MASK |
367                         gtk.gdk.EXPOSURE_MASK |
368                         gtk.gdk.POINTER_MOTION_MASK)
369         self.moved.connect("expose_event",self.do_expose_event_moved)
370         self.moved.connect("motion_notify_event",self.do_motion_moved)
371
372         hbox1 = gtk.HBox()
373         hbox1.add(self.image)
374         hbox1.add(self.moved)
375
376         self.graph_edit = gtk.CheckButton('Edit graph')
377         edit_help = gtk.Button('Edit help')
378         edit_help.connect("clicked", self.show_edit_help)
379         vbox_edit = gtk.VBox()
380         vbox_edit.add(self.graph_edit)
381         vbox_edit.add(edit_help)
382
383         do_open = gtk.Button('Open Image')
384         do_save = gtk.Button('Save graph')
385         do_open.connect("clicked",self.do_open_dialog)
386         do_save.connect("clicked",self.do_save_dialog)
387         do_distance = gtk.Button('Calc Dist.')
388         do_heightmap = gtk.Button('Calc Heightmap.')
389         do_morph = gtk.Button('Calc Morph.')
390         do_all = gtk.Button('Calc All.')
391         do_distance.connect("clicked",self.do_recalc,self.recalc_distance)
392         do_heightmap.connect("clicked",self.do_recalc,self.recalc_heightmap)
393         do_morph.connect("clicked",self.do_recalc,self.recalc_morph)
394         do_all.connect("clicked",self.do_recalc,self.recalc_all)
395         self.do_buttons = [do_open, do_save, do_distance,
396                            do_heightmap, do_all, do_morph]
397
398         self.zoom = gtk.SpinButton()
399         self.zoom.set_range(1,10)
400         self.zoom.set_digits(1)
401         self.zoom.set_increments(1,1)
402         self.zoom.set_value(1)
403         hbox_zoom = gtk.HBox()
404         hbox_zoom.add(gtk.Label('Zoom:'))
405         hbox_zoom.add(self.zoom)
406
407         self.interpolator = gtk.combo_box_new_text()
408         self.interpolators = {
409                 'Stripes': self.interpolate_stripes,
410                 'Blocks': self.interpolate_blocks,
411                 'None': self.interpolate_none,
412             }
413         keys = self.interpolators.keys()
414         keys.sort()
415         for k in keys:
416             self.interpolator.append_text(k)
417         self.interpolator.set_active(keys.index('None'))
418         hbox_interpolator = gtk.HBox()
419         hbox_interpolator.add(gtk.Label('Interpolation:'))
420         hbox_interpolator.add(self.interpolator)
421
422         self.morpher = gtk.combo_box_new_text()
423         self.morphers = {
424                 'Radial': self.morpher_radial,
425                 'Radial (backw.)': self.morpher_radial_back,
426                 'Path int. (backw.)': self.morpher_int_back,
427             }
428         keys = self.morphers.keys()
429         keys.sort()
430         for k in keys:
431             self.morpher.append_text(k)
432         self.morpher.set_active(keys.index('Radial (backw.)'))
433         hbox_morpher = gtk.HBox()
434         hbox_morpher.add(gtk.Label('Morpher:'))
435         hbox_morpher.add(self.morpher)
436         
437         vbox_morph = gtk.VBox()
438         vbox_morph.add(hbox_interpolator)
439         vbox_morph.add(hbox_morpher)
440         vbox_morph.add(hbox_zoom)
441
442         self.penalty = gtk.SpinButton()
443         self.penalty.set_range(1,10)
444         self.penalty.set_increments(1,1)
445         self.penalty.set_value(2)
446         hbox_penalty = gtk.HBox()
447         hbox_penalty.add(gtk.Label('Offroad penalty:'))
448         hbox_penalty.add(self.penalty)
449
450         self.crossroads = gtk.CheckButton('Allow Roadcrossing')
451         self.crossroads.props.visible = False
452         self.crossroads.props.active = True
453
454         vbox_dist = gtk.VBox()
455         vbox_dist.add(hbox_penalty)
456         vbox_dist.add(self.crossroads)
457
458         self.show_heightmap = gtk.CheckButton('Show heightmap')
459         self.show_heightmap.props.active = True
460         self.show_heightmap.connect('toggled', self.queue_draw)
461         self.show_triangulation = gtk.CheckButton('Show Triangulation')
462         self.show_triangulation.props.active = False
463         self.show_triangulation.connect('toggled', self.queue_draw)
464         self.show_int_path = gtk.CheckButton('Show Integration path')
465         self.show_int_path.props.active = False
466         self.show_int_path.connect('toggled', self.queue_draw)
467         vbox_heightmap = gtk.VBox()
468         vbox_heightmap.add(self.show_heightmap)
469         vbox_heightmap.add(self.show_triangulation)
470         vbox_heightmap.add(self.show_int_path)
471
472         hbox2 = gtk.HBox()
473         hbox2.pack_start(do_open, expand=False)
474         hbox2.pack_start(do_save, expand=False)
475         hbox2.pack_start(vbox_edit, expand=False)
476         hbox2.pack_start(vbox_dist, expand=False)
477         hbox2.pack_start(do_distance, expand=False)
478         hbox2.pack_start(vbox_heightmap, expand=False)
479         hbox2.pack_start(do_heightmap, expand=False)
480         hbox2.pack_start(vbox_morph, expand=False)
481         hbox2.pack_start(do_morph, expand=False)
482         hbox2.pack_start(do_all, expand=False)
483         
484         self.status = gtk.Label("Status")
485         
486         self.progress = gtk.ProgressBar()
487         self.reset_progress()
488
489         hbox3 = gtk.HBox()
490         hbox3.add(self.status)
491         hbox3.add(self.progress)
492
493         self.slider = gtk.HScale()
494         self.slider.set_range(0,self.width+self.height)
495         self.slider.connect("change_value",self.do_change_value)
496
497         vbox = gtk.VBox()
498         vbox.pack_start(hbox1, expand=True,fill=True)
499         vbox.pack_start(self.slider, expand=False)
500         vbox.pack_start(hbox2, expand=False)
501         vbox.pack_start(hbox3, expand=False)
502
503         self.window = gtk.Window(gtk.WINDOW_TOPLEVEL)
504         self.window.add(vbox)
505
506         
507         self.graph = Graph()
508         self.d = None
509         self.pixbuf = None
510         self.pixbuf_heightmap = None
511         self.pixbuf_moved = None
512         self.moved_zoom = None
513         if os.path.exists('Ehbühl.jpg'):
514             self.load_files('Ehbühl.jpg')
515         else:
516             self.do_open_dialog(None)
517         
518         self.window.show_all()
519
520     def do_expose_event_orig(self, widget, event):
521         gc = widget.window.new_gc()
522         gc.set_clip_rectangle(event.area)
523
524         if self.pixbuf:
525             widget.window.draw_pixbuf(gc, self.pixbuf, 0,0,0,0,-1,-1)
526         if self.pixbuf_heightmap and self.show_heightmap.props.active:
527             widget.window.draw_pixbuf(gc, self.pixbuf_heightmap, 0,0,0,0,-1,-1)
528
529         if (self.d is not None
530                 and not self.graph_edit.props.active
531                 and not self.progress.props.sensitive):
532             pb = self.equilines()
533             widget.window.draw_pixbuf(gc, pb, 0,0,0,0,-1,-1)
534
535
536         cr = widget.window.cairo_create()
537         cr.rectangle(event.area.x, event.area.y, event.area.width, event.area.height)
538         cr.clip()
539
540         if self.show_triangulation.props.active:
541             for (p1,p2,p3),_ in self.graph.triangulation:
542                 cr.set_source_rgba(0.4,0.8,0.4,0.8)
543                 cr.move_to(*p1)
544                 cr.line_to(*p2)
545                 cr.line_to(*p3)
546                 cr.line_to(*p1)
547                 cr.fill()
548
549             if self.last_mouse_pos_orig:
550                 face = self.graph.on_face(self.last_mouse_pos_orig)
551                 if face != self.graph.faces[self.graph.outer_face]:
552                     cr.move_to(*face[-1])
553                     for p in face:
554                         cr.line_to(*p)
555                     cr.fill()
556         cr.set_source_rgba(0,0.8,0,0.8)
557         for (s,t) in self.graph.edges:
558             cr.move_to(*s)
559             cr.line_to(*t)
560             cr.stroke()
561         for x,y in self.graph.vertices:
562             cr.arc(x,y,2,0, 2 * math.pi)
563             cr.fill()
564         if self.graph.start:
565             x,y = self.graph.start
566             cr.arc(x,y,5,0, 2 * math.pi)
567             cr.fill()
568
569         if self.graph_edit.props.active and self.point_selected:
570             x,y = self.point_selected
571             cr.set_source_rgba(0,0,1,1)
572             cr.arc(x,y,5,0, 2 * math.pi)
573             cr.fill()
574         
575         if self.graph_edit.props.active and self.hover_vertex:
576             x,y = self.hover_vertex
577             cr.set_source_rgba(0.5,0.5,1,1)
578             cr.arc(x,y,5,0, 2 * math.pi)
579             cr.fill()
580
581             if self.point_selected:
582                 if self.graph.has_edge((self.point_selected, self.hover_vertex)):
583                     cr.set_source_rgba(1,0.5,0.5,1)
584                 else:
585                     cr.set_source_rgba(0.5,0.5,1,1)
586                 cr.move_to(*self.point_selected)
587                 cr.line_to(*self.hover_vertex)
588                 cr.stroke()
589         
590         if self.d is not None and self.last_mouse_pos_moved and self.show_int_path.props.active:
591             self.draw_integration_path(cr, self.last_mouse_pos_moved)
592
593     def do_expose_event_moved(self, widget, event):
594         gc = widget.window.new_gc()
595         gc.set_clip_rectangle(event.area)
596
597         if self.pixbuf_moved:
598             widget.window.draw_pixbuf(gc, self.pixbuf_moved, 0,0,0,0,-1,-1)
599
600         cr = widget.window.cairo_create()
601         cr.rectangle(event.area.x, event.area.y, event.area.width, event.area.height)
602         cr.clip()
603         
604         if self.moved_zoom:
605             z = self.moved_zoom
606
607             cr.set_source_rgba(0,1,1,0.5)
608             cr.arc(self.width/2, self.height/2, self.selected_d / z, 0, 2 * math.pi)
609             cr.stroke()
610
611     def do_button_press_event(self, widget, event):
612         if self.graph_edit.props.active:
613             p = (int(round(event.x)),int(round(event.y)))
614             n = self.graph.nearest_point(p)
615
616             if event.button == 1:  #left click
617                 if dist(n,p) > selection_distance:
618                     self.graph.add_vertex(p)
619                     self.point_selected = p
620                 else:
621                     if self.point_selected == n:
622                         self.point_selected = None
623                     else:
624                         self.point_selected = n
625
626             elif event.button == 2: #middle click
627                 if dist(n,p) > selection_distance:
628                     pass
629                 else:
630                     self.graph.start = n
631
632             elif event.button == 3: #right click
633                 if self.point_selected:
634                     if dist(n,p) > selection_distance:
635                         self.graph.add_vertex(p)
636                         self.graph.toggle_edge((self.point_selected, p))
637                         self.point_selected = p
638                     else:
639                         if n == self.point_selected:
640                             if self.graph.alone(n):
641                                 self.graph.delete_vertex(n)
642                                 self.point_selected = None
643                                 self.hover_vertex = None
644                         else:
645                             self.graph.toggle_edge((self.point_selected, n))
646             self.queue_draw()
647
648     def do_recalc(self, widget, func):
649         func()
650         self.queue_draw()
651
652     def equilines(self):
653         assert self.d is not None
654         pb = gtk.gdk.Pixbuf(gtk.gdk.COLORSPACE_RGB, True, 8, self.width, self.height)
655         el = pb.get_pixels_array()
656         my_d = self.selected_d
657         (s_x,s_y) = self.graph.start
658         for x in range(max(0,int(s_x - my_d)), min(int(s_x + my_d), self.width)):
659             for y in range(max(0,int(s_y - my_d)), min(int(s_y + my_d), self.height)):
660                 if my_d - 5 <=  self.d[x,y] <= my_d + 5:
661                     a = 150
662                     if my_d - 3 <=  self.d[x,y] <= my_d + 3:
663                         a = 200
664                         if my_d - 1 <=  self.d[x,y] <= my_d + 1:
665                             a = 250
666                     el[y,x,:]= (0,255,255,a)
667         return pb
668
669     def do_motion_orig(self, widget, event):
670         if 0<=event.x<self.width and 0<=event.y<self.height:
671             p = (int(round(event.x)),int(round(event.y)))
672
673             self.last_mouse_pos_orig = p
674             if self.d is not None:
675                 self.selected_d = self.d[p]
676                 self.status.set_text("(%d,%d): %d" % (event.x, event.y, self.selected_d))
677                 self.slider.set_value(self.selected_d)
678                
679                 if not self.graph_edit.props.active and not self.progress.props.sensitive:
680                     self.queue_draw()
681             else:
682                 self.status.set_text("(%d,%d)" % (event.x, event.y))
683         
684             if self.graph_edit.props.active:
685                 n = self.graph.nearest_point(p)
686                 if dist(n,p) < selection_distance:
687                     self.hover_vertex = n
688                 else:
689                     self.hover_vertex = None
690                 self.queue_draw()
691     
692     def do_motion_moved(self, widget, event):
693         if 0<=event.x<self.width and 0<=event.y<self.height:
694             p = (int(round(event.x)),int(round(event.y)))
695             self.last_mouse_pos_moved = p
696
697             c = (self.width/2, self.height/2)
698             z = self.zoom.get_value()
699             value = int(dist(c,p)*z)
700             self.selected_d = value
701             self.status.set_text("(%d,%d): %d" % (event.x, event.y, self.selected_d))
702
703             self.queue_draw()
704     
705     def do_change_value(self, widget, scroll, value):
706         value = int(value)
707         if value != self.selected_d:
708             self.selected_d = value
709             self.status.set_text("Selected: %d" % (self.selected_d))
710             self.queue_draw()
711         return False
712
713     def show_edit_help(self,widget):
714         help = gtk.MessageDialog(parent = self.window,
715                                 type = gtk.MESSAGE_INFO,
716                                 buttons = gtk.BUTTONS_OK)
717         help.props.text = '''Graph editing:
718 Left click to select/unselect a vertex.
719 Left click any where else to add a new vertex.
720 Middle click to select center vertex.
721 Right click on the selected vertex to delete it, if it has no edges anymore.
722 Right click on another vertex to add or remove the edge.
723 Right click anywhere to add a vertex and an edge in one go.'''
724         help.run()
725         help.destroy()
726
727     def queue_draw(self, widget=None):
728         self.image.queue_draw()
729         self.moved.queue_draw()
730
731     def update_gui(self, pulse=False):
732         now = time.time()
733         if now - self.last_update > 0.1:
734             if pulse:
735                 self.progress.pulse()
736             while gtk.events_pending():
737                 gtk.main_iteration(False)
738             self.last_update = now
739
740     def prepare_progress(self):
741         self.progress.props.sensitive = True
742         self.progress.set_text('')
743         self.progress.set_fraction(0)
744
745         for button in self.do_buttons:
746             button.props.sensitive = False
747
748     def reset_progress(self):
749         self.progress.props.sensitive = False
750         self.progress.set_text('...idle...')
751         self.progress.set_fraction(0)
752
753         for button in self.do_buttons:
754             button.props.sensitive = True
755         self.update_gui()
756
757     def recalc_distance(self):
758         penalty = self.penalty.get_value_as_int() 
759         far = penalty * (self.width + self.height)
760
761         self.prepare_progress()
762         self.progress.set_text('Preparing array')
763         self.update_gui()
764         d = self.d = numpy.oldnumeric.zeros((self.width,self.height), 'i')
765         for (x,y) in self.all_points(True):
766             d[x,y] = far
767
768         d[self.graph.start] = 0
769         todo = set([self.graph.start])
770
771         # unoptimized djikstra
772         self.progress.set_text('Djikstra')
773         self.update_gui()
774
775         while todo:
776             s = min(todo, key=lambda e: d[e])
777             todo.remove(s)
778             for t in ([t for (s2,t) in self.graph.edges if s2 == s ] +
779                       [t for (t,s2) in self.graph.edges if s2 == s ]):
780                 if d[s] + dist(s,t) < d[t]:
781                     d[t] = d[s] + dist(s,t)
782                     todo.add(t)
783             if self.crossroads.props.active:
784                 for t in self.graph.vertices:
785                     if s != t and d[s] + penalty * dist(s,t) < d[t]:
786                         d[t] = d[s] + penalty * dist(s,t)
787                         todo.add(t)
788
789             self.update_gui(True)
790
791         self.progress.set_text('Off-Graph')
792         for (x,y) in self.all_points(True):
793             p = (x,y)
794             if d[p]==far:
795                 # Nearest footpoint:
796                 #(p1,p2) = min(graph, key = lambda e: dist2(find_footpoint(e,p),p))
797                 #footpoint = find_footpoint((p1,p2),p)
798                 #if d[footpoint] == far:
799                 #    d[footpoint] = min(d[p1] + dist(p1,footpoint),
800                 #                       d[p2] + dist(p2,footpoint))
801                 #d[p] = d[footpoint] + dist(p, footpoint)
802
803                 # Best point:
804                 #d[x,y] = min(map (lambda p1: d[p1] + 5*dist(p,p1), points))
805
806                 # Best footpoint:
807                 #for (p1,p2) in self.graph.edges:
808                 for (p1,p2) in self.graph.near_edges(p):
809                     f = find_footpoint((p1,p2),p)
810                     c = min((p1,p2), key=lambda pt: d[pt])
811                     d[p] = min(d[p], d[c] + dist(c,f) + penalty * dist(f,p))
812
813         self.reset_progress()
814     
815     def recalc_heightmap(self):
816         if self.d is None:
817             self.recalc_distance()
818         d = self.d
819         
820         self.prepare_progress()
821         self.progress.set_text('Recreating heightmap')
822         self.pixbuf_heightmap = gtk.gdk.Pixbuf(gtk.gdk.COLORSPACE_RGB, True, 8, self.width, self.height)
823         i = self.pixbuf_heightmap.get_pixels_array()
824         #i = numpy.oldnumeric.zeros((self.height,self.width,4), 'B')
825         for (x,y) in self.all_points(True):
826             a = 255 - min(d[x,y]//3,255)
827             i[y,x,:]= (255,0,0,a)
828
829         self.reset_progress()
830
831     def recalc_morph(self):
832         if self.d is None:
833             self.recalc_distance()
834
835         choice = self.morpher.get_active_text()
836         self.morphers[choice]()
837
838     def interpolate(self, f):
839         self.prepare_progress()
840         self.progress.set_text('Calculating morphed Image')
841         m = numpy.oldnumeric.zeros((self.height,self.width,3),'B')
842         o = self.pixbuf.get_pixels_array()
843
844         choice = self.interpolator.get_active_text()
845         self.interpolators[choice](o, m, f)
846
847         self.m = m
848         self.pixbuf_moved = gtk.gdk.pixbuf_new_from_array(m, gtk.gdk.COLORSPACE_RGB, 8)
849         self.reset_progress()
850
851     def path_integrate(self, p, callback=lambda x,y: None):
852         d = self.d
853         z = self.zoom.get_value()
854         step = 20
855         (cx,cy) = (self.width/2, self.height/2)
856         (sx,sy) = self.graph.start
857         
858         (x,y) = p
859         size = dist(p,(cx,cy)) * z
860         if size > step:
861             tx = sx + (float(x-cx) / size * step)
862             ty = sy + (float(y-cy) / size * step)
863             i = 0
864             l = 1000
865             while d[int(tx),int(ty)] < size and i < 50 and l>step/20:
866                 callback(tx,ty)
867                 (dx,dy) = self.gradient((int(tx),int(ty)))
868                 l = length((dx,dy))
869                 if l > step/20:
870                     tx += dx
871                     ty += dy
872                 else:
873                     i = 100
874                 i += 1
875             return (tx,ty)
876         else:
877             tx = sx +x -cx
878             ty = sy +y -cy
879             return (tx,ty)
880
881     def draw_integration_path(self, cr, p):
882         (sx,sy) = self.graph.start
883         cr.set_source_rgba(0,0,0,1)
884         cr.move_to(sx,sy)
885         tx,ty = self.path_integrate(p, callback = cr.line_to)
886         cr.line_to(tx,ty)
887         cr.stroke()
888
889     def morpher_int_back(self):
890         self.prepare_progress()
891         self.progress.set_text('Calculating transformation')
892         m = numpy.oldnumeric.zeros((self.height,self.width,3),'B')
893         o = self.pixbuf.get_pixels_array()
894
895         d = self.d
896         z = self.zoom.get_value()
897         step = 20
898         (cx,cy) = (self.width/2, self.height/2)
899         (sx,sy) = self.graph.start
900         for (x,y) in self.all_points(True):
901             p = (x,y)
902             (tx,ty) = self.path_integrate(p)
903             if 0<= tx < self.width and 0<= ty < self.height:
904                 m[y,x] = (ty,tx)
905
906         self.m = m
907         self.pixbuf_moved = gtk.gdk.pixbuf_new_from_array(m, gtk.gdk.COLORSPACE_RGB, 8)
908         self.reset_progress()
909
910     def d_float(self,x,y):
911         d = self.d
912         ix = int(x)
913         iy = int(y)
914         rx = x%1
915         ry = y%1
916         return ( (1-rx) * (1-ry) * d[ix  ,iy  ] +
917                  (  rx) * (1-ry) * d[ix+1,iy  ] +
918                  (  rx) * (  ry) * d[ix+1,iy+1] +
919                  (1-rx) * (  ry) * d[ix  ,iy+1] )
920
921     def o_float(self,o,x,y):
922         ix = int(x)
923         iy = int(y)
924         rx = x%1
925         ry = y%1
926         return ( (1-rx) * (1-ry) * o[ix  ,iy  ][0] +
927                  (  rx) * (1-ry) * o[ix+1,iy  ][0] +
928                  (  rx) * (  ry) * o[ix+1,iy+1][0] +
929                  (1-rx) * (  ry) * o[ix  ,iy+1][0],
930                  (1-rx) * (1-ry) * o[ix  ,iy  ][1] +
931                  (  rx) * (1-ry) * o[ix+1,iy  ][1] +
932                  (  rx) * (  ry) * o[ix+1,iy+1][1] +
933                  (1-rx) * (  ry) * o[ix  ,iy+1][1],
934                  (1-rx) * (1-ry) * o[ix  ,iy  ][2] +
935                  (  rx) * (1-ry) * o[ix+1,iy  ][2] +
936                  (  rx) * (  ry) * o[ix+1,iy+1][2] +
937                  (1-rx) * (  ry) * o[ix  ,iy+1][2]   )
938
939     def p_radial(self,dx,dy,dl,r):
940         (sx,sy) = self.graph.start
941         tx = sx + (float(dx * r) / dl)
942         ty = sy + (float(dy * r) / dl)
943         return (tx,ty)
944
945     def d_radial(self,dx,dy,dl,r):
946         (tx,ty) = self.p_radial(dx,dy,dl,r)
947         
948         if 0<= tx < self.width-1 and 0<= ty < self.height-1:
949             return self.d_float(tx,ty)
950         else:
951             return 10000
952
953     def morpher_radial_back(self):
954         self.prepare_progress()
955         self.progress.set_text('Calculating transformation')
956         m = numpy.oldnumeric.zeros((self.height,self.width,3),'B')
957         o = self.pixbuf.get_pixels_array()
958
959         z = self.zoom.get_value()
960         (cx,cy) = (self.width/2, self.height/2)
961         for (x,y) in self.all_points(True):
962             (dx, dy) = (x - cx,y - cy)
963             dlen = length((dx,dy))
964             size = dlen * z
965             if size>0.05:
966                 search_min = 0.0
967                 search_max = 1000.0
968
969                 while search_max - search_min > 0.1:
970                     search_half = (search_max + search_min)/2
971                     if self.d_radial(dx, dy, dlen, search_half) < size:
972                         search_min = search_half
973                     else:
974                         search_max = search_half
975
976                 (ox,oy) = self.p_radial(dx,dy,dlen,search_max)
977
978                 if 0<= ox < self.width - 1 and 0<= oy < self.height - 1:
979                     m[y,x] = self.o_float(o, oy,ox)
980             else:
981                 m[y,x] = o[self.graph.start]
982         
983         self.m = m
984         self.pixbuf_moved = gtk.gdk.pixbuf_new_from_array(m, gtk.gdk.COLORSPACE_RGB, 8)
985         self.reset_progress()
986
987     def morpher_radial(self):
988         self.prepare_progress()
989         self.progress.set_text('Calculating transformation')
990         f = numpy.oldnumeric.zeros((self.width,self.height,2),'i')
991         d = self.d
992         z = self.zoom.get_value()
993         (cx,cy) = (self.width/2, self.height/2)
994         (sx,sy) = self.graph.start
995         for (x,y) in self.all_points(True):
996             p = (x,y)
997             size = dist(p,self.graph.start) * z
998             if size>0.05:
999                 npx = int(round(cx + (x-sx)*d[p]/size))
1000                 npy = int(round(cy + (y-sy)*d[p]/size))
1001                 if 0<= npx < self.width and 0<= npy < self.height:
1002                     if f[npx,npy] != (0,0):
1003                         # already something there, make sure the closer one wins
1004                         if dist(f[npx,npy], self.graph.start) *z > size:
1005                             f[npx,npy,:] = (y,x)
1006                     else:
1007                         f[npx,npy,:] = (y,x)
1008             else:
1009                 f[cx,cy,:] = (y,x)
1010         self.reset_progress()
1011
1012         self.interpolate(f)
1013
1014     def interpolate_blocks(self, o, m, f):
1015         for (x,y) in self.all_points(True):
1016             if f[x, y] != (0,0):
1017                 m[y,x] = o[f[x,y]]
1018                 #print "Pixel data found directly"
1019             else:
1020                 done = False
1021                 for i in range(1,3):
1022                     for tx in range(x-i,x+i+1):
1023                         if 0 <= tx < self.width:
1024                             for ty in range(y-i,y+i+1):
1025                                 if 0 <= ty < self.height:
1026                                     if f[tx, ty] != (0,0):
1027                                         m[y,x] = o[f[tx,ty]]
1028                                         done = True
1029                                         #print "Neighboring pixels asked (%d)" % i
1030                                         break
1031                         if done: break
1032                     if done: break
1033                 #if not done:
1034                 #    print "Could not find pixel to take color from."
1035                 #    m[y,x] = (255,255,0)
1036
1037     def interpolate_stripes(self, o, m, f):
1038         for x in range(self.width):
1039             self.progress.set_fraction(float(x)/float(self.width))
1040             self.update_gui()
1041
1042             prev = None
1043             for y in range(self.height):
1044                 if f[x,y] != (0,0):
1045                     m[y,x] = o[f[x,y]]
1046                     if prev:
1047                         for my in range(prev+1,y):
1048                             m[my,x] = convex(
1049                                         float(my-prev)/float(y-prev),
1050                                         m[prev,x],
1051                                         m[y,x])
1052                     prev = y
1053
1054     def interpolate_none(self, o, m, f):
1055         for (x,y) in self.all_points(True):
1056             if f[x,y] != (0,0):
1057                 m[y,x] = o[f[x,y]]
1058
1059     def gradient(self,(x,y)):
1060         # Sobel filter:
1061         d = self.d
1062         factor = 1
1063         return( factor * float(   (d[x+1,y-1] + 2*d[x+1,y] + d[x+1,y+1])
1064                                  -(d[x-1,y-1] + 2*d[x-1,y] + d[x-1,y+1]) )/8,
1065                 factor *      (   (d[x-1,y+1] + 2*d[x,y+1] + d[x+1,y+1])
1066                                  -(d[x-1,y-1] + 2*d[x,y-1] + d[x+1,y-1]) )/8)
1067     
1068     def all_points(self, progress=False):
1069         for x in range(self.width):
1070             if progress:
1071                 self.progress.set_fraction(float(x)/float(self.width))
1072                 self.update_gui()
1073             for y in range(self.height):
1074                 yield (x,y)
1075
1076     def recalc_all(self):
1077         self.recalc_distance()
1078         self.recalc_heightmap()
1079         self.recalc_morph()
1080
1081     def do_open_dialog(self, widget):
1082         dialog = gtk.FileChooserDialog(title = "Open Image",
1083                                parent =  self.window,
1084                                action = gtk.FILE_CHOOSER_ACTION_OPEN,
1085                                buttons = (gtk.STOCK_OK, gtk.RESPONSE_ACCEPT,
1086                                           gtk.STOCK_CANCEL, gtk.RESPONSE_REJECT))
1087
1088         if dialog.run():
1089             filename = dialog.get_filename()
1090             if filename:
1091                 self.load_files(filename)
1092         dialog.destroy()
1093
1094     def do_save_dialog(self, widget):
1095         assert self.filename, "No file open at the moment"
1096         self.save_files()
1097         help = gtk.MessageDialog(parent = self.window,
1098                                 type = gtk.MESSAGE_INFO,
1099                                 buttons = gtk.BUTTONS_OK)
1100         help.props.text = 'Graph and calculated data saved'
1101         help.run()
1102         help.destroy()
1103
1104     def load_files(self, filename):
1105         self.pixbuf = gtk.gdk.pixbuf_new_from_file(filename)
1106         self.width = self.pixbuf.props.width
1107         self.height = self.pixbuf.props.height
1108         self.filename = filename
1109
1110         self.graph = Graph()
1111         self.d = None
1112         self.pixbuf_heightmap = None
1113         self.pixbuf_moved = None
1114         self.moved_zoom = None
1115
1116         if os.path.exists(filename+'.graph'):
1117             data = pickle.load(file(filename + '.graph'))
1118             self.graph.load(data)
1119
1120         if os.path.exists(filename+'.data'):
1121             data = pickle.load(file(filename + '.data'))
1122
1123             if 'd' in data:
1124                 self.d = data['d']
1125             if 'i' in data and data['i']:
1126                 self.pixbuf_heightmap = gtk.gdk.pixbuf_new_from_array(data['i'],
1127                                          gtk.gdk.COLORSPACE_RGB, 8)
1128             if 'm' in data and data['m']:
1129                 self.m = data['m']
1130                 self.pixbuf_moved = gtk.gdk.pixbuf_new_from_array(self.m,
1131                         gtk.gdk.COLORSPACE_RGB, 8)
1132             if 'mz' in data and data['mz']:
1133                 self.moved_zoom = data['mz']
1134                 self.zoom.set_value(float(self.moved_zoom))
1135             if 'penalty' in data:
1136                 self.penalty.set_value(data['penalty'])
1137         
1138         self.queue_draw()
1139
1140     def save_files(self):
1141         assert self.filename, "No file open at the moment"
1142
1143         pickle.dump(self.graph.dump(), file(self.filename + '.graph','w'))
1144
1145         data = {}
1146         data['d'] = self.d
1147         if self.pixbuf_heightmap:
1148             data['i'] = self.pixbuf_heightmap.get_pixels_array()
1149         if self.pixbuf_moved:
1150             # Re-extracting pixel array from RGB without alpha
1151             # and re-inserting causes strange shift, so let’s
1152             # remember the array directly
1153             data['m'] = self.m
1154         data['mz'] = self.moved_zoom
1155         data['penalty'] = self.penalty.get_value_as_int()
1156
1157         pickle.dump(data, file(self.filename + '.data','w'))
1158
1159     def main(self):
1160         gtk.main()
1161
1162
1163 if __name__ == "__main__":
1164     app = DistanceView()
1165     app.main()
1166
1167 # vim:ts=4:sw=4:sts=4:et
1168