Pa icle Fil e ing wi h Geospa ial Analysis o Indoo
Posi ioning
by
Do ian Ha de
Thesis o he deg ee o
Mas e o Science
(Geodesy and Geoin o ma ics)
Ha enCi y Uni e si y Hambu g
01.09.2021
Examine s:
P o . D .-Ing. Ha ald S e nbe g,
Msc. Hossein Shoush a i
Do ian Ha de
do ian.ha de @hcu-hambu g.de
S uden ID: 6067534
© Do ian Ha de 2021
DEDICATION
Many people ha e suppo ed me in nume ous ways h oughou my ime a he Ha enCi y
Uni e si y and especially while I was w i ing his hesis. Fi s o all I wan o hank my ellow
s uden s o hei company especially h ough he e en s o he las yea . Fu he I wan o
hank all my iends and amily o suppo ing me. I am especially hank ul o Niko Khaled,
who p o ided much inspi a ion and inside in o p og amming languages and all hings ega ding
in o ma ion echnology and who was allways a ailable o deep and in e es ing con e sa ions
ha I always enjoy. Fu he I wan o hank he examine s P o . D .-Ing. S e nbe g and Hossein
Shoush a i o he possibili y o w i e his hesis and o assessing i . Special hanks go o Hossein,
who mo i a ed me o wo k in he opic o his hesis and who always suppo s me in doing my bes .
Hambu g, 31.08.2021
Do ian Ha de
ii
iii
TABLE OF CONTENTS
DEDICATION ......................................... ii
ACKNOWLEDGMENTS.................................... iii
LISTOFFIGURES.......................................
LISTOFALGORITHMS.................................... ii
LISTOFACRONYMS..................................... iii
ABSTRACT........................................... x
KURZFASSUNG........................................ xi
SECTION
1 In oduc ion ......................................... 1
2 Li e a u e Re iew ...................................... 3
3 Me hodology ......................................... 6
3.1 Geospa ialAnalysis.................................. 6
3.2 Pa icleFil e ..................................... 8
3.2.1 Boo s ap Pa icle Fil e . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2.2 Pa icle Fil e wi h Back acking . . . . . . . . . . . . . . . . . . . . . . . 12
4 Implemen a ion ....................................... 15
4.1 Da aSe ........................................ 15
4.2 Boo s ap Pa icle Fil e wi h Geospa ial Analysis . . . . . . . . . . . . . . . . . . 18
4.3 Back acking Pa icle Fil e wi h Geospa ial Analysis . . . . . . . . . . . . . . . . 25
5 Resul s ............................................ 33
5.1 Boo s apPa icleFil e ................................ 33
5.2 Pa icle Fil e wi h Back acking . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
5.3 Compa ison o Boo s ap and Back acking Pa icle Fil e . . . . . . . . . . . . . . 47
6 Conclusion and Ou look .................................. 53
BIBLIOGRAPHY........................................ 55
i

LIST OF FIGURES
FIGURE
3.1 O e iew o some o he spa ial ela ions ha can be que ied in Shapely . . . . . . . . 7
3.2 O e iew o some o he used geospa ial analyses in GeoPandas; wi h dis ance shown
in (a), spa ial join in (b), que y by a ibu e in (c) and bu e in(d)........... 8
3.3 P inciple o pa icle weigh ing based on ou ing edges (blue poin : posi ion; g ey:
dis ibu ed pa icles; cyan: o hogonal dis ances o selec ed ou ing edge) . . . . . . . 10
3.4 Pa icle dis ibu ion based on s ep leng h and heading and he weigh ing, dependen on
wall in o ma ion o he loo plan. (blue: las es ima ed posi ion; ed: pa icles behind
wallwi hminimumweigh ) ............................... 11
3.5 Schema ic pic u e o he esampling p ocess. Wi h pa icles and hei weigh s be o e
( op) and a e (bo om) he esampling . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.6 Back acking PF o pa e n ma ching localiza ion . . . . . . . . . . . . . . . . . . . 13
3.7 P ocess o a back acking es . Blue a ows a e ecen s eps, ed a ows a e in alid pa hs 14
4.1 Floo plans o g ound loo (a), 1s loo (b) and 4 h loo (c), wi h he blue lines ep e-
sen ing he ou ingedges................................. 16
4.2 G ound u h poin s (o ange) o he “ze o o ou -pa h” in (a) o (c) and he “eigh -pa h”
in(d) ........................................... 17
4.3 G ound u h poin s (o ange) o he ze o o ou -pa h in(a) o (c) and he eigh -pa h
in(d); he ed do is he s a ing posi ion, he g een do is he inish . . . . . . . . . . . 18
4.4 O e iew o he used weigh ing me hods, wi h he wm in (a), w in (b), ww in (c) and
wl in(d).......................................... 24
5.1 CDF o he posi ioning e o o he eigh pa h wi h s ep leng h co ec ion o 0.1 m o
he boo s ap PF and he Pedes ian Dead Reckoning (PDR) wi hou a s ep co ec ion. 34
5.2 T ajec o y om he wl me hod (a)) and he combina ion o wl and w me hod (b)) o
eigh pa h wi h s ep leng h co ec ion o 0.1 m . . . . . . . . . . . . . . . . . . . . . 35
5.3 CDF o he posi ioning e o o he ze o o ou pa h wi h s ep leng h co ec ion o 0.2
m o he boo s ap PF and and he PDR wi h a s ep co ec ion o 0.2 m . . . . . . . . 36
5.4 T ajec o ies o he wl (a)), wm (b)) and ww (c)) me hods in combina ion wi h he w
o he ze o o ou pa h wi h s ep co ec ion o 0.2 m; g een do s: es ima ed posi ions . 37
5.5 CDF o he posi ioning e o o he eigh pa h wi hou s ep leng h co ec ion o he
boo s ap PF and he PDR wi hou a s ep co ec ion. . . . . . . . . . . . . . . . . . . 38
5.6 T ajec o ies om he wl me hod (a)), u ning back and he wm me hod (b)) cu ing he
co ne ; g een do s: es ima ed posi ions, ed a ows: walked pa h . . . . . . . . . . . . 39
5.7 CDF o he posi ioning e o o he ze o o ou pa h wi h s ep leng h co ec ion o 0.15
m o he boo s ap PF and he PDR wi h s ep leng h co ec ion o 0.15 m. . . . . . . . 40
5.8 CDF o he posi ioning e o o he eigh pa h wi h s ep leng h co ec ion o 0.1 m o
he back acking PF and he PDR wi h s ep leng h co ec ion o 0.1 m. . . . . . . . . . 41
5.9 Pa o he ajec o y o he eigh pa h, ha w ongly p oceeds in he ”galle y”, when
using he wl me hod, black a ows indica ing he walking di ec ion, he g een poin s
ep esen ing he posi ion es ima es o each s ep. . . . . . . . . . . . . . . . . . . . . 42
5.10 Example o he ajec o y co ec ion ( om (a) o (b)) h ough he back acking unc-
ionali y, he g een do s ep esen he alid, p opaga ed pa icles, he blue do is he
esul ingposi iones ima e ................................ 42
5.11 E ec o he suppo h ough he w suppo on he de ia ed ajec o y. . . . . . . . . . 43
5.12 CDF o he posi ioning e o o he ze o o ou pa h wi h s ep leng h co ec ion o 0.2
m o he back acking PF and he PDR wi h s ep leng h co ec ion o 0.2 m. . . . . . 44
5.13 CDF o he posi ioning e o o he eigh pa h wi hou s ep leng h co ec ion o he
back acking PF and he PDR wi hou s ep leng h co ec ion. . . . . . . . . . . . . . . 45
5.14 T ajec o y (g een do s) om he cl me hod o he eigh pa h wi hou s ep leng h co -
ec ion o he back acking PF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
5.15 CDF o he posi ioning e o o he ze o o ou pa h wi h s ep leng h co ec ion o 0.15
m o he back acking PF and he PDR wi h s ep leng h co ec ion o 0.15 m. . . . . . 46
5.16 Compa ison be ween he CDF o he posi ioning e o o he eigh pa h wi h a s ep
leng h co ec ion o 0.1 m o he back acking PF and he boo s ap PF . . . . . . . . . 47
5.17 T ajec o ies o he wm and w me hod o he boo s ap PF (a)) and he cm me hod o
he back acking PF (b)) o he eigh pa h wi h a s ep leng h co ec ion o 0.1 m . . . 48
5.18 Compa ison be ween he CDF o he posi ioning e o o he ze o o ou pa h wi h a
s ep leng h co ec ion o 0.2 m o he back acking Pa icle Fil e (PF) and he boo -
s apPF.......................................... 49
5.19 Compa ison be ween he CDF o he posi ioning e o o he eigh pa h wi hou s ep
leng h co ec ion o he back acking PF and he boo s ap PF . . . . . . . . . . . . . 50
5.20 Compa ison be ween he CDF o he posi ioning e o o he ze o o ou pa h wi h a
s ep leng h co ec ion o 0.15 m o he back acking PF and he boo s ap PF . . . . . 51
5.21 Compa ison be ween he ajec o ies o he boo s ap PF wi h he weigh ing by ooms
(wm) me hod (a)) and he back acking PF wi h check o oom (cm) me hod (b)).
G een do s ep esen he es ima ed posi ions a each s ep . . . . . . . . . . . . . . . . 52
i
LIST OF ALGORITHMS
ALGORITHM
4.1 Boo s apPF ....................................... 20
4.2 C ea eini ialpa icles .................................. 21
4.3 Weigh ingbylineo sigh ................................ 22
4.4 Weigh ingby ooms ................................... 22
4.5 Weigh ingbywalls.................................... 23
4.6 Weigh ingby ou ing................................... 23
4.7 Resampling........................................ 25
4.8 Back ackingPF ..................................... 26
4.9 C ea eini ialpa icles .................................. 27
4.10 Check pa icles o in e sec ions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.11 Check pa icles o con aining oom . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.12 Check pa icles o dis ance o ou ing edges . . . . . . . . . . . . . . . . . . . . . . 29
4.13 Back acking ....................................... 30
4.14 Back acking es in e sec ions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.15 Back acking es ooms ................................. 31
4.16 Back acking es ou ing................................. 32
ii
LIST OF ACRONYMS
5G Fi h-Gene a ion o Mobile Telecommunica ions Technology
CAD Compu e Aided Design so wa e
CDF Cumula i e Dis ibu ion Func ion
cl check o line o sigh
cm check o oom
c check o ou ing
CSV Comma Sepa a ed Values
GIS Geog aphic In o ma ion Sys em
GNSS Global Na iga ion Sa elli e Sys em
HCU Ha enCi y Uni e si y
IMU Ine ial Measu emen Uni
KF Kalman Fil e
LIDAR Ligh De ec ion and Ranging
iii
Sma phones inco po a e a a ie y o senso s o ack he Magne ic, Angula Ra e and G a -
i y (MARG) alues as well as en i onmen senso s o measu e p essu e, empe a u e, e c. ha
can be used o au onomous posi ioning. Typically a PDR se es as he basis o he localiza ion.
Essen ially, a PDR is a combina ion o a pedome e , es ima ed s ide leng h, and o ien a ion.
The sys em needs o es ima e he s ep’s leng h and di ec ion om he IMU measu emen s a e
i de ec s a s ep [7]. The IMU measu emen s o sma phones a e noisy and can only p o ide
eliable loca ion es ima ion in a limi ed amoun o ime, so ex e nal assis ance is necessa y.
App oaches ha use he in eg a ed senso s wi h addi ional in as uc u e suppo o posi ioning
a e called hyb id me hods. To co ec o d i and p o ide e icien localiza ion, isual suppo
can combine ision ea u es [18, 19], poin clouds om came as [12], [9] and Ligh De ec ion and
Ranging (LIDAR) senso s wi h odome y da a. Howe e , because o en i onmen al ci cums ances
o loca ion o he sma phone, such as in a pocke o bag, such ision-based auxilia y ea u es
may no always be a ailable. O he me hods, such as s a e-o - he-a odome y based lea ning
app oaches [8, 13], which mainly ely on he his o y o mo ion and posi ion senso alues o
eg ess he eloci y ec o , would hea ily ely on labeled da a. The main p oblem wi h hese
me hods is he lack o ealis ic da a se s, which ake in o accoun long ajec o y and unlimi ed
human ac i i ies.
Ano he possibili y o enhance he p ecision o he au onomous localiza ion app oach is o sup-
po he posi ioning wi h en i onmen al in o ma ion, such as loo plans and ou ing g aphs o
buildings. PF a e well sui ed o p ocessing he s ochas ically e y di e en da a o he sma -
phone senso s and he in o ma ion o a building’s geome y. Using PF algo i hms, i is possible o
conside inaccu acies in he posi ion measu emen s, by using weigh ed pa icles as ep esen a ion
o he p obabili y densi y dis ibu ion o he posi ion es ima es [14]. The weigh ed sum han esul s
in he posi ion es ima e. The boo s ap PF, as used in [20, 21] is he mos simple implemen a ion
o a PF algo i hm. The weigh s o he pa icles a e de e mined acco ding o he plausibili y o
he posi ion ha hey ep esen , e.g. hei dis ance o ou ing edges o i he pa icles lie behind
walls. The back acking PF [22, 23] is a mo e complex app oach, ha enables he co ec ion and
e-es ima ion o implausible pa hs, based on he pa icles p opaga ion his o y. This unc ionali y
can be especially use ul in complex building s uc u es, whe e w ong ajec o ies o pa icle clouds
can be co ec ed, by esampling hem o mo e plausible posi ions, based on he p opaga ion his-
o y. PF can no only be used o combine he PDR app oach wi h map ma e ial, bu can also used
in combina ion wi h e.g. Fi h-Gene a ion o Mobile Telecommunica ions Technology (5G) signal
in o ma ion, as done in [24]. He e a concep has been de eloped o use signals om 5G an ennas,
ins alled in a building, o de e mine he absolu e posi ion o a de ice whene e possible, while
using a PDR based me hod wi h PF o map ma ching he es o he ime.
4

The main d awback o he map ma ching app oaches in gene al is he gene a ion o he map
ma e ial, which needs o be o good quali y and he igh da a o ma . In [24] a wo k low has
been de eloped o ex ac he needed map ma e ial as GeoJSON- o ma om usually a ailable
CAD building plans. The PF algo i hms in his hesis ha e been de eloped o be able o use map
in o ma ion in he GeoJSON- o ma , making he aquisi ion o he map ma e ial signi ican ly easie .
5
3 Me hodology
This chap e desc ibes he unde lying me hodologies and concu en ly p esen s ela ed wo ks. The
me hodologies include geospa ial analysis, as well as he p inciples o he boo s ap Pa icle Fil e
(PF) and he PF wi h back acking unc ionali y.
3.1 Geospa ial Analysis
Geospa ial analysis desc ibes he p ocess o ex ac ing, manipula ing and isualizing o (usually
geo e e enced) spa ial in o ma ion [25]. One use case o geospa ial analysis is he in es iga ion
o he spa ial ela ionship be ween geome ic objec s. The mos undamen al geome ic objec s
a e so-called geome ic p imi i es. These a e geome ic objec s, which can be desc ibed by one
con inuous geome y and include poin s, cu es, su aces and solids [26]. A poin ’s in e io
consis s o one poin , i ’s bounda y o no poin s and i ’s ex e io o all o he poin s. A cu e has
an in e io o an in ini ely numbe o poin s along i ’s leng h, a bounda y o wo end poin s and an
ex e io consis ing o all o he poin s. The in e io o a su ace consis s o in ini ely many poin s
wi hin, while he su ace’s bounda y consis s o one o mo e cu es and he ex e io consis s o all
o he poin s.
Geospa ial analysis can be done wi h a a ie y o ools, including Geog aphic In o ma ion Sys-
em (GIS)-so wa e such as QGIS o A cGIS o by using p og amming languages, o example
Py hon, wi h lib a ies such as GeoPandas [27]. GeoPandas is an open sou ce p ojec , ex ending
he da a ypes used by pandas o enable spa ial analysis on geome ic objec s. These da a ypes a e
GeoSe ies and GeoDa aF ames. The undamen al geome ic objec s a e implemen ed in Shapely
as (as Poin class), LineS ing class and Polygon class. Se e al geome ies o he same kind can
be uni ied as collec ions, esul ing in so-called Mul iPoin s,Mul iLines ings and Mul iPolygons
[28]. GeoSe ies and GeoDa aF ames can s o e one o se e al di e en geome ic objec s. Geo-
Da aF ames, which a e basically ex ensions o he Da aF ames used in he Py hon lib a y Pandas,
also enable he s o age o a ibu es o geome ic objec s. This spa ial da a s uc u e includes spa-
ial ela ionships be ween geome ic objec s, such as con ains, in e sec s, o e laps, ouches, e c.
Geome ic ope a ions, such as he in es iga ions o he men ioned spa ial ela ionships, a e pe -
o med by Shapely [28]. Que ies o spa ial ela ions will e u n a Boolean alue (T ue o False).
Some o he que ies o spa ial ela ionships, implemen ed in Shapely a e shown in igu e 3.1 and
lis ed below:
•In e sec s e u ns T ue i he bounda y o in e io o he objec in e sec in any way wi h
hose o he o he .
6
•Con ains e u ns T ue i no poin s o he o he geome y lie in he ex e io o his geome y
and a leas one poin o he o he geome y’s in e io lies in he in e io o his geome y. A
line’s endpoin s a e i ’s bounda y and a e he e o e no con ained
•Wi hin e u ns T ue i his objec ’s bounda y and in e io in e sec only wi h he in e io o
he o he (no i s bounda y o ex e io ), making i he ’in e se’ o con ains.
•Touches e u ns T ue i he gi en objec s’ bounda ies ha e a leas one poin in common, bu
hei in e io s do no in e sec wi h any pa o he o he .
Figu e 3.1: O e iew o some o he spa ial ela ions ha can be que ied in Shapely
The unc ion o some o he undamen al geospa ial analyses ha can be applied o GeoSe ies
and GeoDa aF ames, a e lis ed below and a e shown in igu e 3.2:
•Dis ance e u ns he di ec dis ance be ween geome ies. I is also he o hogonal dis ance
be ween a poin and a line ea u e o edge, i he o hogonal p ojec ion o he poin exis s
(see igu e 3.2 (a). He e he dis ance om he co ne s o polygon B and he edges o he
polygons A and C is simul aneously he o hogonal dis ance, whe eas he dis ance be ween
he co ne s o A and C is no ).
•Spa ial join is used o me ge geome ic objec s based on hei spa ial ela ionships, as shown
in igu e 3.2 (b). Spa ial ela ionships, ha can be used as equi emen s o he spa ial join
include in e sec s,con ains,wi hin o ouches.
7
•Que y by a ibu e e u ns all objec s o he gi en GeoDa aF ame ha hold he que ied
a ibu e alue, as shown in igu e 3.2 (c), whe e all objec s wi h he Type alue o B a e
selec ed and ma ked in blue.
•Bu e gene a es a ep esen a ion o all poin s in a gi en dis ance o he geome y as polygon.
In igu e 3.2 (d), he esul ing bu e -polygons a ound a gi en line and a squa e shaped
polygon a e displayed in g een.
Figu e 3.2: O e iew o some o he used geospa ial analyses in GeoPandas; wi h dis ance shown
in (a), spa ial join in (b), que y by a ibu e in (c) and bu e in (d)
3.2 Pa icle Fil e
PF belong o he Mon e Ca lo Me hods, which a e g oups o s a e es ima ion me hods o model
highly non linea p oblems wi h e y noisy measu emen s [29]. The PF, in con as o he Kalman
Fil e (KF), a e able o handle highly non-linea p oblems, whe e he unce ain ies a e ep esen ed
by se e al es ima ion samples (so-called pa icles) [30]. The idea o a PF in he applica ion o
na iga ion, speci ically o Pedes ian Dead Reckoning (PDR), is o app oxima e he P obabili y
Densi y Func ion (PDF) o he posi ion by a la ge numbe o weigh ed, independen pa icles [14].
The weigh ed sum o he pa icles will han esul in a posi ion es ima e. In he ollowing subsec ion
3.2.1, he gene al PF app oach o indoo na iga ion is explained, based on he boo s ap PF. In
he subsec ion 3.2.2 he Back acking PF, a a ia ion o he PF model, is explained in de ail. Many
8
o he a ia ions o he PF exis , which mainly di e o each o he by modi ica ions o one o mo e
o he componen s. Fo examples o o he PF modi ica ions, see [30] and [31] among o he s.
3.2.1 Boo s ap Pa icle Fil e
The boo s ap PF is one o he simples PF modi ica ion. Fo he boo s ap PF, a i s a se o
ini ial pa icles is c ea ed, ep esen ing he PDF o he s a ing posi ion. The s a ing posi ion can
ei he be known o unknown. Fo he PDR, he pa icles a e ei he all loca ed a he known s a ing
poin as in [20] o hey can be dis ibu ed a ound he s a ing poin acco ding o he unce ain y o
he posi ion. In o he cases, o example in combina ion wi h absolu e posi ioning me hods such
as Recei ed Signal S eng h Indica ion (RSSI), he pa icles could also be andomly dis ibu ed
o e he whole a ea, as done by [21]. The boo s ap PF hen includes h ee main s eps, called
p opaga ion, weigh ing (o es ima ion s ep) and esampling, which a e explained in he ollowing :
P opaga ion:
Du ing he p opaga ion s ep he indi idual pa icles a e changed o be e ep esen he PDF. In
indoo posi ioning, he pa icles can spa ially p opaga ed, acco ding o leng h and heading o he
cu en s ep, which a e de i ed om he Ine ial Measu emen Uni (IMU) measu emen s. Possible
measu emen e o s can be aken in o conside a ion by assigning a andomly dis ibu ed noise o
s ep leng h and s ep heading o each pa icle, as done by [20]. The coo dina es o he Posi ion
xiand yi o he i h p opaga ed pa icle is hen calcula ed om he coo dina es o he las pa icle
posi ion xlas ,i and ylas ,i by (3.1) and (3.2):
xi=xlas ,i + (ls ep +ϵl,i)∗cos(h+ϵh,i)(3.1)
yi=ylas ,i + (ls ep +ϵl,i)∗sin(h+ϵh,i)(3.2)
Whe e ls ep is he leng h and his he heading o he cu en s ep and ϵis a no mal dis ibu ed
noise alue. This leads o a an-like dis ibu ion o he pa icle in he walking di ec ion. In [21], on
he o he hand, he s ep leng h o he pa icle p opaga ion, is p edic ed om he las h ee obse ed
s eps. The weigh s o he pa icles emain unchanged du ing he p opaga ion.
Weigh ing:
Du ing he weigh ing s ep, he weigh s o he pa icles a e upda ed acco ding o he pa icles’
plausibili y, his way he posi ion es ima e can be imp o ed wi h ele an in o ma ion (e.g. om
suppo ed map ma e ial), while he posi ion o he pa icles emains unchanged. A a ie y o
weigh ing me hods and c i e ia could be used. Following some weigh ing me hods a e desc ibed,
9

ha a e mainly based on map in o ma ion:
Weigh ing by ou ing: In he weigh ing by ou ing app oach, as i is implemen ed by [20, 32],
he o hogonal dis ance o each pa icle o he closes ou ing edge is conside ed, as shown in igu e
3.3. The weigh o each pa icle is he eby dec easing wi h inc easing dis ance o he ou ing edge
and can be calcula ed wi h equa ion 3.3:
w i=exp(−d2
i/2) (3.3)
Whe e w iis he weigh o he i h pa icle, wi h he o hogonal dis ance di o he closes ou ing
edge [20, 29].
Figu e 3.3: P inciple o pa icle weigh ing based on ou ing edges(blue poin : posi ion; g ey:
dis ibu ed pa icles; cyan: o hogonal dis ances o selec ed ou ing edge) om [32]
Weigh ing by walls: Ano he weigh ing app oach, used by [20], de e mines he weigh in ela-
ion o he dis ance o a pa icle o he nex wall and he di e ence in he o ien a ion o he pa icle
p opaga ion o he nex wall’s o ien a ion. Figu e 3.4 shows he dis ibu ion and weigh ing o he
pa icles a a speci ic s ep. Red pa icles ha e he minimum weigh , because hey a e behind walls
and he o he pa icles’ weigh , which inc eases wi h he dis ance o he wall, is displayed as shades
o g ey.
10
Figu e 3.4: Pa icle dis ibu ion based on s ep leng h and heading and he weigh ing, dependen on
wall in o ma ion o he loo plan. (blue: las es ima ed posi ion; ed: pa icles behind wall wi h
minimum weigh ) om [33]
Weigh ing based on PDR and map ma e ial: Ano he app oach o he weigh ing o pa icles
is used in [21]. Fi s , pa icles which a e no plausible, based on he building in o ma ion, ecei e
a weigh o ze o, his includes pa icles ha a e ou side o he building, inside walls, c ossed walls
o ha e a low dis ance om he wall. Fo his, me hods o compu a ional geome y [34, 35] ha e
been adap ed o de e mine i pa icles c oss walls o a e inside walls. The weigh o each emaining
pa icle w(k)depends on he di e ence be ween he p edic ed posi ion o he pa icle (xk, yk) and
he obse ed posi ion (zxk, zyk), ha is calcula ed acco ding o he PDR om he las es ima ed
posi ion. The weigh s a e calcula ed wi h he ollowing equa ion, whe e σzis he measu emen
noise, de i ed om empi ical s udies:
wk=1
2πσ2
e
∗exp (︃−(xk−zxk)2+ (yk−zyk)2
2σ2
z)︃(3.4)
Resampling:
The weigh ing o he pa icles can lead o he si ua ion, ha a small numbe o pa icles ha e a high
weigh which can lead o a di e ging il e p ocess. This can be a oided by a esampling p ocess,
which is shown in igu e 3.5. The ew pa icles wi h high weigh a e spli up in se e al pa icles
wi h weigh s ha a e in hei sum equal o he o iginal pa icles’ weigh . The goal is o assign a
weigh o 1/N o each pa icle, whe e Nis he numbe o pa icles. Fo his he pa icles a e pu
in o in e als acco ding o hei weigh s. Then a andom numbe be ween 0 and 1 is gene a ed and
i his numbe alls in a pa icle’s in e al, han his pa icle will be ep oduced wi h he weigh
1/N. Since pa icles wi h bigge weigh s ha e bigge in e als (indica ed wi h wi o he size o
he i h in e al in igu e 3.5), hey a e ep oduced mo e o en han pa icles wi h a lowe weigh
[20, 29].
11
Figu e 3.5: Schema ic pic u e o he esampling p ocess. Wi h pa icles and hei weigh s be o e
( op) and a e (bo om) he esampling ( om [29])
To decide i a esampling should be done, he numbe o e ec i e pa icles Ne can been used.
Ne is de ined by equa ion 3.5:
1
∑︁N
i=1 w2
i
=Ne (3.5)
I is Ne =Ni all pa icle ha e he same weigh and Ne = 1 i only one pa icle holds he
whole weigh . A h eshold o Ne = 0.7is sugges ed by [29] and also used by [20].
3.2.2 Pa icle Fil e wi h Back acking
A PF wi h back acking wo ks in i s basic unc ionali y such as he boo s ap PF. Bu Compa ed
o he simple boo s ap PF, i also conside s he pa icle ajec o y’s his o y o imp o e posi ion
es ima es. Du ing posi ioning wi h he map in o ma ion suppo , i can occu ha pa hs a e no
es ima ed co ec ly. Fo example, a change in di ec ion occu s a a loca ion whe e he e a e se e al
junc ions close by. I can happen ha he pa h ollows he w ong junc ion, due o unce ain ies in
he Posi ioning. The w ong pa h migh lead o an abo ing o he il e , due o s ong co ec ions
om he map in o ma ion. I he sca e ing o he pa icles is wide enough, pa o he pa icles
migh a el he co ec pa h. In his case a back acking unc ionali y can ecalcula e he pa h
om he s o ed his o y o he mo emen s o he pa icles. This was implemen ed, o example
12
in [22], whe e an app oach was de eloped o use RSSI inge p in ing and in o ma ion om map
ma e ial. In such a bac acking PF, a e he p opaga ion, he ajec o ies o in alid pa icles, o
example such ha c oss walls o no accessible a eas, a e dele ed du ing he so-called il e ing s ep,
in con as o he ypical case in he boo s ap PF, whe e he adjus men o he pa icles’ plausibili y
a his poin is done only by he assignmen o weigh s. A e his, he ajec o ies o alid pa icles
a e esampled in he esampling s ep, un il a speci ied numbe o pa icles is eached. In his way
he cu en as well as p e ious posi ion es ima ions can be e ined, as shown in igu e 3.6.
Figu e 3.6: Back acking PF o pa e n ma ching localiza ion, om [22]
In [23] a back acking app oach was used, inspi ed by he abo e men ioned one om [22]. Bu
ins ead o s o ing he ajec o y o e e y pa icle, only he his o y o he displacemen , de i ed
om he PDR, is s o ed and a scaling ac o o he displacemen , ep esen ing he noise o he
s ep leng h, as well as a noise alue o he o ien a ion angle o he de ice is assigned o each
13
Algo i hm 4.1 Boo s ap PF
Requi e: Weigh ingMe hods, pa h
1: load S a poin , S epHeading, S epleng h, heigh acco ding o chosen pa h
2: σS = 0.1
3: σH = 15 ∗π/180
4: Pa icleNumbe = 200
5: pa icles ←Ini ializePa icles(S a poin , Pa icleNumbe )
6: o sin numbe o S eps do
7: walls, Rou ingEdges, ooms ←da a o cu en loo acco ding o heigh [s]
8: P opaga edPa icles ←p opaga ion(pa icles, S epHeading[s], S epleng h[s],
σS, σH)
9: i wl is in Weigh ingMe hods hen
10: weigh s ←Weigh ingByLOS(P opaga edPa icles, walls)
11: append weigh s o Calcula edWeigh s
12: end i
13: i w is in Weigh ingMe hods hen
14: weigh s ←Weigh ingByRou ing(P opaga edPa icles, Rou ingEdges)
15: append weigh s o Calcula edWeigh s
16: end i
17: i wm is in Weigh ingMe hods hen
18: weigh s ←Weigh ingByRooms(P opaga edPa icles, ooms)
19: append weigh s o Calcula edWeigh s
20: end i
21: i ww is in Weigh ingMe hods hen
22: weigh s ←Weigh ingByWalls(P opaga edPa icles, walls)
23: append weigh s o Calcula edWeigh s
24: end i
25: w o al ←p oduc o all Calcula edWeigh s
26: Posi ionEs ima e ←weigh ed mean o pa icles posi ions
27: pa icles ←Resampling(P opaga edPa icles)
28: end o
Ini ializa ion
The ini ializa ion o he pa icles is done wi h algo i hm 4.2 ha equi es he coo dina es o he
s a posi ion (Xs a ,Ys a ) and he numbe o pa icles ha ha e o be ini ialized as inpu . Each
pa icle’s posi ion is calcula ed by adding a no mally dis ibu ed e o alue o he coo dina es o
he s a posi ion (line 2 o 3) and a Shapely Poin -geome y is c ea ed o his posi ion. A he end,
aGeoDa aF ame con aining all o hese Poin -geome ies is e u ned.
20

Algo i hm 4.2 C ea e ini ial pa icles
Requi e: Xs a , Ys a , s d, Pa icleNumbe
1: o isuch ha 0≤i≤Pa icleNumbe do
2: e ← andno m
3: add Poin (Xs a +e , Ys a +e ) o Pa icleLis
4: end o
5: Ini ialPa icles ←GeoDa aF ame(Pa icleLis )
6: e u n Ini ialPa icles
P opaga ion
The pa icles’ posi ion is upda ed wi h a simila app oach as [20] has used, based on he Pedes ian
Dead Reckoning (PDR). The heading o he i h pa icle (Hi) is calcula ed by (4.5):
Hi=H0+Hgy +Randno m ∗σH (4.5)
Whe e H0is he ini ial heading, Hgy is he es ima ed heading om he PDR, σHiis he noise
alue o he heading and Randno m is a no mal dis ibu ed andom numbe . Following he ap-
p oach om [20], he s ep leng h Si o he i h pa icle is calcula ed by (4.6):
Si=Sacc +Randno m ∗σS (4.6)
Whe e Sacc is he measu ed s ep leng h, and σS is he noise alue o he s ep leng h. The
coo dina es o he Posi ion Xiand Yi o he i h pa icle is hen calcula ed om he coo dina es o
he las pa icle posi ion Xlas ,I and Ylas ,i by (4.7) and (4.8):
Xi=Xlas ,i +Si∗cosHi(4.7)
Yi=Ylas ,i +Si∗sinHi(4.8)
Weigh ing me hods
A e he p opaga ion o he pa icles, he weigh s o he pa icles a e de e mined based on he
map in o ma ion, using he ollowing me hods, which a e also pic u ed in igu e 4.4:
Weigh ing by line o sigh : In he weigh ing by line o sigh (wl) app oach, he line ep esen ing
he di ec connec ion be ween a pa icle and he las es ima ed posi ion is checked o in e sec ions
wi h walls o e e y pa icle, as shown in igu e 4.4 (d). Algo i hm 4.3 is he implemen a ion o he
wl. Fi s all weigh s a e se o one. In line 2 o 5 a GeoDa aF ame con aining all di ec connec ions
be ween he las es ima ed posi ion and he cu en (p opaga ed) pa icles as LineS ings. Then,
21
hese connec ions a e es ed o in e sec ions wi h he polygons ep esen ing he walls. Fo each
connec ion, ha in e sec s a wall, he weigh o he espec i e pa icle is se o he minimal weigh .
Algo i hm 4.3 Weigh ing by line o sigh
Requi e: pa icles, walls, las Posi ion
1: all weigh s = 1
2: o pa icle in pa icles do
3: append LineS ing(Pa iclePosi ion, las Posi ion) o connec ions
4: end o
5: con e connec ions o GeoDa aF ame
6: in e sec ions ←spa ial join on ’in e sec ’ o connec ions and walls
7: i numbe o in e sec ions ≥1 hen
8: o i←index o in e sec ions do
9: wiegh s[i]←MinimalWeigh
10: end o
11: end i
12: e u n weigh s
Weigh ing by ooms: In he weigh ing by ooms (wm) me hod, e e y pa icle is examined i
i is posi ioned in a polygon ep esen ing a cu en ly alid oom. All pa icles loca ed in a alid
oom ecei e he weigh 1, all o he pa icles ecei e he minimal weigh (see igu e 4.4 (a)). In
algo i hm 4.4, which implemen s he wm me hod, all weigh s a e se o he minimal alue o 0.001.
Then a spa ial join be ween he wo GeoDa aF ames con aining he pa icles and he alid ooms
a e done, e u ning all pa icles wi hin hose alid ooms (line 2). Fo each o hose pa icles in a
alid oom, he weigh is hen se o 1 (line3 o 5). Di e en ooms could be used as alid ooms, in
his case all s ai cases, li s and co ido s a e used as alid ooms. Rooms ha a e no pa o hese,
e.g. he small ooms in he es da a se , can s ill be en e ed, i enough pa icles a e in hem, since
hei weigh is no se o ze o bu o 0.001 gi ing hem s ill a e y small in luence on he posi ion
es ima e.
Algo i hm 4.4 Weigh ing by ooms
Requi e: pa icles, V alidRooms
1: all weigh s =MinimalWeigh
2: Pa iclesWi hin ←spa ial join on ’wi hin’ o pa icles and V alidRooms
3: o i←index o in e sec ions do
4: wiegh s[i]←1
5: end o
6: e u n weigh s
Weigh ing by walls: As in he wm app oach, in he weigh ing by walls (ww) app oach each
pa icle is checked i i is inside a polygon. In his case he polygons ep esen he buildings’ walls
22
and pa icles loca ed in hem a e conside ed in alid and pa icles ha a e no inside he polygons
and a e conside ed alid (see igu e 4.4 (c)). The algo i hm 4.5, used o implemen he weigh ing
by walls (ww) me hod, is simila o algo i hm 4.4, bu he ini ial weigh s a e se o 1. Now a spa ial
join be ween he wo GeoDa aF ames con aining he pa icles and he walls a e done, e u ning all
pa icles wi hin he walls (line 2). Fo each pa icle, ha is loca ed wi hin a wall, he weigh is hen
se o he minimal weigh .
Algo i hm 4.5 Weigh ing by walls
Requi e: pa icles, walls
1: all weigh s = 1
2: Pa iclesinWalls ←spa ial join on ’wi hin’ o pa icles and walls
3: o i←index o Pa iclesinWalls do
4: wiegh s[i]←minimalWeigh
5: end o
6: e u n weigh s
Weigh ing by oo ing: The implemen ed weigh ing by ou ing (w ) app oach is simila o he
app oach o [20, 32], as desc ibed in sec ion 3.2.1. He e he dis ance o each pa icle o he closes
ou ing edge is conside ed, as shown in igu e 4.4 (b) and in line 2 o algo i hm 4.6. Fo his,
he di ec dis ances be ween all ou ing edges and he pa icle a e que ied, by using he dis ance
me hod o he GeoDa aF ame con aining all ou ing edges. The smalles o hose dis ances is hen
he di ec dis ance be ween he pa icle and he closes ou ing edge (called mindis in algo i hm
4.6. I his minimal dis ance is smalle han 3 m, he weigh o his pa icle is calcula ed (line
4). I he minimal dis ance is g ea e han 3 m, he co esponding weigh is se o he minimal
weigh - alue o 0.001. To make he algo i hm as e and simpli y he compu a ions, he sho es
dis ance om each pa icle o he nex ou ing edge has been used ins ead o always calcula ing
he o hogonal dis ances.
Algo i hm 4.6 Weigh ing by ou ing
Requi e: pa icles, Rou ingEdges
1: o pa icle in pa icles do
2: mindis ←minimal o alldis ances be ween Rou ingEdges and pa icle
3: i mindis < 3 hen
4: weigh o pa icle ←exp (︂−0.5∗mindis 2
ϵ ou )︂
5: else
6: weigh o pa icle ←minimalWeigh
7: end i
8: end o
9: e u n weigh s
23
Figu e 4.4: O e iew o he used weigh ing me hods, wi h he wm in (a), w in (b), ww in (c) and
wl in (d)
Resampling
The algo i hm o he esampling s ep (algo i hm 4.7), is used o pe o m he low a iance esam-
pling, as desc ibed in sec ion 3.2.1. The esampling p ocess is only s a ed, i Ne is smalle han
0.7 ( o he calcula ion see equa ion 3.5), o he wise he o iginal pa icle posi ions a e e u ned. To
de e mine he limi s o he esampling in e als o he esampling, he cumula ed alues o he
pa icles’ weigh s a e used (line3). In line 4 o 8, o each pa icle a andom numbe be ween 0
and 1 is d awn and he posi ion o e e y pa icle, which’s co esponding weigh in e al’s uppe
limi is smalle han he d awn andom numbe (line 6 and 7), is added o he lis o pa icles o
esample (line 8). As explained in sec ion 3.2.1 his esul s in pa icles wi h highe weigh being
esampled mo e o en. The weigh s a e no changed, since he weigh s will be ecalcula ed o
e e y pa icle du ing he nex loop o he PF algo i hm. The esampled pa icles a e han e u ned
as a GeoDa aF ame o be used in he nex p opaga ion s ep.
24
Algo i hm 4.7 Resampling
Requi e: pa icles
1: i Ne =<0.7∗Pa icleNumbe hen
2: o pa icle in pa icles do
3: in e als ←lis o cumula ed weigh s
4: o each pa icle in pa icles do
5: and1← andomnumbe be ween 0and 1
6: o iin Index o pa icles do
7: i in e alls[i]> and1 hen
8: append pa icles[i] o ResampledPa icles
9: end i
10: end o
11: end o
12: end o
13: con e ResampledPa icles o GeoDa aF ame
14: e u n ResampledPa icles
15: else
16: e u n Pa icles
17: end i
4.3 Back acking Pa icle Fil e wi h Geospa ial Analysis
This sec ion explains he implemen a ion o he undamen al algo i hms o he Back acking PF
wi h geospa ial analysis. Algo i hm 4.8 desc ibes he o e all algo i hm o his PF app oach. As
inpu i equi es he name o he chosen pa h and he name o he chosen il e ing concep as s ing
and a boolean s a emen i he ou ing suppo (w ) should be used. Simila o he boo s ap PF
wi h geospa ial analysis, i s he da a o he s ep heading, s ep leng h and s ep heigh o he
chosen pa h a e loaded (line 1), ollowed by he se ing o he needed pa ame e s in line 2 o 5. In
line 6 he ini ial pa icles a he s a posi ion a e c ea ed (see algo i hm 4.9, be o e he o -loop
om line 7 on i e a es o e all s eps while pe o ming he PF-p ocesses. Fo e e y s ep he cu en
loo is de e mined and he loo da a is selec ed acco dingly (line 8 o 10). In con as o he
boo s ap PF wi h geospa ial analysis, a s ep-objec (S ep) is c ea ed (line 11), which s o es he
leng h, heading, heigh , cu en loo , he cu en posi ion es ima e and he oom i is loca ed in, as
well as all ooms whe e pa icles a e allowed o he cu en s ep. In line 12 he pa icles’ posi ions
a e hen p opaga ed and il e ed ega ding hei plausibili y acco ding o he chosen il e concep
( o de ailed explana ion see algo i hms 4.10 o 4.12). I ou ing suppo is ac i e, he pa icles’
weigh s acco ding o he w me hod a e de e mined a e wa ds, using algo i hm 4.6, o he wise all
weigh s a e se o one. The weigh ed mean o he pa icles posi ion hen, p o ides he posi ion
es ima e. Following he es ima ion o he posi ion, he back acking algo i hm (see algo i hm 4.13,
25

is execu ed o c ea e new pa icles (co esponding o he esampling o he boo s ap pa icle il e )
and add hem o he GeoDa aF ame con aining he p opaga ed, alid pa icles. These a e hen
used in he nex loop o he back acking PF algo i hm. A e he PF is pe o med on he las s ep,
all calcula ed posi ions, as well as he s anda d de ia ion o each posi ion es ima e is e u ned and
sa ed as a CSV- ile.
Algo i hm 4.8 Back acking PF
Requi e: pa h,Fil e Concep ,Rou ingSuppo =T ue/False
1: load S a poin , S epHeading, S epLeng h, S epHeigh acco ding o chosen pa h
2: maxPa icleNumbe = 200
3: σR= 1.52
4: σH = 15 ∗np.pi/180
5: σS = 0.1
6: pa icles ←Ini ializePa icles(S a , maxPa icleNumbe , σH, σS)
7: o iin S epNumbe do
8: Cu en Floo ←CheckFloo (Heigh )
9: Floo Changed ←T ue/False
10: se Floo Da a acco ding o he Cu en Floo
11: S ep ←S ep(S epLeng h, S epHeading, Heigh , Cu en Floo , Cu en Room,
V alidRooms, Cu en Posi ion, S epScale)
12: P opaga edPa icles ←CheckPa icleS eps(pa icles, S ep, Floo Da a,
Floo Changed, ansi ion)
13: i Rou ingSuppo is T ue hen
14: weigh s ←Weigh ingByRou ing(P opaga edPa icles, Rou ingEdges)
15: else
16: se all weigh s o 1
17: end i
18: Posi ionEs ima e ←weigh ed mean o pa icles posi ions
19: append Posi ionEs ima e o T ajec o y
20: Numbe O NewPa icles ←maxPa icleNumbe −numbe o P opaga edPa icles
21: Back ackingS epNumbe ←numbe o S eps, bu max 32
22: BackT ackingS eps ←walked S eps in e e se o de un il Back ackingS epNumbe
o a loo change is eached
23: pa icles ←BackT acking(Numbe O NewPa icles, P opaga edPa icles,
BackT ackingS eps, Floo Da a, maxT ies, σH, σS)
24: e u n Posi ionEs ima e
25: end o
26: e u n T ajec o y
26
Pa icle Ini ializa ion
In algo ihm 4.9, he ini ializa ion o pa icles is shown. As o he boo s ap PF wi h geospa ial
analysis, he s a posi ion is conside ed o be known and each pa icle posi ion is calcula ed in
by adding a no mally dis ibu ed noise alue o he coo dina es o he s a posi ion. He e, o
each pa icle an indi idual noise alue o s ep heading and s ep leng h is gene a ed by mul iplying
he noise alues o s ep heading (σH) and s ep leng h (σS) wi h a no mally dis ibu ed andom
numbe (line 3 and 4). The pa icles posi ion, ep esen ed by Poin -geome ies, as well as he noise
alues a e hen s o ed in a GeoDa aF ame, ha is e u ned.
Algo i hm 4.9 C ea e ini ial pa icles
Requi e: Xs a , Ys a , MaxPa icleNumbe
1: o isuch ha 0≤i≤MaxPa icleNumbe do
2: append Poin (Xs a +e andno m, Ys a +e andno m) o geome ies
3: append σS +e o Leng hNoise
4: append σH +e o AngleNoise
5: end o
6: Ini ialPa icles ←GeoDa aF ame(geome ies, Leng hNoise, AngleNoise)
7: e u n Ini ialPa icles
P opaga ion and pa icle check
In he back acking PF wi h geospa ial analysis, he p opaga ion o he pa icles is in eg a ed in he
il e p ocess, in which he pa icles a e checked o hei plausibili y by ei he he check o line o
sigh (cl), check o oom (cm) o check o ou ing (c ) concep . The new posi ion o each pa icle
Xi, Yiis calcula ed in he p opaga ion wi h equa ions 4.9 and 4.9:
Xi=Xlas ,i + (S+ϵl,i)∗cos(H0+Hgy +ϵh,i)(4.9)
Yi=Ylas ,i + (S+ϵl,i)∗sin(H0+Hgy +ϵh,i)(4.10)
Whe e H0is he ini ial heading, Hgy is he es ima ed heading om he PDR, Sacc is he measu ed
s ep leng h and ϵl,i and ϵh,i a e he noise alues o s ep leng h and s ep heading o each i h pa icle.
The cl (see algo i hm 4.10, equi es he cu en pa icles, he cu en s ep objec and he s a emen
i he loo changed in his s ep. I u he equi es he GeoDa aF ame con aining he polygons
ep esen ing he ele an s ai s and li s (called Cu en T ansi ion in algo i hm 4.10,4.11 and
4.12). In line 1 o 3, pa icles ha a e no loca ed in he polygon con ained in Cu en T ansi ion
a e dele ed. The pa icles a e han p opaga ed as men ioned abo e. The s ep heading and s ep
leng h a e ob ained om he S ep objec . Nex , a GeoDa aF ame is c ea ed con aining all he
connec ions be ween each p opaga ed pa ice and i ’s p e ious posi ion (line 5 o 7). E e y pa icle,
27
whose co esponding connec ion line in e sec s a wall is dele e, e e y o he pa icle is kep in he
GeoDa aF ame (line 9 o 17). Finally he GeoDa aF ame wi h he emaining pa icles is e u ned.
Algo i hm 4.10 Check pa icles o in e sec ions
Requi e: pa icles, S ep, walls, Floo Changed, Cu en T ansi ions
1: i Floo Changed is T ue hen
2: pa icles ←pa icles in Cu en T ansi ion
3: end i
4: P opaga edPa icles ←p opaga ion(pa icles, S epHeading, S epLeng h)
5: o each p1in pa icles and p2in P opaga edPa icles do
6: append LineS ing(p1,p2) o connec ions
7: end o
8: in e sec ions ←spa ial join on ’in e sec ’ be ween connec ions and walls
9: i numbe o in e sec ions ≥1 hen
10: o pin P opaga edPa icles do
11: i pis no endpoin o any line in in e sec ions hen
12: keep p
13: else
14: dele e p
15: end i
16: end o
17: end i
18: e u n P opaga edPa icles
Algo i hm 4.11, o he cm concep is simila s uc u ed as algo i hm 4.10. Bu he e no
he walls a e equi ed as map in o ma ion, bu he ooms conside ed as alid o he pa icles
(V alidRooms) and doo s. I a loo change ook place, he ooms cu en ly con ained in he
GeoD aF ame V alidRooms a e eplaced wi h he polygon-geome y ep esen ing he cu en an-
si ion (line 1 o 3). Fo each p opaga ed pa icle, i is checked i i is ei he wi hin one o he alid
ooms o i he LineS ing-geome y om i ’s new and i ’s p e ious posi ion in e sec s ei he wi h
any doo -polygon o any polygon con ained in T ansi ions. I ha is he case, i is appended o
he alid pa icles (line 5 o 9), which a e inally e u ned as a GeoDa aF ame.
28
Algo i hm 4.11 Check pa icles o con aining oom
Requi e: pa icles, S ep, Floo Changed, T ansi ion, V alidRooms, doo s)
1: i Floo Changed is T ue hen
2: pa icles ←pa icles in Cu en T ansi ion
3: end i
4: P opaga edPa icles ←p opaga ion(pa icles, S epHeading, S epLeng h)
5: o each p1in pa icles and p2in P opaga edPa icles do
6: i p2is in V alidRooms o LineS ing(p1,p2) in e sec s Doo s o T ansi ions hen
7: append p2 o V alidPa icles
8: end i
9: end o
10: e u n V alidPa icle
The algo i hm 4.12, o he c concep , is simila o 4.6. All pa icles a e p opaga ed in he
same way as in algo i hm 4.10 and 4.11. Fo each p opaga ed pa icle he smalles dis ance o he
ou ing edges is de e mined (as in algo i hm 4.6). Only i he smalles dis ance o he ou ing edges
o a pa icle is smalle han 2 m, i is appended o he lis o alid pa icles (line 3 o 4). The alid
pa icles a e hen, as o he o he concep s, e u ned as a GeoDa aF ame.
Algo i hm 4.12 Check pa icles o dis ance o ou ing edges
Requi e: pa icles, S ep, Rou ingEdges
1: P opaga edPa icles ←p opaga ion(pa icles, S epHeading, S epLeng h)
2: o each pin P opaga edPa icles do
3: i dis ance be ween pand Rou ingEdges < 2 hen
4: append p o V alidPa icles
5: end i
6: end o
7: e u n V alidPa icles
Back acking
Following, he algo i hms o he back acking p ocedu e a e explained. Algo i hm 4.13 o e all
p ocedu e, which basically ies o gene a e new pa icles un il he maximal numbe o pa icles is
eached again. Fi s , a numbe pa icles, acco ding o he di e ence be ween he numbe o alid
pa icles and he maximum numbe o pa icles, is andomly chosen om he cu en ly exis ing
pa icles (line 2). Fo each sample pa icle, a new pa icle a a andom posi ion inside adius
(line 1) is p oposed (line 5). Fo his p oposed pa icle, a back acking es is pe o med and i
i passes he es , i is appended o he exis ing pa icles (line 6 o 8). I he pa icle doesn’ pass
he back acking es , he p ocedu e is epea ed un il ei he he maximum numbe o pa icles is
eached o un il a maximum numbe o ies (in his case eigh ies) has been eached. The limi ed
29
Figu e 5.3: CDF o he posi ioning e o o he ze o o ou pa h wi h s ep leng h co ec ion o 0.2
m o he boo s ap PF and and he PDR wi h a s ep co ec ion o 0.2 m
Figu e 5.4 shows he ajec o ies o he wl,ww and wm me hods in combina ion wi h he w
o he ze o o ou pa h. O all he es ed me hods only he ajec o ies o he ww wi h w and he
wm me hod we e able o en e he ele a o du ing he ze o o ou pa h, while he o he ajec o ies
missed i closely. The las oom was only eached by he ajec o ies om he ww in combina ion
wi h he w as well as he wm me hod wi h and wi hou he addi ional suppo h ough he w
me hod. The combina ion o wl and w e en missed he las u n in he 4 h loo , whe e some
posi ions could no be es ima ed because all pa icles we e in alid.
36

Figu e 5.4: T ajec o ies o he wl (a)), wm (b)) and ww (c)) me hods in combina ion wi h he w
o he ze o o ou pa h wi h s ep co ec ion o 0.2 m; g een do s: es ima ed posi ions
The esul s o he eigh pa h wi hou any s ep leng h co ec ion is displayed in igu e 5.5. The
pe o mance o he wl me hod wi h and wi hou he w me hod wo sens signi ican ly. The accu acy
o he wm me hod is simila o he es wi h a s ep co ec ion o 0.1 m, wi h a posi ioning e o o
2 o 3 m 90 % o he ime. The ww and he w me hods pe o med simila o he es wi h a s ep
co ec ion wi h 0.1 m as well.
37
Figu e 5.5: CDF o he posi ioning e o o he eigh pa h wi hou s ep leng h co ec ion o he
boo s ap PF and he PDR wi hou a s ep co ec ion.
The wl me hod is s ongly e ec ed by he smalle s ep co ec ion, because sho e s eps esul
in ea lie u ns a co ne s, placing many pa icles behind co ne s o walls, blocking he Line o
Sigh (LOS) o he las posi ion. This leads o a back u n o he ajec o y (as seen in igu e 5.6 (a),
leading i h ough a doo in o he neighbou ing oom, while he wm me hod only cu s he co ne a
bi oo ea ly (see igu e 5.6), as he pa icles on he o he side a e in he same oom ( he co ido )
and he e o alid.
38
Figu e 5.6: T ajec o ies om he wl me hod (a)), u ning back and he wm me hod (b)) cu ing he
co ne ; g een do s: es ima ed posi ions, ed a ows: walked pa h
Fo he ze o o ou pa h, a dec ease o he he s ep co ec ion alue o 0.15 m esul ed in highe
posi ioning e o s, shown in igu e 5.7. The wl,ww and wm me hod, all in combina ion wi h he
w me hod, eached a posi ion accu acy o 7.5 m o be e in 90 % o he s eps. The wm and ww
me hods wi h w suppo achie ed an o e all be e accu acy han he w and wl combina ion. The
combina ion o he wl and w me hod could en e he ele a o , bu ailed o ake las u n a he
4 h loo . As in he p e ious es o he ze o o ou pa h, a some posi ions a he missed u n, all
pa icles we e in alid. The wm and ww me hods wi h ou ing suppo on he o he hand missed he
ele a o sligh ly, bu eached he las oom.
39
Figu e 5.7: CDF o he posi ioning e o o he ze o o ou pa h wi h s ep leng h co ec ion o 0.15
m o he boo s ap PF and he PDR wi h s ep leng h co ec ion o 0.15 m.
As i can be seen om he es esul s, a good s ep leng h es ima ion is impo an o each a
high accu acy wi h he boo s ap PF wi h geospa ial analysis. In con as o he andom e o o
he s ep leng h and heading, which is he esul o noisy measu emen s o he IMU, he sys ema ic
e o o he s ep leng h can no be mi iga ed as well by he PF algo i hm. This is especially ue
o he ze o o ou pa h. The eigh pa h mainly leads h ough na ow co ido s wi h many u ns,
which gi es mo e oppo uni ies o co ec o w ongly es ima ed posi ions. The ze o o ou pa h
on he o he hand passes he en ance hall in he g ound loo as well as in he i s loo , p o id-
ing less oppo uni ies o co ec ions o he pa icles’ posi ions, especially in he i s hal o he
ajec o y. Fo his eason, all weigh ing me hods wo k less well, e en wi h a su icien co ec ion
o he sys ema ic s ep leng h e o , o he ze o o ou pa h. Fo bo h pa hs, he wm me hod in
combina ion wi h he w me hod p o ided he bes esul s o e all, ega ding he accu acy as well
as he de e mina ion o he co ec oom, closely ollowed by he combina ion o he ww and w
me hod.
40
5.2 Pa icle Fil e wi h Back acking
The back acking PF has been es ed wi h he h ee di e en concep s check o line o sigh (cl)),
check o oom (cm), check o ou ing (c ) o pa icle checks (as desc ibed in sec ion 4.2). The
CDF o he posi ion es ima e e o o he di e en concep s used o he eigh pa h, wi h a s ep
co ec ion o 0.1 m, is shown in igu e 5.8. The cm and c me hod eached an o e all simila
accu acy, wi h he cm me hod eaching a accu acy o less han 4 m and he c me hod eaching a
accu acy o jus less han 3 m in 90 % o he s eps.
Figu e 5.8: CDF o he posi ioning e o o he eigh pa h wi h s ep leng h co ec ion o 0.1 m o
he back acking PF and he PDR wi h s ep leng h co ec ion o 0.1 m.
The cl me hod pe o med signi ican ly wo se, his is mainly due o he si ua ion ha a a s ep
co ec ion o 0.1 m, enough pa icles a e o e shoo ing a one o he u ns, ending up in he ”galle y”
ha he posi ions o he nex s eps is es ima ed o be on he w ong side o he wall (see igu e 5.9.
41

Figu e 5.9: Pa o he ajec o y o he eigh pa h, ha w ongly p oceeds in he ”galle y”, when
using he wl me hod, black a ows indica ing he walking di ec ion, he g een poin s ep esen ing
he posi ion es ima es o each s ep.
A his poin , he back acking unc ionali y can be obse ed (see igu e 5.10). A he end o
he ”galle y”, wi h e e y subsequen s ep mo e pa icles ge dele ed because hey would c oss a
wall, esul ing in he back acking algo i hm o esample he in alid pa icles a mo e plausible
co ec ions (as explained in sec ion 4.3) and by his, changing he ajec o y o he co ec pa h.
Figu e 5.10: Example o he ajec o y co ec ion ( om (a) o (b)) h ough he back acking unc-
ionali y, he g een do s ep esen he alid, p opaga ed pa icles, he blue do is he esul ing posi-
ion es ima e
This was also an excep ion, whe e he w me hod helped o signi ican ly inc ease he accu acy
42
o less han 4.5 m in 90 % o s eps, by co ec ing he ajec o y close o he nex ou ing edge (see
igu e 5.11). Since he ”galle y” does no con ain any ou ing edges, he ajec o y was di ec ed
back in o he co ido . The e ec o he w me hod was negligible o he o he me hods.
Figu e 5.11: E ec o he suppo h ough he w suppo on he de ia ed ajec o y.
Figu e 5.12 shows he CDF o he posi ion es ima e e o o he ze o o ou pa h wi h a s ep
co ec ion o 0.2 m. The accu acy o all me hods is be ween 5 and 6 m in 90 % o he s eps.
The cm me hod can p o ide an posi ion e o o less han 4 m mo e o en han he wo o he
me hods. F om he h ee me hods, only he cm me hod lead he ajec o y in o he ele a o , while
only he c me hod eached he inal oom. The cm and he cl me hod bo h lead he ajec o y in
he neighbou ing oom, wes o he inal oom.
43
Figu e 5.12: CDF o he posi ioning e o o he ze o o ou pa h wi h s ep leng h co ec ion o 0.2
m o he back acking PF and he PDR wi h s ep leng h co ec ion o 0.2 m.
Fo he eigh pa h wi hou s ep co ec ion, a accu acy be e han 3 m can be achie ed wi h
he cm and cl me hod, while he o e all pe o mance o he c me hod alls behind he wo o he
me hods, as shown in igu e 5.13. The use o addi ional ou ing suppo (w ) e en wo sens he
achie able accu acy o he c me hod. Fo he cm and cl me hod, he c has only a small in luence
on he e o o posi ion es ima e. The cl me hod pe o m signi ican ly be e (also see igu e 5.14),
mainly, because less pa icle o e shoo a he u n a he eas e n co ne . This way he ajec o y
doesn’ de ia e in o he ”galle y”.
44
Figu e 5.13: CDF o he posi ioning e o o he eigh pa h wi hou s ep leng h co ec ion o he
back acking PF and he PDR wi hou s ep leng h co ec ion.
Figu e 5.14: T ajec o y (g een do s) om he cl me hod o he eigh pa h wi hou s ep leng h
co ec ion o he back acking PF
Figu e 5.15 shows he di e en me hod’s CDF o he posi ioning e o o he ze o o ou pa h
wi h a s ep leng h co ec ion o 0.15 m. All me hods, wi h and wi hou he addi ional use o he
45
Figu e 5.21: Compa ison be ween he ajec o ies o he boo s ap PF wi h he wm me hod (a)) and
he back acking PF wi h cm me hod (b)). G een do s ep esen he es ima ed posi ions a each s ep
E en hough he cl me hod o he back acking PF is empo a y de ia ing om he walked ou e
o he eigh pa h, he e ec o he back acking algo i hm, co ec ing he w ong pa h, shows he
po en ial obus ness o he back acking PF.
52

6 Conclusion and Ou look
In his hesis, a boo s ap and a back acking PF algo i hm ha e been de eloped ha use geospa ial
analysis o de e mine he plausibili y o he pa icles based on building in o ma ion. The goal
was o de elop a PF algo i hm ha p o ides a me e scale posi ion accu acy o indoo na iga ion
wi hou he use o GPS o in as uc u e assis ance and allows he use o building in o ma ion in
he GeoJSON o ma .
Fo his, i s he unde lying concep s and me hology we e explained and ela ed wo k was
p esen ed. Then, he concep s as hey we e u he de eloped and adjus ed o his hesis ha e
been explained, including he unde lying ma hema ics, ollowed by he de ailed explana ion o
he implemen a ion in he algo i hms o he wo PF app oaches. Finally he used da a se was
p esen ed and he esul s o he boo s ap and he back acking PF wi h geospa ial analysis ha e
been in es iga ed and discussed.
Fo he boo s ap PF se e al me hods o he de e mina ion o he pa icles’ weigh s we e de-
eloped, namely he weigh ing by line o sigh (wl) app oach, weigh ing by ooms (wm) app oach,
he weigh ing by walls (ww) app oach and he weigh ing by ou ing (w ) app oach. Fo he
back acking PF algo i hm h ee me hods we e de eloped, ha de e mine in alid pa icles based
on di e en building in o ma ion, namely he check o line o sigh (cl), check o oom (cm) and
check o ou ing (c ) me hod.
The esul s o he di e en me hods o bo h PF app oaches ha e been es ed wi h he da a om
wo pa hs h ough he Ha enCi y Uni e si y (HCU) building and ha e been compa ed in ega ds
o he a ainable posi ion accu acy as well as he abili y o de ec ce ain ooms.
Fo he boo s ap PF, he wm me hod p o ided he o e all bes esul s, while he wl me hod
was less eliable in he eigh pa h. The cm and cl o he back acking PF eached a sligh ly
be e p ecision han he app oaches o he boo s ap PF, wi h he cm me hod being a bi mo e
obus . The back acking PF app oaches admi edly needed mo e compu a ion powe , esul ing
in signi ican ly longe un imes han he boo s ap PF me hods, bu hey we e be e in de ec ing
es ima ing posi ion o be in speci ic ooms (e.g. he ele a o o he inal oom in he ze o o ou
pa h). Al oge he i was possible o de elop wo PF algo i hms ha could each an accu acy o
2 o 7 m in mos es cases o indoo na iga ion, by only using building in o ma ion, wi hou
any in as uc u e o GPS suppo , i an su icien s ep leng h es ima ion model is used o he
de e mina ion o he used s ep leng hs.
53
The e is s ill po en ial o imp o emen , especially o si ua ions, whe e la ge hallways p o ide
only li le possibili ies o co ec ions. Fu he , he accu acy de eloped PF app oaches is deenden
on he quali y o he p o ided map in o ma ion, esul ing in be e pe o mances he be e he
map ma e ial is. O all he es ed me hods cm me hod o he back acking PF app oach migh be
a o able, no only because i ’s pe o mance ega ding he posi ion p ecision and oom accu acy,
bu also because addi ional in o ma ion o he accessibili y o ooms can ela i ely easily be
implemen ed. An b oken ele a o could o example easily be decla ed an in alid oom.
The weakness o bo h PF algo i hms on he one hand is he sensibili y o sys ema ic e o s in
he s ep leng h es ima ion and on he o he hand open spaces, ha p o ide li le in o ma ion o
co ec ions. The quali y o he s ep leng h es ima ion could be imp o ed ei he by scaling he s ep
leng h e e y ime an absolu e posi ion can be a ained wi h high p ecision and accu acy, ei he
h ough in as uc u e suppo o when a posi ion is de e mined wi h ela i ely high con idence
ega ding hei co ec ness, o example when using an ele a o change he loo . On he o he
hand machine lea ning algo i hms could be used o a mo e p ecise s ep leng h es ima ion.
Ano he op ion would be o use da a se s o s ep leng h in ela ion o o he biome ic in o ma ion
om a huge numbe o people. Bu hese a e cos ly and ha d o a ain.
Because o he ela i ely simple and modula code s uc u e, i is possible o add o exchange
me hods and unc ionali ies o bo h PF app oaches ha ha e been de eloped in his hesis. This
would also include he addi ional use o posi ion es ima ion om 5G an ennas, as implemen ed
in [24]. Since he al eady calcula ed s ep leng h and heading is used o he PF algo i hms, hei
usage is no limi ed o he use by pedes ians, bu hey could also, o example be implemen ed
o he indoo na iga ion o obo s o any o he mo ing objec , as long as a elled dis ance (which
can easily be calcula ed om he speed) and heading is p o ided.
54
BIBLIOGRAPHY
[1] Pa am i Bahl and Venka a N Padmanabhan. RADAR: An in-building RF-based use loca-
ion and acking sys em. In P oceedings IEEE INFOCOM 2000. Con e ence on compu e
communica ions. Nine een h annual join con e ence o he IEEE compu e and communica-
ions socie ies (Ca . No. 00CH37064), olume 2, pages 775–784. Ieee, 2000.
[2] Mous a a Yousse and Ashok Ag awala. The Ho us loca ion de e mina ion sys em. Wi eless
Ne wo ks, 14(3):357–374, 2008.
[3] Jaewoo Chung, Ma Donahoe, Ch is Schmand , Ig-Jae Kim, Ped am Raza ai, and Micaela
Wiseman. Indoo loca ion sensing using geo-magne ism. In P oceedings o he 9 h in e na-
ional con e ence on Mobile sys ems, applica ions, and se ices, pages 141–154, 2011.
[4] Niklas Ka lsson, En ico Di Be na do, Jim Os owski, Luis Goncal es, Paolo Pi janian, and
Ma io E Munich. The SLAM algo i hm o obus localiza ion and mapping. In P oceedings
o he 2005 IEEE in e na ional con e ence on obo ics and au oma ion, pages 24–29. IEEE,
2005.
[5] S ephen P. Ta zia, Pe e A Dinda, Robe P Dick, and Gokhan Memik. Indoo localiza ion
wi hou in as uc u e using he acous ic backg ound spec um. In P oceedings o he 9 h in-
e na ional con e ence on Mobile sys ems, applica ions, and se ices, pages 155–168, 2011.
[6] Hossein Shoush a i, Thomas Willemsen, and Ha ald S e nbe g. Many ways lead o he
goal—possibili ies o au onomous and in as uc u e-based indoo posi ioning. Elec onics
(Swi ze land), 10(4):1–17, 2021.
[7] Fan Li, Chunshui Zhao, Guanzhong Ding, Jian Gong, Chenxing Liu, and Feng Zhao. A
Reliable and accu a e indoo localiza ion me hod using phone ine ial senso s. In P oceedings
o he 2012 ACM Con e ence on Ubiqui ous Compu ing - UbiComp’12, pages 421–430, 2012.
[8] Changhao Chen, Peijun Zhao, Ch is Xiaoxuan Lu, Wei Wang, And ew Ma kham, and Niki
T igoni. Deep-Lea ning-Based Pedes ian Ine ial Na iga ion: Me hods, Da a Se , and On-
De ice In e ence. IEEE In e ne o Things Jou nal, 7(5):4431–4441, 2020.
[9] Renaud Dub´
e, Daniel Dugas, Elena S umm, Juan Nie o, Roland Siegwa , and Cesa Ca-
dena. SegMa ch: Segmen based place ecogni ion in 3D poin clouds. In P oceedings o he
2017 IEEE In e na ional Con e ence on Robo ics and Au oma ion (ICRA), pages 5266–5272,
2017.
55
[10] Elzbie a Lewandowicz. Ne wo k models o 2d and 3d ca as al da a. In En i onmen al Engi-
nee ing. P oceedings o he In e na ional Con e ence on En i onmen al Enginee ing. ICEE,
olume 9, page 1. Vilnius Gediminas Technical Uni e si y, Depa men o Cons uc ion Eco-
nomics & P ope y, 2014.
[11] Chun Yang, Thao Nguyen, and E ik Blasch. Mobile posi ioning ia usion o mixed signals
o oppo uni y. IEEE Ae ospace and Elec onic Sys ems Magazine, 29(4):34–46, 2014.
[12] Jiaqi Yang, Zhiguo Cao, and Qian Zhang. A as and obus local desc ip o o 3d poin
cloud egis a ion. In o ma ion Sciences, 346:163–179, 2016.
[13] Sachini He a h, Hang Yan, and Yasu aka Fu ukawa. Ronin: Robus neu al ine ial na iga ion
in he wild: Benchma k, e alua ions, amp; new me hods. In P oceedings o he 2020 IEEE
In e na ional Con e ence on Robo ics and Au oma ion (ICRA), pages 3146–3152, 2020.
[14] Neil J Go don, Da id J Salmond, and Ad ian F M Smi h. No el app oach o nonlinea /non-
Gaussian Bayesian s a e es ima ion. In IEE p oceedings F ( ada and signal p ocessing),
olume 140, pages 107–113, 1993.
[15] Chi Ming Esmond Mok, Chung Ming Lau, L Xia, G Re sche , and H Tian. In luen ial ac o s
o decime e le el posi ioning using ul a wide band echnology. Su ey Re iew, 44(324):37–
44, 2012.
[16] Reza Zeka a and R Michael Bueh e . Handbook o posi ion loca ion: Theo y, p ac ice and
ad ances, olume 27. John Wiley & Sons, 2011.
[17] J¨
o g Blankenbach, Abdelmoumen No dine, Hend ik Hellme s, and Edua d Gaspa ian. A
no el magne ic indoo posi ioning sys em o indoo loca ion se ices. In P oceedings o he
8 h In e na ional Symposium on Loca ion-Based Se ices, pages 1–11, 2011.
[18] 3gpp. Release 17. h ps://www.3gpp.o g/ elease-17. Accessed: 2021-07-28.
[19] Ad i´
an Ca dalda Ga c´
ıa, S e an Maie , and Abhay Phillips. Loca ion-Based Se ices in Cel-
lula Ne wo ks: om GSM o 5G NR. A ech House, 2020.
[20] Thomas Willemsen. Fusionsalgo i hmus zu au onomen Posi ionssch¨
a zung im Geb¨
aude,
basie end au MEMS-Ine ialsenso en im Sma phone. PhD hesis, Ha enCi y Uni e si ¨
a
Hambu g, 2016.
[21] Ca ia Real Eh lich and J¨
o g Blankenbach. Indoo localiza ion o pedes ians wi h eal- ime
capabili y using mul i-senso sma phones. Geo-Spa ial In o ma ion Science, 22(2):73–88,
ap 2019.
[22] Widyawan, Ma in Klepal, and S ´
ephane Beau ega d. A No el Back acking Pa icle Fil e
o Pa e n Ma ching Indoo Localiza ion. In P oceedings o he Fi s ACM In e na ional
Wo kshop on Mobile En i y Localiza ion and T acking in GPS-Less En i onmen s, MELT
’08, pages 79–84, New Yo k, NY, USA, 2008. Associa ion o Compu ing Machine y.
56
[23] Chuanhua Lu, Hideaki Uchiyama, Diego Thomas, A sushi Shimada, and Rin-ichi o
Taniguchi. Indoo posi ioning sys em based on ches -moun ed IMU. Senso s, 19(2):420,
2019.
[24] Hossein Shoush a i, Cigdem Aska , Do ian Ha de , Thomas Willemsen, and Ha ald S e n-
be g. 3D Indoo Localiza ion using 5G-based Pa icle Fil e ing and CAD Plans. IPIN, 2021.
accep ed (p ep in ).
[25] Ch is ophe Cappelli. The Language o Spa ial Analysis. Es i P ess, 2013. h ps:
//www.es i.com/con en /dam/es isi es/si eco e-a chi e/Files/
Pd s/lib a y/books/ he-language-o -spa ial-analysis.pd , Ac-
cessed: 2021-07-01.
[26] Donna Peuque . A concep ual amewo k and compa ison o spa ial da a models. Ca -
og aphica: The In e na ional Jou nal o Geog aphic In o ma ion and Geo isualiza ion,
21:66–113, 10 1984.
[27] GeoPandas de elope s. Geome ic manipula ions. h ps://geopandas.o g/docs/
use _guide/geome ic_manipula ions.h ml. GeoPandas documen a ion, Ac-
cessed: 2021-07-02.
[28] Sean Gills. The Shapely Use Manual. h ps://shapely. ead hedocs.io/en/
la es /manual.h ml#bina y-p edica es, 2021. Accessed: 2021-07-02.
[29] Jan Wendel. In eg ie e Na iga ionssys eme. Oldenbou g Ve lag, M¨
unchen, 2011. doi:
10.1524/9783486705720, isbn: 9783486704396.
[30] P ianka Agga wal, Zainab Syed, Nase El-sheimy, and Abeoelmagd Nou eldin. MEMS-
Based In eg a ed Na iga ion. No wood : A ech House, 2010.
[31] M Sanjee A ulampalam, Simon Maskell, Neil Go don, and Tim Clapp. A u o ial on pa icle
il e s o online nonlinea /non-Gaussian Bayesian acking. IEEE T ansac ions on Signal
P ocessing, 50(2):174–188, 2002.
[32] Thomas Willemsen, F ied ich Kelle , and Ha ald S e nbe g. Ka enges ¨
u z e MEMS-basie e
Indoo - posi ionie ung mi els Pa ikel Fil e . In Oldenbu ge 3D-Tage 2015, 2015.
[33] Thomas Willemsen, F ied ich Kelle , and Ha ald S e nbe g. A opological app oach wi h
mems in sma phones based on ou ing-g aph. In 2015 In e na ional Con e ence on Indoo
Posi ioning and Indoo Na iga ion (IPIN), pages 1–6. IEEE, 2015.
[34] F anco P P epa a a and Michael I Shamos. Compu a ional Geome y – An In oduc ion.
Sp inge Ve lag, 1988.
[35] G inbe gni . Codep ojec - is a poin inside a polygon? h p://www.codep ojec .
com/Tips/84226/Is-a-Poin -inside-a-Polygon. Accessed: 2021-07-20.
57