geometry.py

Fri, 04 May 2018 21:43:46 +0300

author
Teemu Piippo <teemu@hecknology.net>
date
Fri, 04 May 2018 21:43:46 +0300
changeset 99
0726eb9bc9d1
parent 88
3b86597c5a88
permissions
-rw-r--r--

night routes can be rarer

5
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
1 from math import sqrt, hypot, radians, sin, cos, atan2
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
10 return 6371 * 2 * atan2(sqrt(a), sqrt(1 - a))
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
15 @property
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
18 @property
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
106 else:
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
107 return None
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
108 except ZeroDivisionError:
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
109 return None
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
112 def __init__(self, x, y):
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
113 self.x, self.y = x, y
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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
a65b680f1774 Paljon asioita
Teemu Piippo <teemu@hecknology.net>
parents:
diff changeset
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))

mercurial