Úloha 1

Koľko kilometrov pásky s nápisom polícia by bolo potrebných na ohraničenie/izoláciu karanténnej oblasti všetkých miest na Slovensku kde sa vykystlo aspoň 7 potvrdených prípadov?

Údaje o testovaných osobách sú dostupné na stránke Národného centra zdravotníckych informácií, mapu Slovenska z OpenStreetMap môžete stiahnuť z geofabrik.de (podstatné sú body 1001-1003, t.j. veľkomestá,mestá a dediny viď formát dát GIS-OSM)

Takisto môžeme využiť už vytvorenú mapu mapa.covid.chat mapa.covid.chat

Konvexný obal množiny bodov

Konvexny obal

Spracovanie dát z mapy

Pomocou DevTools si môžeme zo stránky vybrať vektorový obrázok v SVG formáte. Ten v jazyku Python spracujeme knižnicou xmltodict DevTools na stránke mapa.covid.chat

In [4]:
import xmltodict

with open('covid.svg') as fd:
    data = xmltodict.parse(fd.read())
print("Počet kružníc: {}".format(len(data['svg']['circle'])))   
print(data['svg']['circle'][0])
print(data['svg']['circle'][4])
Počet kružníc: 201
OrderedDict([('@cx', '59'), ('@cy', '340'), ('@stroke-width', '5.897911347683685'), ('@r', '9.610530170360718'), ('@stroke-location', 'inside'), ('@class', 'recovered')])
OrderedDict([('@cx', '167'), ('@cy', '491'), ('@stroke-width', '2'), ('@r', '6.661574496518876'), ('@stroke-location', 'inside'), ('@class', 'infected')])

Spracovanie bodov znázorňujúcich potvrdené prípady:

In [5]:
body = []
for circle in data['svg']['circle']:
    if circle['@class'] == 'infected': #zaujimaju nas len potvrdene pripady
        body.append((int(circle['@cx']), int(circle['@cy']), float(circle['@r'])))
        print(circle['@cx'], circle['@cy'], circle['@r'])
374 517 6.661574496518876
167 491 6.661574496518876
202 501 4.902686155817854
337 503 5.897911347683685
349 483 4.902686155817854
120 454 7.872569573006374
175 464 5.897911347683685
189 465 4.902686155817854
206 471 4.902686155817854
278 449 4.902686155817854
273 466 7.3053723116357085
363 461 4.902686155817854
82 423 30
104 435 5.897911347683685
125 444 4.902686155817854
204 432 4.902686155817854
109 410 5.897911347683685
143 399 4.902686155817854
135 403 6.661574496518876
194 410 4.902686155817854
300 396 5.897911347683685
490 405 4.902686155817854
515 394 4.902686155817854
46 371 5.897911347683685
69 372 4.902686155817854
68 387 5.897911347683685
111 384 6.661574496518876
195 385 4.902686155817854
212 388 4.902686155817854
260 379 7.872569573006374
278 389 4.902686155817854
302 383 4.902686155817854
316 378 4.902686155817854
548 373 4.902686155817854
35 358 4.902686155817854
59 340 6.661574496518876
66 343 5.897911347683685
91 351 4.902686155817854
136 365 7.3053723116357085
158 362 4.902686155817854
151 350 4.902686155817854
168 361 8.385355093802978
208 346 5.897911347683685
303 365 6.661574496518876
316 357 6.661574496518876
612 357 5.897911347683685
634 348 4.902686155817854
991 353 4.902686155817854
164 320 4.902686155817854
217 335 4.902686155817854
408 339 4.902686155817854
213 300 8.85691004683183
264 287 4.902686155817854
274 309 4.902686155817854
313 290 8.385355093802978
405 298 4.902686155817854
450 304 4.902686155817854
919 290 5.897911347683685
113 270 4.902686155817854
110 283 4.902686155817854
127 276 4.902686155817854
215 283 4.902686155817854
223 259 4.902686155817854
301 279 4.902686155817854
316 270 4.902686155817854
313 281 4.902686155817854
344 278 4.902686155817854
382 263 4.902686155817854
453 262 9.708058467453561
442 268 4.902686155817854
629 275 6.661574496518876
659 267 4.902686155817854
700 270 4.902686155817854
705 283 4.902686155817854
823 268 5.897911347683685
835 266 13.245139146012749
1005 258 4.902686155817854
165 255 4.902686155817854
195 247 4.902686155817854
206 237 4.902686155817854
213 255 5.897911347683685
286 233 4.902686155817854
351 233 4.902686155817854
357 250 8.385355093802978
477 252 4.902686155817854
542 241 7.872569573006374
956 255 5.897911347683685
250 205 4.902686155817854
247 229 4.902686155817854
250 217 10.468808467829213
270 205 5.897911347683685
274 213 4.902686155817854
299 204 4.902686155817854
356 228 4.902686155817854
396 214 5.897911347683685
711 203 6.661574496518876
778 229 5.897911347683685
800 209 5.897911347683685
849 218 4.902686155817854
913 217 6.661574496518876
955 206 5.897911347683685
275 198 4.902686155817854
286 188 6.661574496518876
405 188 4.902686155817854
420 191 5.897911347683685
558 177 4.902686155817854
683 194 4.902686155817854
692 193 4.902686155817854
744 187 6.661574496518876
833 187 9.29582269536737
917 197 4.902686155817854
922 196 4.902686155817854
325 157 10.097960754938644
412 169 6.661574496518876
412 157 4.902686155817854
462 152 7.872569573006374
484 167 7.3053723116357085
538 166 9.29582269536737
662 173 7.872569573006374
816 158 5.897911347683685
884 156 7.872569573006374
316 142 4.902686155817854
366 140 7.872569573006374
380 125 8.85691004683183
672 122 4.902686155817854
691 135 4.902686155817854
350 106 5.897911347683685
391 101 4.902686155817854
415 91 5.897911347683685
432 116 6.661574496518876
453 111 4.902686155817854
520 101 5.897911347683685
733 104 4.902686155817854
839 106 10.468808467829213
860 92 4.902686155817854
898 91 4.902686155817854
904 96 4.902686155817854
388 65 5.897911347683685
395 77 4.902686155817854
263 303 4.902686155817854
363 449 4.902686155817854
116 419 6.661574496518876
127 404 4.902686155817854
215 308 4.902686155817854
546 258 6.661574496518876
686 150 7.3053723116357085
808 159 5.897911347683685
765 139 6.661574496518876
109 439 4.902686155817854
399 301 4.902686155817854
623 171 5.897911347683685
381 146 5.897911347683685
537 87 6.661574496518876
199 428 5.897911347683685
167 417 4.902686155817854
450 294 5.897911347683685
837 309 4.902686155817854
381 251 4.902686155817854
945 237 4.902686155817854
1000 191 4.902686155817854
402 131 4.902686155817854
405 81 4.902686155817854
524 141 4.902686155817854
985 295 4.902686155817854
64 273 4.902686155817854
842 202 4.902686155817854
781 195 4.902686155817854
412 119 4.902686155817854
351 238 4.902686155817854
744 125 4.902686155817854
836 242 4.902686155817854
262 190 4.902686155817854
264 198 4.902686155817854
319 286 4.902686155817854
404 188 6.661574496518876
789 295 4.902686155817854
296 421 4.902686155817854
809 300 4.902686155817854
127 353 4.902686155817854
393 50 4.902686155817854
249 395 4.902686155817854
291 265 5.897911347683685
305 425 4.902686155817854
592 229 4.902686155817854
466 129 4.902686155817854
671 178 4.902686155817854
400 225 4.902686155817854
482 128 4.902686155817854
649 149 6.661574496518876
571 345 4.902686155817854
492 266 4.902686155817854
604 171 4.902686155817854
664 150 4.902686155817854
722 231 4.902686155817854
866 103 4.902686155817854
599 305 4.902686155817854

Zobrazenie v obrázku:

In [8]:
from PIL import Image, ImageDraw
w, h = int(1.1*max(b[0] for b in body)), int(1.1*max(b[1] for b in body)) #rozmery podla hodnot + 10% okraj
img = Image.new('RGB', (w, h), color = 'lightgray')
draw = ImageDraw.Draw(img)
for b in body:
    x, y, r = b
    img.putpixel( (b[0], b[1]), (255, 0, 0))
    draw.ellipse([x-r, y-r, x+r, y+r], fill=(255,0,0,255))
display(img)

Filtrovanie podľa polomeru:

In [17]:
from PIL import Image, ImageDraw
w, h = int(1.1*max(b[0] for b in body)), int(1.1*max(b[1] for b in body)) #rozmery podla hodnot + 10% okraj
img = Image.new('RGB', (w, h), color = 'lightgray')
draw = ImageDraw.Draw(img)
r = 3
for b in body:
    x, y, _r = b
    if _r < 8:
        continue
    img.putpixel( (b[0], b[1]), (255, 0, 0))
    draw.ellipse([x-r, y-r, x+r, y+r], fill=(255,0,0,255))
display(img)
In [18]:
vrcholy = [(b[0], b[1]) for b in body if b[2]>=8]
print(len(vrcholy))
print(vrcholy)
13
[(82, 423), (168, 361), (213, 300), (313, 290), (453, 262), (835, 266), (357, 250), (250, 217), (833, 187), (325, 157), (538, 166), (380, 125), (839, 106)]

Zametanie, zametacia priamka (Sweeping line)

  • konvexný obal vytvoríme z 2 častí - horná a dolná časť
  • usporiadame body podľa súradníc $\Theta(n.\log n)$
  • priebežne vytvárame aktuálnu hornú časť konvexného obalu ako spracovávame body zľava doprava
In [21]:
import matplotlib.pyplot as plt

from PIL import ImageFont
fnt = ImageFont.truetype("courbi.ttf", 32)

def zobraz(body, obal):
    body = sorted(body)
    w, h = int(1.1*max(b[0] for b in body)), int(1.1*max(b[1] for b in body))
    img = Image.new('RGB', (w, h), color = 'lightgray')    
    draw = ImageDraw.Draw(img)
    r = 3
    draw.line([body[i] for i in obal], fill=(0,0,255))
    draw.text((10,10), ",".join(str(i) for i in obal), font=fnt)
    for b in body:
        x, y = b
        draw.ellipse([x-r, y-r, x+r, y+r], fill=(255,0,0,255))
    display(img)
In [46]:
#horna cast konvexneho obalu

#zobraz(sorted(vrcholy), [0,1])
#zobraz(sorted(vrcholy), [0,1, 2]) #nekonvexne ... odstranime 1
#zobraz(sorted(vrcholy), [0,2])
#zobraz(sorted(vrcholy), [0,2,3]) #nekonvexne ... odstranime 2
#zobraz(sorted(vrcholy), [0,3]) 
#zobraz(sorted(vrcholy), [0,3,4,5])#nekonvexne ... odstranime 4
#zobraz(sorted(vrcholy), [0,3,5,6, 7]) #... odstranime 6
zobraz(sorted(vrcholy), [0,3,5,7,10,11,12]) #... odstranime 11 aj 10
zobraz(sorted(vrcholy), [0,3,5,7,10,12]) 
zobraz(sorted(vrcholy), [0,3,5,7,12])

Spočítanie konvexnosti 3 za sebou nasledujúcich bodov $A, B, C$: konvexnost $ \tan \alpha \textbf{?} \tan{\beta}$

$$ \frac{B_y-A_y}{B_x-A_x} ? \frac{C_y-B_y}{C_x-B_x} $$

Aby sa nemuselo riešiť delenie nulou, tak sa obe strany vynásobia ...

Po spojení hornej a dolnej časti môžeme spočítať celkovú dĺžku konvexného obalu:

In [47]:
obal = [0,3,5,7,12]
obal_body = [sorted(vrcholy)[i] for i in obal]
print(obal_body)
print(*zip(obal_body, obal_body[1:])) #dvojice susedných bodov
[(82, 423), (250, 217), (325, 157), (380, 125), (839, 106)]
((82, 423), (250, 217)) ((250, 217), (325, 157)) ((325, 157), (380, 125)) ((380, 125), (839, 106))
In [49]:
import numpy as np

def dist(p1, p2): #vypocitanie euklidovskej vzdialenosti
    return np.linalg.norm(np.array(p1)-np.array(p2))
In [50]:
dist((1,2), (3,4))
Out[50]:
2.8284271247461903
In [51]:
sum(dist(p1,p2) for p1,p2 in zip(obal_body, obal_body[1:]))
Out[51]:
884.8911821395161

Najbližšie dva body

Máte daných $n$ bodov v rovine. Nájdite najmenšiu vzdialenosť medzi 2 bodmi. Triviálne riešenie v $\Theta(n^2)$:

In [79]:
body = sorted(vrcholy)
najm = 10**10 #10^10 je XOR!!, t.j. nula
n = len(body)
for i in range(n-1):
    for j in range(i+1, n):
        vzd = dist(body[i], body[j])
        print(body[i], body[j], vzd)
        if vzd < najm:
            najm = vzd
print(najm)
(82, 423) (168, 361) 106.01886624558857
(82, 423) (213, 300) 179.6941846582688
(82, 423) (250, 217) 265.81948762270986
(82, 423) (313, 290) 266.5520587052368
(82, 423) (325, 157) 360.2846097184835
(82, 423) (357, 250) 324.8907508686574
(82, 423) (380, 125) 421.4356415871823
(82, 423) (453, 262) 404.4279911183201
(82, 423) (538, 166) 523.4357649224975
(82, 423) (833, 187) 787.20835869546
(82, 423) (835, 266) 769.1930836922547
(82, 423) (839, 106) 820.6936090892874
(168, 361) (213, 300) 75.8023746329889
(168, 361) (250, 217) 165.71059109181888
(168, 361) (313, 290) 161.44968256394932
(168, 361) (325, 157) 257.41989045137905
(168, 361) (357, 250) 219.18485349129398
(168, 361) (380, 125) 317.23808094237364
(168, 361) (453, 262) 301.70515408259104
(168, 361) (538, 166) 418.24036151476344
(168, 361) (833, 187) 687.3870816359586
(168, 361) (835, 266) 673.7314004853863
(168, 361) (839, 106) 717.8203117772581
(213, 300) (250, 217) 90.87353850269065
(213, 300) (313, 290) 100.4987562112089
(213, 300) (325, 157) 181.63975335812367
(213, 300) (357, 250) 152.43359209832983
(213, 300) (380, 125) 241.89667215569543
(213, 300) (453, 262) 242.98971171636055
(213, 300) (538, 166) 351.54089378051026
(213, 300) (833, 187) 630.2134559020459
(213, 300) (835, 266) 622.9285673333661
(213, 300) (839, 106) 655.3716502870718
(250, 217) (313, 290) 96.42613753542138
(250, 217) (325, 157) 96.04686356149273
(250, 217) (357, 250) 111.97321108193691
(250, 217) (380, 125) 159.26079241294764
(250, 217) (453, 262) 207.92787210953705
(250, 217) (538, 166) 292.48076859855246
(250, 217) (833, 187) 583.7713593522724
(250, 217) (835, 266) 587.0485499513647
(250, 217) (839, 106) 599.3680004805061
(313, 290) (325, 157) 133.5402561027947
(313, 290) (357, 250) 59.464274989274024
(313, 290) (380, 125) 178.08424972467387
(313, 290) (453, 262) 142.772546380598
(313, 290) (538, 166) 256.9065978132909
(313, 290) (833, 187) 530.1028202150975
(313, 290) (835, 266) 522.5514328752721
(313, 290) (839, 106) 557.253981591877
(325, 157) (357, 250) 98.35141076771599
(325, 157) (380, 125) 63.631753079732135
(325, 157) (453, 262) 165.55663683464942
(325, 157) (538, 166) 213.19005605327843
(325, 157) (833, 187) 508.8850557837202
(325, 157) (835, 266) 521.5179766796156
(325, 157) (839, 106) 516.5239587860374
(357, 250) (380, 125) 127.09838708654017
(357, 250) (453, 262) 96.74709297958259
(357, 250) (538, 166) 199.5419755339713
(357, 250) (833, 187) 480.15101790999046
(357, 250) (835, 266) 478.2677074609993
(357, 250) (839, 106) 503.0506932705689
(380, 125) (453, 262) 155.23530526268823
(380, 125) (538, 166) 163.23296235748464
(380, 125) (833, 187) 457.22314027179334
(380, 125) (835, 266) 476.3465125305317
(380, 125) (839, 106) 459.3930778755814
(453, 262) (538, 166) 128.22246293064254
(453, 262) (833, 187) 387.3306081372863
(453, 262) (835, 266) 382.02094183434497
(453, 262) (839, 106) 416.3315986086091
(538, 166) (833, 187) 295.7465130817268
(538, 166) (835, 266) 313.38315206788
(538, 166) (839, 106) 306.9218141481638
(833, 187) (835, 266) 79.02531240052139
(833, 187) (839, 106) 81.2219182240853
(835, 266) (839, 106) 160.04999218994044
59.464274989274024
In [56]:
print(body)
[(82, 423), (168, 361), (213, 300), (250, 217), (313, 290), (325, 157), (357, 250), (380, 125), (453, 262), (538, 166), (833, 187), (835, 266), (839, 106)]
In [111]:
#OneLiner:
n = len(vrcholy)
min(dist(vrcholy[i], vrcholy[j]) for i in range(n) for j in range(n) if i < j)
Out[111]:
59.464274989274024
In [112]:
min(dist(vrcholy[i], vrcholy[j]) for i in range(n-1) for j in range(i+1,n))
Out[112]:
59.464274989274024