Beveiliging van museum Kempenland Irene Man 0721206
Richard Kuijstermans 0720436 31 maart 2011
Inhoudsopgave 1 Probleembeschrijving 1.1 Vereenvoudiging van het probleem . . . . . 1.1.1 Geheeltallige punten beveiligen . . . 1.1.2 Oneindig dunne muren . . . . . . . . 1.2 Camera’s . . . . . . . . . . . . . . . . . . . 1.2.1 3 typen camera’s . . . . . . . . . . . 1.2.2 Plaatsing van Camera’s . . . . . . . 1.3 Doel . . . . . . . . . . . . . . . . . . . . . . 1.4 Vertalen in wiskundige termen . . . . . . . 1.4.1 Parameters . . . . . . . . . . . . . . 1.4.2 Variabelen voor camera-verdelingen 1.4.3 Kostenfunctie . . . . . . . . . . . . . 1.4.4 Oplossingsverzameling . . . . . . . . 1.4.5 Optimalisatie . . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
. . . . . . . . . . . . .
3 4 4 4 5 5 6 7 7 7 8 9 10 11
2 Algoritme 12 2.1 Greedy algoritme I . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Greedy algoritme II . . . . . . . . . . . . . . . . . . . . . . . 16 3 Geheeltallige lineaire programmering 19 3.1 Randvoorwaarden . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2 Doelfunctie . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4 Oplossingsproces 4.1 Programmeren . . . . . . . . . . . 4.1.1 Buitenmuren . . . . . . . . 4.1.2 Camerapunten . . . . . . . 4.1.3 Te beveiligen punten . . . . 4.1.4 Verzameling C(qi ) bepalen 5 Wat nog te doen
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
21 21 21 21 24 24 26
Inleiding Ieder museum wil dat alle waardevolle spullen beveiligd wordt door camera’s. Natuurlijk willen ze dit doen tegen minimale kosten. Hoe kun je dan nu de camera’s zo hangen dat alles gezien wordt, maar tegen minimale kosten. Dit is wat wij voor museum Kempenland hebben onderzocht de afgelopen kwartiel. Ze willen namelijk dat al hun waardevolle schilderijen goed beveiligd worden. We zijn begonnen met het probleem om te schrijven naar wiskunde en van daaruit zijn we verder gaan werken. We hebben ook een twee algoritmen bedacht over het ophangen van de camera’s, zodat het hele museum beveiligd wordt. Maar de vraag is dan of je dan de minimale kosten kunt bereiken. De plattegrond van het museum is bekend en we gaan dit in een Java programma implementeren zodat we weten door welke camera een punt in het museum beveiligd kan worden. Dit kunnen we later gebruiken bij het lineair programmeren.
2
Hoofdstuk 1
Probleembeschrijving We moeten dus camera’s zo gaan hangen dat alles binnen het museum beveiligd wordt tegen minimale kosten. Er zijn drie soorten camera’s die gehangen mogen worden op de geheeltallige co¨ordinaten. Hieronder volgt de plattegrond van het museum.
Figuur 1.1: Plattegrond van het museum Kempenland
3
1.1 1.1.1
Vereenvoudiging van het probleem Geheeltallige punten beveiligen
Het doel van dit project is het vinden van de goedkoopste camera-verdeling die het museum geheel beveiligt. Het geheel beveiligen is in deze context het beveiligen van alle geheeltallige punten. Verder hoeft elk punt maar ´e´en keer door een camera beveiligd te worden. Stel dat er op een bepaald geheeltallig punt een muur staat, dan hoeft dit punt maar beveiligd te worden aan ´e´en kant van de muur. Dit is natuurlijk niet realistisch. Maar om het probleem simpel te houden, is dit volgens de opdrachtgever voldoende.
1.1.2
Oneindig dunne muren
Een andere vereenvoudiging van het probleem is het verwaarlozen van de dikte van de muren. De muren in dit model zijn als het ware oneindig dun, maar ze zijn niet doorzichtig. Dus een camera kan evenwijdig langs een muur kijken zonder last van de dikte van de muur te hebben.
Figuur 1.2: Het verschillen tussen een muur met dikte (boven) en een oneindig dunne muur (onder). Op het punt dat omcirkeld werd, is een camera geplaatst.
4
1.2 1.2.1
Camera’s 3 typen camera’s
Er zijn drie soorten camera’s waaruit de directie mag kiezen: 1. 90◦ -camera: Deze camera kan alleen bevestigd worden waar de muren een hoek maken. De hoek waarin de camera bevestigd wordt moet kleiner of gelijk zijn aan 90◦ . De aanschafkosten voor deze camera zijn 3000 euro. 2. 180◦ -camera: Deze camera kan zowel in hoeken van het gebouw als op rechte muren geplaatst worden. De hoek waarin de camera bevestigd wordt moet kleiner of gelijk zijn aan 180◦ . De aanschafkosten voor deze camera zijn 5000 euro. 3. 360◦ -camera: Deze camera kan in alle hoeken van het gebouw alsmede aan uiteinden van muren bevestigd worden. De aanschafkosten voor deze camera zijn 8000 euro. Hoewel een 360◦ -camera geschikt is voor alle hoeken kleiner dan of gelijk aan180◦ , en een 180◦ -camera goed is voor hoeken kleiner dan of gelijk zijn aan 180◦ , is het niet verstandig om een 360◦ -camera te plaatsen in een hoek kleiner dan 180◦ . Want het plaatsen van een 180◦ -camera is goedkoper en de beide soorten camera’s beveiligen dezelfde punten. Dit leidt tot eenduidige keuzen van camera voor elke hoek. Als de hoek gelijk aan θ is, waarbij: • 0◦ < θ ≤ 90◦ , dan is alleen een 90◦ -camera geschikt. • 90◦ < θ ≤ 180◦ , dan is alleen een 180◦ -camera geschikt. • 180◦ < θ ≤ 360◦ , dan is alleen een 360◦ -camera geschikt.
5
1.2.2
Plaatsing van Camera’s
Verder mag een beveiligingscamera slechts geplaatst worden op geheeltallige punten die tegelijkertijd ook muren zijn. Als er meerdere hoeken op een punt zijn, mogen ook meerdere camera’s gericht op verschillende richtingen opgehangen worden. Zie bijvoorbeeld het gekleurde punt in figuur 1.1, op ieder gekleurd deel mag ´e´en camera opgehangen worden.
Figuur 1.3: Meerdere camera’s op ´e´en punt: 180◦ -camera op geel, 180◦ camera op rood en 90◦ -camera op blauw.
6
1.3
Doel
Het doel is de camera’s zo te plaatsen dat ieder geheeltallig co¨ordinaat binnen het museum beveiligd is tegen minimale kosten.
1.4 1.4.1
Vertalen in wiskundige termen Parameters
Om het beveiligingsprobleem te analyseren, moeten eerst de relevante parameters die voortkomen uit het probleem gedefinieerd in wiskundige termen. Dit zijn bijvoorbeeld de aanschafkosten van de verschillende soorten camera’s. Maar ook de verzamelingen van punten die beveiligd moeten worden die vastgelegd worden door de gegeven plattegrond. Hieronder is een lijst van parameters: Omschrijving Q C90◦ C180◦ C360◦
={q1 , q2 , ..., qN }, punten die beveiligd moeten worden, #Q = N = {r1 , ..., rk }, verzameling posities waar 90◦ -camera’s opgehangen kunnen worden, #C90◦ = k = {rk+1 , ..., rk+1 }, verzameling posities waar 180◦ -camera’s opgehangen kunnen worden, #C180◦ = l = {rk+l+1 , ..., rk+l+m }, verzameling posities waar 360◦ -camera’s opgehangen kunnen worden, #C360◦ = m
K90◦ K180◦ K360◦
= 3000, aanschafkosten van een 90◦ -camera = 5000, aanschafkosten van een 180◦ -camera = 8000, aanschafkosten van een 360◦ -camera
C(qi )
= verzameling van camera-posities die het punt qi beveiligt
Verklaring voor C(qj ) Voor het beveiligen van een bepaald punt qj ∈ Q, is de eerste stap het vinden van alle camera-posities die het punt qj kunnen zien. Dat zijn precies alle punten waaruit een rechte lijn tot qj getrokken kan worden zonder dat het eerst snijdt met een muur. Het symbool dat hiervoor gebruikt wordt is C(qj ), omdat het afhangt van qj . Deze verzameling is ook een parameter, omdat het vast ligt samen met de gegeven plattegrond. Welke camera nu uit deze verzameling uiteindelijk gekozen moet worden om de optimale camera-verdeling te construeren, moet nog nader bepaald worden en dat wordt behandeld later in het verslag.
7
1.4.2
Variabelen voor camera-verdelingen
Behalve de parameters, zijn ook variabelen ingevoerd om de mogelijke cameraverdelingen te beschrijven. {x1 , ..., xk }, {xk+1 , ..., xk+1 } en {xk+l+1 , ..., xk+l+m } vertegenwoordigen respectievelijk de elementen van C90◦ , C18◦ en C360◦ , waarbij de 3 verzamelingen respectievelijk k, l en m elementen bevatten. Elke xi is dan een variabele die met waarden 0, 1 aangeeft of daar op de positie ri een camera wordt opgehangen of niet. De discrete waarde 1 is JA, en 0 NEE. 1, Wel camera op ri xi = (1.1) 0, Geen camera op ri Hiermee kan een mogelijke camera-verdeling uitgedrukt worden in een rijtje enen en nullen, x = (x1 , ..., xn )T , waarbij n = k + l + m.
8
1.4.3
Kostenfunctie
Nu de variabele voor een camera-verdeling gedefinieerd is, kan ook de aanschafkosten van iedere camera-verdeling bepaald worden. De kostenfunctie die aan ieder camera-verdeling zijn geassocieerde aanschafkosten toekent heeft de volgende formule: k(x) =
k X
k+l X
K90◦ xi +
i=1
K180◦ xi +
k+l+m X
K360◦ xi
(1.2)
i=k+l+1
i=k+1
Deze kostenfunctie rekent eigenlijk het inproduct uit van x met de kostenvector c = (c1 , ..., cn )T met: K90◦ , 1 ≤ i ≤ k K180◦ , k + 1 ≤ i ≤ k + l ci = K360◦ , k + l + 1 ≤ i ≤ k + l + m
(1.3)
Met de bovenstaande kostenvector wordt de kostenfunctie omgezet tot een inproduct:
k(x) =
k X
K
90◦
xi +
i=1
=
k X
=
K
180◦
ci xi +
k+l X
ci xi +
i=k+1
k+l+m X
xi +
i=k+1
i=1 n X
k+l X
K360◦ xi
i=k+l+1 k+l+m X
ci xi
i=k+l+1
ci xi
i=1
= (c, x) = cT x
(1.4)
9
1.4.4
Oplossingsverzameling
Er zijn heel veel camera-verdelingen (om precies te zijn: 2n stuks), maar niet elke camera-verdeling is in staat om alle qj uit de verzameling Q te beveiligen. In dit probleem zijn alleen camera-verdelingen interessant die ieder punt uit Q beveiligt. De verzameling van al dit soort verdelingen is de oplossingsverzameling en het wordt aangegeven met het symbool: P . Een element uit de verzameling P moet alle punten uit Q overdekken. Vanuit het perspectief van de te beveiligen punten, kan deze voorwaarde opgesplitst worden in een lijst voorwaarden die ieder voortkomt uit ´e´en qj . Dat wil zeggen, neem een willekeurig qj ∈ Q, dan moet het ten minste ´e´en keer gezien worden door een camera uit C(qj ), wat leidt tot de volgende ongelijkheid: X
xi ≥ 1
(1.5)
i:ri ∈C(qj )
Bij elke qj ∈ Q hoort ´e´en ongelijkheid. Als het aantal elementen in Q gelijk is aan N , dan zijn er in totaal N voorwaarden en al deze voorwaarden resulteren samen de voorwaarde voor een camera-verdeling om bij de oplossingsverzameling P te kunnen horen. In wiskundige termen luidt deze cumulatieve voorwaarde als volgt: ∀qj ∈ Q :
X
xi ≥ 1 =⇒ x ∈ P
(1.6)
i:ri ∈C(qj )
Bovendien kan deze voorwaarde in de matrix-vorm weergegeven worden: Ax ≥ b, waarbij de afmetingen van de matrix A, N × n is: − a1 T .. A= . − aN T
− 1 aj1 .. .. , b = . , aj = . − 1 ajn
Door de elementen uit aj op de juiste plaatsen gelijk aan 0 of 1 te kiezen, kan de ongelijkheid die behoort tot het element qj verwerkt worden in de vermenigvuldiging tussen de j’de rij uit A met de kolomvector x. Als de camera-positie ri in de verzameling C(qj ), oftewel als de camera op ri het punt qj ziet, dan is aji = 1, anders 0. 1, ri ∈ C(qj ) aji = (1.7) 0, ri ∈ / C(qj )
10
aj T x =
n X
aji xi
i=1
=
X
aji xi +
X
1 · xi +
X
X
0 · xi
i:ri ∈C(q / j)
i:ri ∈C(qj )
=
aji xi
i:ri ∈C(q / j)
i:ri ∈C(qj )
=
X
xi ≥ 1
(1.8)
i:ri ∈C(qj )
1.4.5
Optimalisatie
Nu alle benodigde parameters, variabelen en functies gedefinieerd zijn, kan ook de optimale oplossing in wiskundige termen uitgedrukt worden. Het doel van deze opdracht is om een optimale camera-verdeling uit deze verzameling te vinden die de laagste aanschafkosten met zich mee brengt. Met andere ˆ is optimaal als het aan de volgende 2 eisen woorden, een camera-verdeling x voldoet: ˆ∈P • x • ∀x ∈ P : k(ˆ x) ≤ k(x)
11
Hoofdstuk 2
Algoritme De eerste heuristische poging om een camera-verdeling te vinden die alle punten van Q beveiligt tegen lage kosten, was het toepassen van de zogenaamde Greedy algoritme. Twee simpele greedy algoritmen zijn ontwikkeld die intu¨ıtief redelijk goede camera-verdeling opleveren. Aan de hand van stapsgewijze voorschriften worden de algoritmen behandeld. Bovendien wordt de onvolledigheid van de algoritmen bewezen door het voorzien van tegenvoorbeelden.
12
2.1
Greedy algoritme I
Greedy algoritme I (GA-I) begint met een lege verzameling van cameraposities. Bij elke stap wordt de camera met de laagste aanschafkosten bepaald tussen de resterende camera’s die nog niet in die verzameling zit en het meest extra punten dekt, deze wordt dan toegevoegd aan de oude verzameling. Dit herhaalt zich totdat alle punten die beveiligd moeten worden overdekt zijn door de camera’s in de verzameling camera-positie. De precieze formulering gaat als volgt:
Voorschrift Begintoestand: I = {1, 2, ..., n} V = {∅}, verzameling indices van camera-positie’s W = {∅}, verzameling punten beveiligd door camera’s met indices in V
1. Bepaal c zodanig dat c = min ck . k∈I\V
2. Bepaal i zodanig dat ∀k, ck = c : #D(ri ) ≥ #D(rk ), waarbij D(rk ) = {qj | rk ∈ C(qj ) ∧ qj ∈ / W }. Als er meerdere i’s zijn die aan deze voorwaarden voldoen, kies dan de ene met de kleinste x-co¨ ordinaat. Als i nog niet eenduidig is, kies dan van de overgebleven indices de ene met de kleinste y-co¨ ordinaat. 3. Voeg i toe aan V en voeg D(ri ) toe aan W . Herhaal deze 3 stappen totdat W = Q.
13
Tegenvoorbeeld In de eerste instantie lijkt het GA-I intu¨ıtief goede oplossingen te bieden. Maar er zijn ook plattegronden waarbij GA-I niet de optimale oplossing kan vinden. De plattegrond in Figuur 2.1 is een voorbeeld waarbij de aanschafkosten niet geminimaliseerd worden.
Figuur 2.1: Tegenvoorbeeld voor Greedy algoritme I
In deze plattegrond gaat GA-I eerst alle mogelijke plaatsen van 90◦ -camera’s vullen, omdat er telkens wat nieuwe punten bij komen. Maar de cruciale punten in het midden kunnen net niet gezien worden door deze camera’s, waardoor er uiteindelijk toch een 180◦ -camera geplaatst moet worden in het midden(Zie figuur 2.2). De totale aanschafkosten van deze camera-verdeling bedragen 3000 · 4 + 5000 = 17000, dit is echt niet minimaal. Neem bijvoorbeeld de camera-verdeling in figuur 2.3, deze camera-verdeling kost 3000 + 5000 = 8000, wat minder is dan de oplossing die GA-I biedt.
14
Figuur 2.2: GA-I toegepast op het tegenvoorbeeld in figuur 2.1. De rode punten op de plattegrond rechtsonder zijn de camera-posities van de resulterende camera-verdeling.
Figuur 2.3: Een camera-verdeling voor plattegrond in figuur 2.1 die goedkoper is dan de oplossing van GA-I.
15
2.2
Greedy algoritme II
Greedy algoritme II (GA-II) begint met een lege verzameling van cameraposities. Bij elke stap wordt de camera met de gemiddeld laagste aanschafkosten bepaald tussen de resterende camera’s die nog niet in de verzameling zit en de meeste extra punten dekt, deze wordt dan toegevoegd aan de oude verzameling. Dit herhaalt totdat alle punten die beveiligd moeten worden gedekt zijn door de camera’s in de resulterende verzameling wat de oplossing is die GA-II biedt. De precieze formulering gaat als volgt:
Voorschrift Begintoestand: I = {1, 2, ..., n} V = {∅}, verzameling indices van camera-positie’s W = {∅}, verzameling punten beveiligd door camera’s met indices in V ci =kosten van camera op positie ri
1. Bereken voor ri de verzameling D(ri ) met D(ri ) = {qj | ri ∈ C(qj ) ∧ qj ∈ / W} 2. Noem E(ri ) = gemiddelde kosten voor camera-positie ri . ci Dit betekent E(ri ) = #D(r i) 3. Herhaal stap 1 en stap 2 totdat voor alle rj Ga dan naar stap 4. 4. Bepaal i zodanig dat E(ri ) = min E(rk ). k∈I\V
Als er meerdere i’s zijn die aan deze voorwaarden voldoen, kies dan de ene met de kleinste x-co¨ ordinaat. Als i nog niet eenduidig is, kies dan van de overgebleven indices de ene met de kleinste y-co¨ ordinaat. 5. Voeg i toe aan V en voeg D(ri ) toe aan W . Herhaal deze 5 stappen totdat W = Q.
16
Tegenvoorbeeld Ook bij dit algoritme is een tegenvoorbeeld te bedenken waar het algoritme niet de optimale oplossing geeft.
Figuur 2.4: Tegenvoorbeeld voor Greedy algoritme II
In deze plattegrond kiest GA-II als eerste camerapositie helemaal links- of rechtsonder. Er blijft dan bovenin nog een punt over die niet gezien wordt. Er komt daar dus ook nog een camera te hangen. De aanschafkosten voor deze camera-verdeling bedragen 3000 · 2 = 6000, maar dit is niet de optimale oplossing. In figuur 2.6 is een optimale oplossing te vinden. Als je daar een 180◦ -camera hangt wordt alles gezien en de aanschafkosten bedragen 5000.
17
Figuur 2.5: GA-II toegepast op het tegenvoorbeeld. De rode punten op de plattegrond rechtsonder is de resulterende camera-verdeling.
Figuur 2.6: Een camera-verdeling voor plattegrond in figuur 2.4 die goedkoper is dan de oplossing van GA-II.
18
Hoofdstuk 3
Geheeltallige lineaire programmering In de jaren 40 was de optimalisering techniek lineair programmeren sterk ontwikkeld vanwege de brede scala van transport-, planning-, organisatie- en productieproblemen. Doorgaans werden de oplossingsmethoden ge¨ımplementeerd in de computer die de berekening voerde. Omdat de doelfunctie en de randvoorwaarden van het probleem lineair waren, werd deze methode lineair programmering genoemd. In dit probleem gaat het om het plannen van camera-posities, waarbij de aanschafkosten geminimaliseerd moeten worden en het valt precies onder de context van lineair programmeren. Omdat de onbekende variabelen geheeltallig zijn, wordt het een geheeltallig lineair programmeringsprobleem (LIP). In dit hoofdstuk wordt een precieze formulering van de randvoorwaarden en de doelfunctie gegeven, die het probleem vastlegt. Hiermee kan de benodigde inputs bij een oplossingsprogramma ingevoerd worden dat de optimale oplossing zal vinden.
19
3.1
Randvoorwaarden
In het vorige hoofdstuk waren de voorwaarden vastgelegd waar een cameraverdeling aan moet voldoen om bij de oplossingsverzameling te horen. Bij elk punt dat beveiligd moet worden hoort ´e´en voorwaarde. Kies een qj ∈ Q, dan moet er gelden: X xi ≥ 1 i:ri ∈C(qj )
In matrix-vorm, (zie vergelijking (1.7) voor de elementen in matrix A):
−
a1 T .. .
− aN
T
x1 1 − .. .. . ≥ . − xn 1
(3.1)
Verder moeten alle onbekende variabelen xi geheeltallig zijn om samen een zinnige oplossing te vormen. Immers, op elk camera-positie mag maar ´e´en camera opgehangen worden.
3.2
Doelfunctie
De voorgaande randvoorwaarden beperken samen een gebied waar de optimale oplossing verschuilt en de doelfunctie specificeert waaraan de optimale oplossing moet voldoen. In dit geval is dat de kostenfunctie: k(x) = cT x die geminimaliseerd moet worden (zie vergelijking (1.3) voor de vector c).
20
Hoofdstuk 4
Oplossingsproces 4.1
Programmeren
Om aan de paramters te komen waarmee wij het probleem oplossen. Moeten we eerst de gegevens die bepaald zijn door de gegeven plattegrond van het museum in de computer verwerken. Daarvoor zijn programma’s in JAVA geschreven die de input van de text-file inleest. In de text-file zijn de beginen eindco¨ ordinaten van de muren gegeven. Bijvoorbeeld: 0,15,9,0 is de muur die loopt van co¨ ordinaat (0,15) naar co¨ordinaat (9,0).
4.1.1
Buitenmuren
Het eerste wat we dan gaan doen is de buitenmuren bepalen. Dit doen we door te beginnen met een muur met de grootste x-co¨ordinaat. Je weet zeker dat dit een buitenmuur is of anders aansluit op de buitenmuur. Het algoritme wat je dan steeds op elke muur gaat toepassen totdat je weer terug bent waar we begonnen zijn is: 1. Ga naar het eindpunt (xe , ye ) van de muur. Ga naar stap 2. 2. Kijk of er een muur is die aansluit op (xe , ye ). Als dit het geval is, ga naar stap 3, anders naar stap 4. 3. Ga naar stap 1 en herhaal totdat je weer terug bent bij (xe , ye ). 4. Dit betekent dat het geen buitenmuur is. Je gaat dan weer terug naar het beginpunt (xb , yb ) van deze muur. Ga naar stap 1 en zoek andere muur die aansluit op dit punt.
4.1.2
Camerapunten
De camerapunten kunnen alleen maar op de muren geplaatst worden en je kunt dus in twee situaties belanden: 21
1. De camera bevindt zich op een hoek, ofwel een snijpunt tussen twee muren. 2. De camera bevindt zich op punt van muur. In het geval dat de camera zich op een snijpunt van twee muren bevindt zit je ook weer in een bepaald aantal situaties waarin zich het snijpunt kan bevinden: 1. Begin- of eindpunt van Muur 1 en begin- of eindpunt van Muur 2 2. Snijpunt is begin- of eindpunt van Muur 1 en deze ligt tussen beginen eindpunt van Muur 2 3. Snijpunt is begin- of eindpunt van Muur 2 en deze ligt tussen beginen eindpunt van Muur 1 Nu hebben we drie verschillende camera’s die gebruikt kunnen worden. We moeten dan nog wel bepalen waar welke camera mag komen hangen. Dit betekent dat we de hoek moeten uitrekenen die het camerapunt maakt. Natuurlijk is het mogelijk om op een bepaald punt meerdere camera’s op te hangen als het camerapunt een snijpunt van muren is. Dus we moeten elk camerapunt ook nog specificeren met een minimale- en maximale kijkrichting. Hoe we dit allemaal doen wordt hieronder weergegeven. Hoeken berekenen Als de camera een snijpunt van twee muren is kun je de hoek berekenen door middel van de Cosinusregel. Het snijpunt tussen de twee muren noemen we (x3 , y3 ) en de andere co¨ordinaten van de muren noemen we (x1 , y1 ) van Muur 1 en (x2 , y2 ) van Muur 2. We weten drie punten en kunnen daar dus een driehoek van vormen. Hieruit bepalen we dus de drie zijden van de driehoek en we moeten een hoek weten. Dan kun je gebruik maken van de Cosinusregel. De lengte van de drie zijden noemen we: • A is de lengte tussen (x1 , y1 ) en (x3 , y3 ) • B is de lengte tussen (x3 , y3 ) en (x2 , y2 ) • C is de lengte tussen (x2 , y2 ) en (x1 , y1 ) De hoek tussen A en B noemen we γ. Dan geeft de cosinusregel: C 2 = A2 + B 2 − 2AB cos(γ) Hieruit kun je de hoek uithalen: γ = arccos(
C 2 − A2 − B 2 ) −2AB
22
Als de camera geen snijpunt van twee muren is heb je een paar gevallen: 1. De camera ligt op het uiteinde van een muur. Hier kan maar ´e´en camera hangen en dat is de 360◦ camera. 2. De camera ligt op een recht stuk van een muur. Hier kan dan een 180◦ camera hangen. Kijkrichting bepalen We gaan de minimale en maximale kijkrichting bepalen. Hierbij maken we gebruik van de arctangens. Omdat de arctangens een hoek geeft tussen de −90◦ en 90◦ moeten we dit in sommige gevallen nog wat corrigeren. Stel we zitten in de situatie als bij de vorige afbeelding. We berekenen de minimale kijkrichting dan als volgt: arctan(
y1 − y3 ) + 180 x1 − x3
De maximale kijkrichting berekenen we als volgt: arctan(
y2 − y3 ) + 360 x2 − x3
Er zijn natuurlijk nog veel meer mogelijkheden om een camerapunt te vormen zoals we al besproken hebben. Dit werkt vervolgens gewoon op dezelfde manier alleen het kan zijn dat je er andere getallen bij moet optellen. Dat is in het programma allemaal verwerkt, maar iets te groot om ze allemaal in het verslag te verwerken.
23
4.1.3
Te beveiligen punten
We hebben natuurlijk ook de verzameling te beveiligen punten nodig. In dit geval is dat niet zo heel moeilijk, want de buitenmuren zijn bekend. Je kunt de linker buitenmuren zien als de kleinste co¨ordinaten die beveiligd moeten worden en dat geldt ook voor de rechter kant, dit zijn de maximale co¨ ordinaten. Alle geheeltallige co¨ordinaten daartussen moeten beveiligd worden.
4.1.4
Verzameling C(qi ) bepalen
We hebben ook nog te bepalen welke camera een punt kan zien. Dit gaan we doen door te kijken of de lijn tussen het te beveiligen punt (xb , yb ) en het camerapunt (xc , yc ) geen snijpunt heeft met de muren. We gaan eerst een lijn bepalen tussen het te beveiligen punt en de camera. Dit doen we alleen in het geval waarbij de x-co¨ordinaat van beide punten niet gelijk is. Je hebt anders te maken met een verticale lijn. We hebben te maken met de volgende structuur: y = ac x + bc c Hiervoor geldt: ac = xybb −y −xc en bc = yc − xc ac . Dit kunnen we ook doen voor elke muur met beginpunt (xbm , ybm ) en eindpunt (xem , yem ). Je krijgt dan:
y = am x + bm bm −yem met am = xybm −xem en bm = yem − xem am . Dan kunnen we nu het snijpunt tussen deze lijnen uitrekenen. Er geldt nu namelijk:
am x + bm = ac x + bc Hieruit kun je x bepalen, namelijk: x=
bc − bm am − ac
Nu moeten we kijken of het snijpunt (x, y) zich op een muur bevindt. Dan kan dit punt niet door de camera worden gezien. Dit kunnen we bepalen door te kijken naar de co¨ ordinaten. Als geldt: min(b.x, c.x) < x < max(b.x, c.x) ∧ min(xbm , xem ) < x < max(xbm , xem ) dan kan de camera het punt niet zien. Als dit voor alle muren niet geldt dan kan de camera het punt zien.
24
Er zijn ook situaties waarbij je geen snijpunt kunt vinden. Je bevindt je dan namelijk in de situatie dat am = ac . Dit betekent dat de camera het punt kan zien. In het geval dat xb = xc betekent dit dat de lijn tussen deze twee punten verticaal is. Als deze lijn een snijpunt met een muur heeft, betekent dit dat de x-co¨ ordinaat van het snijpunt gelijk is aan xb . We gaan dan de y-co¨ordinaat van het snijpunt bepalen en kijken of deze waarde binnen het goede bereik ligt. De y-co¨ ordinaat van het snijpunt is makkelijk te vinden, want er geldt: y = am x + bm Nu moeten we controleren of geldt: min(yb , yc ) < y < max(yb , yc ) ∧ min(xbm , xem ) < xc < max(xbm , xem ) Als dit het geval betekent dat de muur de verticale lijn snijdt en de camera het punt niet kan zien. Dus we weten nu de verzameling C(qi ) en vanuit hier kunnen we dit gebruiken voor het lineair programmeren.
25
Hoofdstuk 5
Wat nog te doen We gaan lineair programmeren in Aimms. Omdat dit geheeltallig lineair programmeren is hopen we dat dit de optimale oplossing geeft. Als er geen oplossing uit komt moeten we verder gaan met algoritmen bedenken zodat we dit kunnen gaan toepassen op onze plattegrond en op een andere manier aan de oplossing te komen.
26
Literatuurlijst D.G. Luenberger, Y. Ye. Linear and Nonlinear Programming, Springer, 2008
27
