Fri, 04 May 2018 21:43:46 +0300
night routes can be rarer
5 | 1 | from math import sqrt, hypot, radians, sin, cos, atan2 |
2 | ||
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
3 | class Location: |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
4 | def __init__(self, latitude, longitude): |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
5 | self.latitude, self.longitude = latitude, longitude |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
6 | def distance(self, other): |
5 | 7 | # https://stackoverflow.com/a/365853 |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
8 | a = sin(radians(self.latitude - other.latitude) / 2) ** 2 |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
9 | a += sin(radians(self.longitude - other.longitude) / 2) ** 2 * cos(radians(self.latitude)) * cos(radians(other.latitude)) |
5 | 10 | return 6371 * 2 * atan2(sqrt(a), sqrt(1 - a)) |
11 | def __repr__(self): | |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
12 | return '%s(%r, %r)' % (type(self).__name__, self.latitude, self.longitude) |
5 | 13 | def __str__(self): |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
14 | return '%.5f, %.5f' % (self.latitude, self.longitude) |
5 | 15 | @property |
16 | def x(self): | |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
17 | return self.latitude |
5 | 18 | @property |
19 | def y(self): | |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
20 | return self.longitude |
19
16fa9fb20b32
Lisätty pysäkkiryhmän aikataulunäkymä
Teemu Piippo <teemu@hecknology.net>
parents:
7
diff
changeset
|
21 | @property |
16fa9fb20b32
Lisätty pysäkkiryhmän aikataulunäkymä
Teemu Piippo <teemu@hecknology.net>
parents:
7
diff
changeset
|
22 | def link_to_map(self): |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
23 | return 'http://www.openstreetmap.org/#map=19/%f/%f' % (self.latitude, self.longitude) |
5 | 24 | |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
25 | class Ring: |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
26 | def __init__(self, container): |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
27 | self.container = container |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
28 | def __getitem__(self, i): |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
29 | while i < 0: |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
30 | i += len(self.container) |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
31 | while i >= len(self.container): |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
32 | i -= len(self.container) |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
33 | return self.container[i] |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
34 | def __iter__(self): |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
35 | return iter(self.container) |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
36 | def __len__(self): |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
37 | return len(self.container) |
5 | 38 | |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
39 | class Polygon: |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
40 | def __init__(self, *points): |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
41 | self.points = points |
5 | 42 | def __repr__(self): |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
43 | return '%s(%s)' % (type(self).__name__, ', '.join(map(repr, self.points))) |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
44 | def area(self): |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
45 | ring = Ring(self.points) |
5 | 46 | return sum( |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
47 | ring[i].x * ring[i + 1].y - ring[i + 1].x * ring[i].y |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
48 | for i in range(len(ring)) |
5 | 49 | ) / 2 |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
50 | def circumference(self): |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
51 | ring = Ring(self.points) |
5 | 52 | return sum( |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
53 | sqrt((ring[i + 1].x - ring[i].x)**2 + (ring[i + 1].y - ring[i].y)**2) |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
54 | for i in range(len(ring)) |
5 | 55 | ) |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
56 | def centroid(self): |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
57 | ring = Ring(self.points) |
5 | 58 | x = sum( |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
59 | (ring[i].x + ring[i + 1].x) * (ring[i].x * ring[i + 1].y - ring[i + 1].x * ring[i].y) |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
60 | for i in range(len(ring)) |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
61 | ) / 6 / self.area() |
5 | 62 | y = sum( |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
63 | (ring[i].y + ring[i + 1].y) * (ring[i].x * ring[i + 1].y - ring[i + 1].x * ring[i].y) |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
64 | for i in range(len(ring)) |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
65 | ) / 6 / self.area() |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
66 | return self.point_type()(x, y) |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
67 | def point_type(self): |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
68 | if len(self.points): |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
69 | return type(self.points[0]) |
5 | 70 | else: |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
71 | return Point |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
72 | def segments(self): |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
73 | ring = Ring(self.points) |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
74 | for i in range(len(ring)): |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
75 | yield LineSegment(ring[i], ring[i + 1]) |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
76 | def contains_point(self, point): |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
77 | outer_point = self.point_type()( |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
78 | min(point.x for point in self.points) - 1, |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
79 | min(point.y for point in self.points) - 1 |
5 | 80 | ) |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
81 | outer_segment = LineSegment(point, outer_point) |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
82 | intersections = 0 |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
83 | for segment in self.segments(): |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
84 | if segment.intersection(outer_segment) is not None: |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
85 | intersections += 1 |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
86 | return bool(intersections & 1) |
5 | 87 | |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
88 | class LineSegment: |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
89 | def __init__(self, p1, p2): |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
90 | self.p1, self.p2 = p1, p2 |
5 | 91 | def __repr__(self): |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
92 | return 'LineSegment(%r, %r)' % (self.p1, self.p2) |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
93 | def length(self): |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
94 | return hypot(self.p1.x - self.p2.x, self.p1.y - self.p2.y) |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
95 | def intersection(self, other): |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
96 | point_type = type(self.p1) |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
97 | x = (self.p1.x, self.p2.x, other.p1.x, other.p2.x) |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
98 | y = (self.p1.y, self.p2.y, other.p1.y, other.p2.y) |
5 | 99 | try: |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
100 | denominator = (x[0] - x[1]) * (y[2] - y[3]) - (y[0] - y[1]) * (x[2] - x[3]) |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
101 | Px = ((x[0] * y[1] - y[0] * x[1]) * (x[2] - x[3]) - (x[0] - x[1]) * (x[2] * y[3] - y[2] * x[3])) / denominator |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
102 | Py = ((x[0] * y[1] - y[0] * x[1]) * (y[2] - y[3]) - (y[0] - y[1]) * (x[2] * y[3] - y[2] * x[3])) / denominator |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
103 | distance = lambda n: hypot(Px - x[n], Py - y[n]) |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
104 | if max(distance(0), distance(1)) <= self.length() and max(distance(2), distance(3)) <= other.length(): |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
105 | return point_type(Px, Py) |
5 | 106 | else: |
107 | return None | |
108 | except ZeroDivisionError: | |
109 | return None | |
110 | ||
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
111 | class Point: |
5 | 112 | def __init__(self, x, y): |
113 | self.x, self.y = x, y | |
114 | def __repr__(self): | |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
115 | return 'Point(%r, %r)' % (self.x, self.y) |
5 | 116 | |
88
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
117 | A = Polygon( |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
118 | Point(2,3), |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
119 | Point(1,1), |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
120 | Point(4,0), |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
121 | Point(6,2), |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
122 | Point(4,4)) |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
123 | L1 = LineSegment(Point(1, 1), Point(-1, 5)) |
3b86597c5a88
major update, moved the map to an osm patch
Teemu Piippo <teemu@hecknology.net>
parents:
19
diff
changeset
|
124 | L2 = LineSegment(Point(1, 5), Point(5, 1)) |