- Najbliższy punkt dla lokalizacji
- Odległość euklidesowa
- Najbliższy punkt dla danej lokalizacji w js
- Przykład zastosowania funkcji closestLocation
- Defibrillators - rozwiązanie zadania z CodinGame
Ostatnio moje posty są głównie inspirowane zadaniami, które rozwiązuję w wolnym czasie na CodinGame.
A, że są Święta i trwa narodowa izolacja z powodu koronawirusa, czasu tego jest sporo.
Ogólnie przez te ciągłe nawoływania “zostań w domu, zostań w domu” w obecnej sytuacji, mój dzień zupełnie się przestawił.
Wstaję mniej więcej o 3:00 nad ranem, kładę się spać w okolicach godziny 20:00. Jedyne gdzie wychodzę to z moim psem na spacer (niestety dość krótki) i do pracy - no cóż, w takich czasach przyszło mi żyć 
Czas ten jednak mogę spożytkować na rozwój i utrwalanie wiedzy oraz umiejętności programowania.
Najbliższy punkt dla lokalizacji
Wracając do tematu. Dzisiejszy post, będzie o tym jak znaleźć najbliższy punkt dla lokalizacji, w której się znajduje inny punkt, czyli jesteśmy w lokalizacji A, wokół nas są lokalizacje B, C, D i szukamy tej najbliższej:
Odległość euklidesowa
Do obliczenia odległości między dwoma punktami zastosujemy tzw. odległość euklidesową. Nałóżmy sobie na powyższy schemat układ współrzędnych:
Zapewne, każdy z nas w szkole podstawowej miał to na matematyce. Szkoła była jednak dawno, można więc nie pamiętać wzoru, dlatego przytaczam go poniżej.
Szukaną odległość między punktem A i punktem B można opisać wzorem:
No tak, my bazujemy na Lon i Lat więc podmieńmy oznaczenia:
Możemy, i to właśnie w kodzie zrobimy, rozbić całe równanie na składowe, czyli:
Tyle matematyki 
przejdźmy do kodu.
Najbliższy punkt dla danej lokalizacji w js
Powyższe wzory są przedstawione w postaci dwóch funkcji locationDistance, która umożliwia obliczenie dx i dy oraz vectorDistance, która oblicza nam pierwiastek z sumy potęg dx i dy:
1
2
3
4
5
6
7
8
9
10
const locationDistance = (location1, location2) => {
var dx = location1.lon - location2.lon,
dy = location1.lat - location2.lat;
return vectorDistance(dx, dy);
}
const vectorDistance = (dx, dy) => {
return Math.sqrt(dx * dx + dy * dy);
}
Mając kilka punktów wokół, czyli B, C i D, pojedynczo sprawdzamy, która jest z nich najniższa. Możemy to wykonać w js przy użyciu reduce, ponieważ funkcja ta zwróci nam jedynie jedną wartość z obliczeń. Możemy też zastosować np. Math.min.
Istnieje wiele ścieżek prowadzących w te samo miejsce.
Dane wejściowe targetLocation to lokalizacja, dla której poszukujemy najbliższego punktu w zestawie danych nazwanych locationData:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const targetLocation ={ lon: '3.879483', lat: '43.608177' }
const locationData = [
{
id: '1',
name: 'Maison de la Prevention Sante',
address: '6 rue Maguelone 340000 Montpellier',
lon: '3.87952263361082',
lat: '43.6071285339217'
},
{
id: '2',
name: 'Hotel de Ville',
address: '1 place Georges Freche 34267 Montpellier',
lon: '3.89652239197876',
lat: '43.5987299452849'
},
{
id: '3',
name: 'Zoo de Lunaret',
address: '50 avenue Agropolis 34090 Mtp',
lon: '3.87388031141133',
lat: '43.6395872778854'
}
];
Zobaczmy wpierw wykorzystanie reduce:
1
2
3
4
5
6
7
locationData.reduce((prev, curr) => {
var prevDistance = locationDistance(targetLocation, prev),
currDistance = locationDistance(targetLocation, curr);
return (prevDistance < currDistance) ? prev : curr;
});
Do tego samego wykorzystajmy Math.min():
1
2
const result = locationData.map((a)=>locationDistance(targetLocation, a));
console.log(locationData[result.indexOf(Math.min(...result))]['name']);
Przykład zastosowania funkcji closestLocation
Zobaczmy jak ten kod działa z danymi:
See the Pen zYvGWdQ by ejo (@ejo) on CodePen.
Najbliższa lokalizacji: {'3.879483', '43.608177'} jest punkt o nazwie: Maison de la Prevention Sante o lokalizacji: {'3.87952263361082', '43.6071285339217'}
Defibrillators - rozwiązanie zadania z CodinGame
Zastosowałam tą funkcję do rozwiązania zadania: Defibrillators. Pełne rozwiązanie zadania jest na moim Githubie, gdzie zamieszczam swoje rozwiązania z CodinGame.