Device Has Been Forcibly Removed Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

For Android, a framework called Google Cloud Messaging exists for this specific purpose, allowing a server to send a message complete with a small payload up to 4kB to a pre-registered device. The intention is that such a message may either be self-sufficient, in that the payload is all that is required, or the phone is instructed to request the server for additional data (pull).

GCM works through an authenticated server sending messages to a pre-registered device and application. If an application wishes to receive GCM messages, it must call a function registering it for the service, issuing it with a unique composite key for the device and application. This key is then sent to the server and stored along with the device details in the database through the use of the REST API. The application server must also be registered to communicate via GCM, with each request to the service being sent along with a validated API key. This is shown in appendix 6.7 figure 3.

Sending GCM messages to Android applications from a Java application server has been made trivial thanks to Google's implementation of a package of GCM support classes, which are freely available for download. It is then possible to simply create a new sender object, which takes the server API key, and the application/devices unique GCM key as parameters. Messages are formed from key-value pairs, where the key may be used as an index, and the value contains the payload. From this, sending the message is a simple case of calling the send method on the sender object, and passing in the message as a parameter.

Database Setup

Installation of the database software on the same physical machine as the application server has been achieved with a composite package of software called XAMPP. XAMPP is an "easy to use Apache distribution containing MySQL and PHP" as well as Apache web server, and phpMyAdmin [46]. A useful side effect of such a package is that components are automatically configured upon host installation to interact with one another correctly, making management and initial setup exceptionally easy. Apache webserver also makes it possible to remotely manage the MySQL database in a browser through the useful phpMyAdmin software [47].

The database has been configured relationally with nine tables as illustrated in the design section of this document. Such a design affords maximum data efficiency and performance to the application. The SQL written to build the database in this way is included in Appendix X. At the time of writing, the database currently holds a total of 16,565 entries, the majority of which are location updates from various test devices.

Geofence Computation

This section details the method which has been employed in order to provide location alerts to subscribed devices based on the two types of geofence that are called for in the requirements specification: radial and polygonal. This particular section only deals with the computation of geofences and related alerting from a server perspective. Application side implementation of geofence management and display is provided in the parental application implementation section.

The Geodesic Problem

While many algorithms exist for determining the distance between two points (or indeed determining if a point exists within a polygon), the vast majority of these make a simple assumption: the points will be Cartesian, and exist in Euclidean space. The most fundamental assumption from these algorithms is based on the parallel postulate (also known as Euclid's fifth postulate). This postulate states that if a line is intersected by two lines that are non-parallel, they must always meet on the side which neither of the interior angles are right angles [48]. While this assumption is perfectly valid for points existing in two or three dimensional planes, the rule fails when applied to points in elliptic space. This can perhaps best be visualised when imagining a triangle. Euclidean mathematics states that the sum of the internal angles of a triangle add up to 180°, however when such a triangle is applied to a sphere such as the earth, this no longer holds true as illustrated in figure 6. From this it is clear that while for small areas the angular assumption holds (the area is so small that the earth is virtually flat), for larger triangles the edges simply are not straight.

Figure 6. Internal angles of triangles applied to the earth [49].

The result of this issue is that new algorithms must be developed or researched in order to solve the problem in the scope of this project. As can be seen from figure 6, while using a conventional Cartesian algorithm for small scale geofences would probably be acceptable, ideally the solution needs to be capable of scaling to fences of any size.

Radial Geofence - Distance between Two Points

Radial geofences can be thought of as a way of illustrating a concept that is essentially formalised as the distance between two fixed points on the earth, as shown in figure 7. A device lies within a geofence if the distance between it, and the centre of the circle is less than the radius of the circle.

Figure 7. A Radial Geofence in the TrackiT application.

Conventional approaches to the issue of finding the distance between two fixed points (P1, and P2) involve something along the lines of the following:

Distance =

essentially forming a triangle about the two points, with the line between them forming the hypotenuse. Pythagoras' theorem is then used to calculate the distance.

Coming back to the geodesic problem, the result of applying this formula directly to a pair of geographic coordinate system (latitude and longitude) points is shown in figure 8.


Figure 8 (left). Comparison of Geodesic and Cartesian paths, Earth image [50].

Figure 9 (right). Small and great circles on a sphere [51].

In this illustration the paths shown represent the hypotenuse of the aforementioned triangle, highlighting a clear problem: there is a large disparity in their length. This disparity is unacceptable to this application, and as such a solution has been implemented.

When applying a polygon to a sphere it is important to be aware of the fact that each of the polygons edges are no longer straight, but actually form an arc. When such an arc is applied to the earth, these arcs are known as portions of either great or small circles, with the difference between the two being shown in figure 9.

As such, when calculating the shortest distance between two points (and forming a triangle) the resulting algorithm needs to cater for the nature of the sphere upon which the shape rests. The solution to this is the Haversine Formula which is used to calculate the great circle distance between two points on the earth based on a pair of latitude and longitudinal values. This formula is implemented in Java based on the work of R.W. Sinnot as follows [52]:

Code in appendix?

D:\Skydrive\Documents\Project\Report\Diagrams\Exists in radius.jpg

Figure 10. The Haversine formula in action.

This then forms an essential part of the following algorithm which is used to determine if an alert should be issued or not:

For each device location update

Load details for the device, including its parent's username

Load all radial geofences for this parent

For each radial geofence

Determine if the device the device exists inside or outside of the fence based on the haversine formula

Based on historical information in the database determine if a fence cross has occurred:

If the device was inside the fence on the previous update and is now outside of it

If the device was outside of the fence on the previous update and is now inside of it

Issue an alert, else

Do nothing

End for

End for

A similar method is used when an update occurs to a geofence (i.e. its radius is edited, or its centre point is moved), except instead of looping over each fence for that parent, the application loops over each device for that parent.

Point in Geodesic Polygon

A significantly more complicated extension to this problem is attempting to determine if a point exists in a geodesic polygon. Determining if a point exists within a simple polygon is a problem that has existed in computer graphics since their inception, with evidence of practical solutions as early as 1974 [53]. As with the aforementioned radial geofence computation, a number of well-established algorithms now also exist for solving the point in polygon (PIP) problem. Again however, the majority of these solutions are only designed to work with Cartesian points existing in a Euclidean space presenting the same issues of practical accuracy upon implementation. The most common of these and one of the most efficient is the ray-casting algorithm.

Naïve Approach: Ray casting

Ray casting in the context of PIP works by determining the number of intersections a straight line makes when travelling from the exterior of a polygon to the point being tested as shown in Figure 11. If the number of intersections is odd, the point lies inside the polygon. Ray casting as a method of resolving PIP has become increasingly popular thanks to its simple underlying methodology, removing the need for complicated trigonometry as required in other algorithms involving angular computation. As with other PIP solutions however, the ray casting algorithm is defeated by points lying on an elliptical plane, owing to the fact that the edges of a polygon are actually sections of a small circle and not a straight line.

Figure 11. Cartesian Ray Casting showing Edge Crosses

For the same reasons as a Pythagorean algorithm fails to accurately compute the distance between two geodesic points however, Ray Casting fails to accurately determine if a point exists within a polygon. The same constraints apply: the method is suitable for small polygons that do not approach the meridian, at which point the "wrap-around" nature of the geographic coordinate system bamboozle the algorithm further.

NASA Approach: Great Circles

A 2007 NASA paper on algorithms for spherical polygons first attempted to formalise a solution for this problem [54] through the calculation of small and great circle intersections. A conventional ray casting algorithm calls for a line drawn from the test point to a point known to be outside the polygon, so for the purpose of geodesics a great circle is drawn from the North Pole. The algorithm then evaluates this great circle against each of the small circles formulating the polygon in question in order to determine whether or not the test point lies within said polygon. A small circle is defined as a spherical section that does not contain a diameter of the sphere [55]. Inevitably however, given the complex nature of the mathematics involved (and the fact that the earth is not a perfect sphere) the resulting algorithm is exceptionally complicated, and beyond the reasonable scope of an undergraduate project.

Simplification and Optimisation: Projection

Upon realising the scale of this problem and the difficulties involved with meeting this particular key aspect of the requirements specification, some significant research was undertaken, including an attempt to implement the NASA algorithm. While partially successful in doing so, it was decided that the solution was far from optimum due to the mathematical complexity involved. It was at this point that a rather more innovative idea was formulated: instead of trying to manipulate the algorithm to suit the problem, why not try and manipulate the co-ordinates instead.

While researching the problem space extensively, another mathematical technique was uncovered, with far deeper historical roots in navigation than this relatively recent and under-researched area. Realising the need to carry accurate paper printed maps; early explorers and navigators developed a system known today as map projection, allowing them to display the spherical earth on a plat piece of paper. A map projection is defined as "a systematic transformation of the latitudes and longitudes of locations on the surface of a sphere or an ellipsoid into locations on a plane" [56]. This then means that in the context of this project, latitudes and longitudes can be projected out of Elliptic space and into Euclidean space; making the use of conventional algorithms possible without losing accuracy.

As map projection is a fairly common application (having been used for hundreds of years), a number of useful open source libraries exist for its application. Google maps makes use of a technique known as a Mercator projection for displaying its mapping data on a plain, and considering Android is the platform of choice, a Mercator projection will be employed on the server also. A library exists for such a projection, providing a mechanism for converting latitudes and longitudes into x and y Cartesian coordinates [57]. A Mercator projection is particularly relevant to this project thanks to its ability to maintain accuracy at a scale of order of a few kilometres, which realistically is the most important to this project. While some accuracy is lost at larger scales, projecting in this manner is still far more mathematically correct than simply ignoring the shape of the earth altogether!

Convex polygons representing the convex hull sent from the device are stored in the database (along with other meta information relating to historical device locations relative to the hull) as a set of latitude and longitude points bound by a group. Once these have been loaded into a custom hull point class, a projection is made of each point to gain its Cartesian coordinate value. In order to determine if a point exists within the polygon represented by this point set, it is required to first affirm that this set of points does indeed form a convex hull: if it does, order it clockwise from the bottom, if it doesn't extract the ordered subset. Full details of the convex hull implementation can be found in the section relating to the parents device, however the same divide and conquer O(nlogn) algorithm is used. Once this algorithm has been run, the result is an ordered convex hull representing the target geofence polygon in Euclidean space. The resultant point set can then be run through a Ray Casting algorithm with the device location used as a parameter representing the test point, as shown in figure 12.

D:\Skydrive\Documents\Project\Report\Diagrams\Ray Trace.jpg

Figure 12. Applying a Ray Cast to the PIP Problem.

Code in appendix explicitly?

The pseudo algorithm shown for the entire alerting application flow for radial geofences is used in the same way for convex geofences.

This particular method of determining location information based on a freely drawn complex polygon has never before been used in a publically available application or piece of research, making this feature truly innovative. The commercial and academic review conducted in section 2.1 shows the rarity of such a feature, and its practical benefit has already been discussed. What makes this solution so unique however is its remarkable simplicity, achieved through the application of two well established techniques: map projection, and the PIP Ray Cast. The result is a highly flexible and accurate (as confirmed in testing), yet high performance avant-garde alerting framework which can be innovatively employed throughout the rest of the project.

Child Application

This section contains information details regarding the development of the child location tracking application for Android smartphones. Initially the application server was developed for use with a third party application, Big Brother GPS [58], however once initial server development completed, a custom TrackiT application was developed.

Networking and Web Services

Connection to the public TrackiT API is provided through a dedicated and asynchronous network class. Ever since the release of Android 3.0, Google have enforced the spawning of an additional thread when performing network operations for the simple reason of not hanging the main thread running the user interface [59]. For this reason, the TrackiT class used to perform network operations extends the built in AsyncTask class: this allows operations (such as networking) to run in the background. Parsing of response bodies including JSON is also done on this new thread, ensuring the main thread is never locked. This is particularly relevant for the TrackiT login screen, shown in figure 11, where information is supplied to the user through the display of a loading icon.

The custom TrackiT networking class has an additional benefit of being completely generic. The idea is that instead of having repeated network handling code distributed throughout the application, a call can be made to a class function with the only parameters required being a URL, and a list of key value pairs.

SSL Certification Problems

Connection to the TrackiT application service is provided through a secure SSL tunnel running as part of the HTTPS protocol, ensuring personal location and user credential data is kept secure. Android includes a number of functions to assist with making an SSL connection to a server, such as those found in the Apache HTTP Client class. As was mentioned when configuring the server however, the SSL certificate used is self-signed, presenting an issue: Android will not accept connections to servers presenting self-signed certificates (it is a potential security risk). There are two solutions to this:

Purchase a signed certificate from a certificate authority recognised by Google (expensive!)

Craft an alternative

There are two ways that this problem can be overcome:

Accept any SSL certificate: this is insecure, as any attacker could spoof the TrackiT server, and thus capture users private information, destroying the whole security architecture the project is working towards

Add the TrackiT server certificate to a secure key store, and check this explicitly during the handshake.

Clearly, the later of these two options is the only reasonable solution in the contexts of this project; unfortunately however the complexities are somewhat acute. The following solution is based on the research of Antoine Hauck [60]:

Obtain the TrackiT servers SSL certificate as published to connecting clients

This is achieved by connecting over SSH to a Linux machine, and executing the following command:

openssl s_client -connect {}:{2610} -showcerts

Save the resulting certificate in a .cer certificate file

Download the Bouncy Castle Crypto API [61]

Create a new secure key store, insert the server certificate, and use the Bouncy Castle API to encrypt it

keytool -importcert -v -trustcacerts -file "users/james/trackit/serverCert.cer" -alias IntermediateCA -keystore "users/james/trackit/clientKeyStore.bks" -provider org.bouncycastle.jce.provider.BouncyCastleProvider -providerpath "path_to_bouncycastle/bcprov-jdk.jar" -storetype BKS -storepass ##password

Create a custom HTTP client which extends the built-in default HTTP client, overriding the Client Connection Manager. This function is where SSL certificate checking occurs, and the methodology is fairly simple:

Register a new SSL Socket Connection (port 2610), using a custom SSL Socket factory:

Load the secure key store (which has been distributed with the App)

Initialise and open the key store using the password entered upon creation

Load the server certificate from the key store

Create an instance of the default socket factory

Insert the server certificate as trusted, along with those from verified authorities

Return the custom SSL Socket Factory

Return the custom Client Connection Manager.

When an SSL connection is established, only trusted certificates are allowed, and this process now checks the certificate received from the server against the usual list, but also the TrackiT certificate inserted. The claim is easily verifiable, and has been tested by generating a new server certificate: the SSL connection is refused.

Acquiring the Latest Location

Locations on mobile devices can typically be acquired using a number of methodologies, each of which has benefits and costs associated with them:

Cell tower ID: Fast acquisition, low battery impact, inaccurate

WiFi: Low battery impact, fast acquisition, only works if in range, inaccurate

GPS: High accuracy (10m), slow acquisition, high battery impact

On the Android platform, an optimum solution is to begin listening to location updates from all of these sources, and then use an algorithm to determine which location is optimum based on its age, accuracy, and trust (based on the type of provider). Such an algorithm is given by Google as an example and has been adapted for the purposes of this project [62], as shown in figure 13. Source in appendix

D:\Skydrive\Documents\Project\Report\Diagrams\Get Best Location.jpg

Figure 13. Algorithm for comparing two locations.

Location updates can be requested either after a set period, or on a significant location change. Unfortunately neither of these is guaranteed, which presents an issue: the system requires regular and accurate location information. The solution to this is to set an alarm. The alarm triggers every two minutes, at which point the current best location is processed.

Services: Running in the Background

In order to provide this information consistently when the application is closed or the phone is sleeping, a service is required. In the context of the Android platform, a service is a defined as "an application component that can perform long-running operations in the background and does not provide a user interface" [63]. This essentially allows developers to run tasks for an indeterminate length of time (known as a foreground service: there is a small icon in the notification centre indicating activity), and receive notifications when the service is shut down. Such services can also be loaded when the device starts: ideal for this application.

Initially a custom service was written for this purpose, however issues were encountered when attempting to process locations when the phone is sleeping. Conventionally this is overcome through a process called wake locking: allowing the service to wake the device up. A more optimal solution is to use a library called LocationPoller [64]. LocationPoller also works by setting a two-minutely alarm, and waking the device up ahead of time in order to acquire a location fix. This means the project requires two services:

Location Poller: wakes the device up ahead of time every two minutes and acquires the best location available

TrackiT Location Service: Listens to updates from the Location Poller and processes them to determine the best available location based on the previous algorithm. This location is then sent to the server.

Battery and Performance Optimisation

By sending the device to sleep in-between processing concurrent location updates, battery and performance efficiencies are maximised. The results of battery longevity studies are shown in the relevant testing section.

On-demand Location Updates

On demand location updates can be requested from the device by the server as a result of a push notification via GCM. When such a request is received, this works asynchronously:

Send the current most accurate location available from the devices location cache (this is updated by any location aware application on the device)

Attempt to acquire an up-to-date GPS location fix, send it when it arrives (this can take up to two minutes).

Remote Wiping the Device

Remote wiping of the device in the event of permanent loss or theft can be achieved through a command issued from the administrating web interface. When the device receives a GCM message with the remote wipe flag set, a number of things occur:

Delete the TrackiT authentication token

Set the TrackiT authenticated flag to false

Stop both of the location services

If active, disable the map view, and return the user to the login screen

Issue an audible alert to the effect that device has been remotely disabled.

GCM Token Update Problem

Integrating GCM into a client application is very easy. GCM runs as an independent background service on the platform, and in order to receive messages from it the application simply has to register with the service, and define a class in which messages will be placed. This technology is known as a broadcast intent. When the application first starts, the registration process returns a unique application/device key from the Google Servers, known as the GCM key. Unfortunately, Google do not guarantee that this key is static (i.e. it might change), and during testing the key invalidated itself. The painful result of this is that every time the application starts, the device must re-register with the GCM service, and then transmit the key it receives to the application server. The application server can then store this key in its database, and use it for future push notifications.

Overall Application Flow

Black Outline indicates main application

Blue Outline indicates LocationPoller (third party) service

Red Outline indicates TrackiT service

Green Outline indicates TrackiT server Need to add GCM push responses


Figure 14. Overall Flow of the Child Application.

Parent Application

This section details the implementation of the Android based parent application, which provides the majority of the user interaction for the application, including:

View real time and on demand location information from children on a map

Add, edit, and delete radial and polygonal geofences

Receive alerts when geofences are crossed

View detailed device information including battery life and advanced positional statistics.

Many core components are shared with the child application in relation to networking, security, remote wiping, and user & device authentication.

Start-up Procedure

Login and initial setup procedure is the same as the child application (figure 14) with respect to the authentication of credentials, the storage of tokens, and the updating of the TrackiT server with the latest GCM token. Add stuff on fence loading on startup

Size Adaptive User Interface

The requirements specification calls for an application that is suitable for both tablet and smartphone sized devices. There are two approaches to this: develop two applications, or develop one application with a single UI that is scalable to any screen size. In the interests of project scope, the later method is chosen, despite the inevitable complexity brought to the project. Fortunately the Android SDK includes a number of layouts suitable for this particular purpose. While there is a degree of trade-off in usability when attempting to scale an interface between multiple screen sizes, it is felt that given the lack of UI complexity for this project, the trade-off is worthwhile. The chosen layout from the SDK is called "Tabs + Swipe", allowing a user to swipe between various tabs, as illustrated in figure 15. When run on a smaller display, tabs along the top and buttons in the menu bar automatically rearrange themselves for more suitable accessibility.

User Interfaces for Android are developed and manipulated using simple XML constructs, with the interface elements then instantiated in Java code through a process known as expansion. Full XML for the application user interface can be found in the appendix. A screen shot of the main application view running on a tablet is shown in figure 15.


Figure 15. The TrackiT Parent application running on a Motorola Xoom tablet.


Mapping for the Android platform is provided, as one might expect, by the Google maps platform. Unexpectedly, this caused a serious issue early in the project: the application was developed using version 1.0 of this mapping technology (which was the current at the time), however midway through development Google deprecated this in favour of a new version. While this new version provided a host of new features, including improved vector graphics, smoother pan/zoom functionality, and the ability to change the angle of attack, it also had a whole new API, requiring a complete redevelopment from the ground up. The change was so vast that even simple elements such as map overlays were not transferable from the old API to the new one.

Access to the mapping platform is fairly straight forward: simply obtaining an API key, instantiating a particular fragment (a UI component), and providing the fragment with the API key through the Android Manifest results in a working map. The majority of common tools are also built in, including all those expected for reasonable user navigation, saving significant additional work. It is then possible to add overlays to the map in a number of forms, notably markers, and lines (referred to as polylines).

Drawing on the Map

Drawing on the map and handling multiple objects has been made a little more difficult in the second version of the mapping API. In order to do so, a custom class must be written for each type of overlay object wished to be placed, with this then kept track of in a data map in the fragment responsible for the map fragment. For this project, seven distinct data structures are required for overlay storage and operation (including two indexes to reduce overall processing time):

Map of Google Map markers to Radial Geofence Marker objects containing specific implementation for managing the geofence (dialog, polyline etc.)

Index map of Google Map marker id to Radial Geofence marker for fast lookup on marker tap

Map of maps containing Convex Geofence Group id : map containing Google Map marker id to Convex Geofence Marker

Index map of Google Map marker id to Convex Geofence Marker for fast lookup on marker tap

Map of Convex Geofence Group id to associated polyline (the line representing the fence)

Map of device id to TrackiT Device Marker

Index map of Google Map marker id to TrackiT Device Marker for fast lookup on marker tap.

Location Markers

Each time a new location update arrives from the background GCM service, it is asynchronously sent out (as JSON) to all registered listening components through a process known as broadcasting. One of these registered components is the map fragment. Each time an update arrives at the map fragment a fixed process occurs, as shown in figure 16. The goal of this is to add a new (or update an existing) phone icon on the map view, and alert the user to its presence through some subtle animation.


Figure 16. Process illustration for when a new device location is received via GCM.

The user's current location is also displayed as a small blue marker with a circle around it (representing location accuracy). Tapping on the target icon in the top right hand corner of the screen (as in figure 17) refreshes this location, and pans/zooms the map to it.

Radial Geofences

Radial Geofences are TrackiT's implementation of the common distance from a fixed point alerting feature, with this distance illustrated on the map fragment in the form of a circle around a centre point. The aim is to provide users with the ability to:

Add and visualise a radial geofence

Modify the size of the fence, and have this update the UI

Drag the centre marker of the fence and have this update the UI

Save changes to the fence and have them persist across multiple devices.

From a user perspective, adding a new radial geofence to the application is simply a case of tapping the "Add Radial Boundary" button on the top tool bar, as shown in figure 17.

C:\Users\James\AppData\Local\Microsoft\Windows\Temporary Internet Files\Content.Word\Screenshot_2013-04-09-19-18-19.png

Figure 17. Adding a new Radial Geofence in the Parent application.

Once added, the user is then able to tap on the resulting marker and manipulate the geofence (radius shown in meters), as shown in figure 18. Each marker is also fully draggable with the radial geofence updated on the screen in real time as the marker is moved. Once saved, the geofence is securely sent to the TrackiT server and propagated to all other registered parent devices on the current account. The fence also becomes active, meaning that any registered child device that crosses the virtual boundary will trigger an alert.

C:\Users\James\AppData\Local\Microsoft\Windows\Temporary Internet Files\Content.Word\Screenshot_2013-04-09-19-31-42.png

Figure 18. Manipulating an existing Radial Geofence.

Calculating the circular polyline that represents the geofence is somewhat complicated, as such a fence must be calculated as a user drags/resizes it with respect to the elliptic nature of the earth. This is achieved through looping over every 4th degree between 0 and 360, and plotting a red line between each gap with respect to the centre of the geofence and its radius:

This calculation is performed dynamically updating the polyline each time a radius is changed (by dragging the slider in figure 18), or the central marker (figure 17) is dragged. The main difficulty experienced when handling radial geofences was with keeping track of multiple markers and multiple related properties. For example, each marker has an associated radius value, radius text, polyline, slider, and dialog box. The solution to this was the creation of the RadialGeofenceMarker class which handles all of these attributes, along with methods to access them. Such methods include listeners which determine the exact object behaviour when a marker is tapped, dragged, or a slider value updates. The overall flow of this is shown in figure 19.


Figure 19. Process illustration for Radial Geofence objects.

Polygonal Geofences

Similar functionality exists for Geofences that are polygonal in nature, with the additional technical complexity of managing not only multiple individual markers, but successfully holding these together under group ids. This proved to be one of the biggest technical challenges of the project: maintaining a group id after it had been allocated by the server and the application had been restarted.

Users can add a new freeform boundary by tapping the relevant button in the tool bar. Doing this enables a listener (tap to add) on the map view which is triggered by users tapping on the map; used to add a new flag marker to the current group. Once there are more than four flags on the map, the application begins dynamically re-computing and redrawing the convex hull of all points as shown in figure 15. The process for this is shown in figure 20.


Figure 20. Process illustration for adding Convex Geofence markers.

Once a geofence has been saved, the "tap to add" functionality is automatically disabled. Re-enabling this functionality starts drawing a new fence, although users can edit existing fences by dragging and deleting markers. The following actions are supported:

Add markers to extend or reshape the geofence

Drag markers to reshape and re-compute the geofence

Save and delete the entire geofence group, updating all associated markers

Assign a "friendly name" to the geofence group, which is used in subsequent alerts.

Each marker is fully interactive, supporting both tap and drag functionality. Tapping on a geofence marker that is forms part of the group provides users with a dialog, the properties of which are loaded in the same way as for radial geofences: based on a series of hash maps and indexes. Such a dialog is shown in figure 21.

Figure 21. Properties dialog of a Polygonal Geofence with the fence shown in the background.

When a user saves a geofence for the first time, the details of each marker comprising the geofence group are sent to the server, with the ids of all markers and the group itself set to -1. This indicates that the geofence has never been saved before, forcing the database server to assign a new id to each marker and group. The server will then respond to the application with a success flag once the new ids have been assigned, which are then retained in memory. This group id association allows the application to keep track of various geofence attributes (such as friendly name) when handling multiple similar fences at the same time. Geofences are deleted as a group, with the command sent to the server, and the fence itself only removed from the application once the server confirms its deletion from the database, resulting in an atomic transaction.

Drawing a Convex Hull

This was perhaps the single biggest technical challenge of the entire project. As has been discussed, attempting to compute Cartesian shapes on an elliptic plane is a major technical and mathematical challenge. In order to produce an intuitive UI however, this needed to be done in real time as users added new and manipulated existing markers. Given the algorithm is to run on a mobile device, it needs to be exceptionally efficient so as to reduce the overall load on system resources and battery drain.

Computing the Convex Hull of a set of points is a fairly classical computation problem, with the most efficient algorithms calculating the hull in O(n log n) time. Perhaps the most popular of these is the Quick Hull algorithm, which employs a divide and conquer strategy [65] to compute the point set as efficiently as possible. An additional complexity to this problem however is that not only must the hull be recomputed each time the point set changes, it must also be recomputed each time the users map perspective changes (i.e. each time they drag, pan, zoom, or change the attack angle).

In order to display an accurate virtual fence with respect to the curvature of the Earth, the same Mercator projection method used in alerting and drawing radial fences is used. A condition of the implementation of this on the Android platform is that each projection is computed with respect to the user's current view of the world. That is, the projection values are scaled based on the current visible area of the map. The result of this is that each time the perspective changes, a projection must be performed on each hull vertex and the hull recomputed for accuracy (shown in figure 20). The following implemented algorithm is based on the divide and conquer method taught in the CS2G7 Essential Algorithms module:

Algorithm DCHull (P : set of points)


if (sizeof(P) < minsize )

return ConvexHull (P)

else {

split(P, L1, L2); // divide P into two distinct lists L1, L2

return Merge(DCHull(L1) , DCHull(L2));



The remainder of the flow for this type of geofence is the same as for radial fences, with the additional complexity of storing markers in groups, and retaining group assigned as well as marker assigned ids from the application server.

Location on Demand

Detailed Device Information

Multi-user Multi-device Capability

On fence change, push

Receive fence changes

Vulnerabilities: Data Stored on the Device

No personal information is ever stored on the device. Everything is loaded on demand from the TrackiT application server over a secure SSL tunnel, and stored transiently in memory only for the time that the application is active. This ensures in the case of loss, data cannot be extracted by a felon. The only information permanently stored on the device is related to authentication:

A flag indicating a successful login

A copy of the devices authentication token allowing it to communicate with the server

A copy of its GCM token enabling it to receive encrypted push messages from the server.

When the device is remotely wiped, these three data items are permanently removed.

Parent application


Drawing on the map, managing multiple objects

Loading data on demand

Loading points on startup


Nothing stored on the device, ever

Saving data to the server

Keeping multiple parents in sync

Amending geofences


Remote wipe functionality

The whole GCM push issue

Maybe talk about icon sizing

Web application

Authentication and cookies

CSS/static content serving issues

On the fly creation and delivery of dynamic HTML (DHTML)

API hook ins

List of technologies and languages employed

Technical difficulties review

Example flows

Class diagrams

Check log, make sure nothing missed

Server flow charts

Overall flow chart for entire application flow

Testing and Quality Strategy

Functional testing

Web location simulator

Unit test

In the wild tests

Load testing the API and database connectivity

Resulting changes to improve efficiency

User tests

Google Code analytics

Toms tool for checking Java correctness

Test Results, Correctness and Proceeding Actions

How it meets MOSCOW, and original requirements

Future Development

Ideas to rake forward

Ideas to discard


Project Review


Project management review

Project statistics - lines of code, development time, languages used etc

Review MoSCoW - show what was and what wasn't done in a table :)

How project differed in the end from original proposal

Retrospective time breakdown


Basically this project is going to change your life.

For the worse.

Project inception

Problem space

Requires a solution

What was required, why

How it was delivered

Why it's awesome

User guide

Screen shots of the application on tablet, phone, child application etc. The whole enchilada


Risk Register




Anderson - supervising the project

Bushby for the freeform drawing concept based on the original project idea