Programiranje 1

Razvijamo prototip aplikacije za iskanje vesoljcev na podlagi slik spletnih kamer. Za zdaj zna iz slike izluščiti samo kroge in nobenih drugih likov. Ti krogi se ne sekajo. Primer je na spodnji sliki.

Naša prva naloga je prepoznati ptiče, torej okroglaste živali z dvema očesoma. Ptič je krog, ki

• ni vsebovan v nobenem drugem krogu
• in vsebuje natančno dva kroga,
• ki ne vsebujeta drugih krogov.

Na gornji sliki sta dva ptiča - označena sta z rdečo.

Prepoznati je potrebno tudi letala. To so okroglasti predmeti z okni. Letalo je torej krog, ki

• ni vsebovan v nobenem drugem krogu
• vsebuje nekaj krogov (vendar ne dveh, saj gre v tem primeru za ptiča),
• krogi, ki jih vsebuje, ne vsebujejo drugih krogov.

Z drugimi besedami, letala so kot ptiči, ki imajo kako čudno število oči.

Zaznani krogi so podani s seznamom trojk, ki predstavljajo koordinati središča in polmer. Za gornjo sliko je seznam takšen:

krogi = [
    (164.4, 136.8, 50.8),
    (59.2, 182.8, 50.8),
    (282.8, 71.5, 45.6),
    (391, 229.4, 58.4),
    (259.9, 186, 47.6),
    (428, 89, 63.2),
    (88.6, 44.3, 37.5),
    (371.6, 233.6, 10.6),
    (408.7, 210.5, 8.9),
    (398.1, 95.5, 13),
    (449.5, 99.6, 13.6),
    (455.4, 66.5, 12.4),
    (139.6, 138, 10.6),
    (185, 138, 10.6),
    (69.8, 46.5, 10.6),
    (267.4, 51.7, 17.2),
    (225.8, 187.3, 7.5),
    (242.8, 187.3, 7.5),
    (259.8, 187.3, 7.5),
    (276.7, 187.3, 7.5),
    (293.7, 187.3, 7.5),
    (267.4, 51.7, 10.6),
    (99.6, 43.1, 17.2),
    (99.6, 43.1, 10.6),
    (150.3, 245.5, 50.8),
    (144.3, 243.6, 38.8),
    (127.3, 245.5, 7.5),
    (161.3, 245.5, 7.5)]

Obvezna naloga

Napiši funkcijo ptici(krogi), ki prejme seznam krogov in vrne množico koordinat središč vseh ptičev. Za gornji primer vrne {(164.4, 136.8), (391, 229.4)}

Napiši funkcijo letala(krogi), ki vrne množico koordinat središč letal. V gornjem primeru sta to {(259.9, 186), (428, 89)}.

Pomembno: test vsake funkcije se mora izteči v 15 sekundah, sicer naloga ni rešena pravilno.

Dodatna naloga

Napiši funkcijo sumljivi(krogi), ki prejme prav takšen seznam in vrne središča potencialnih marsovskih ladij - to, je, vseh krogov, ki niso vsebovani v nobenem drugem krogu in niso ptiči ali letala.

Matematična pomoč

Če za dva kroga vemo, da se ne sekata in je prvi večji od drugega, je drugi vsebovan v prvem, kadar je razdalja med središčema manjša od polmera prvega kroga.

$$\sqrt{(x_0 - x_1)^2 + (y_0 - y_1)^2} < r_0$$

We are developing an application to detect flying saucers using web cameras. For now, it can detect only circles in images. Circles never overlap. See the image above.

Our first task is to recognize birds - circular animals with pair of eyes. A bird is thus a circle that

• is not contained within another circle
• and contains exactly two circles
• that do not contain any circle.

There are two birds in the above image; we colored them red.

Our next task is to recognize airplanes - circular objects with windows. An airplane is thus a circle that

• is not contained within another circle
• and contains some circles, but not exactly two (because in that case it's a bird)
• and the circles within the plane do not contain another circles.

In other words, an airplane is a bird with a weird number of eyes.

Circles are given as lists of triplets representing the x and y coordinates and the radius. See the example above.

Mandatory task

Write a function ptici(circles) that returns a set of centers of all birds. In the above case, it must return {(164.4, 136.8), (391, 229.4)}

Write a function letala(circles) that returns a set of centers of all airplanes. In the above case, {(259.9, 186), (428, 89)}.

Important: Tests for each function must complete in 15 seconds, otherwise the solution is considered incorrect.

Extra task

Write a function sumljivi(circles) that returns a set with centers of potential flying saucers, that is, all circles which are not contained in another circle and are not birds.

Mathematical help

If two circles do not intersect and the first one is larger than the second, then the second is within the first if the distance between their centers is smaller than the radius of the first.

$$\sqrt{(x_0 - x_1)^2 + (y_0 - y_1)^2} < r_0$$

Test