Ray Casting Algorithm

If you’ve been struggling with the problem of determining whether a point lies inside or outside a polygon, perhaps in google maps, read on. This post is specific to Android and Node.js but the algorithm can easily be implemented in any other language/platform as the algorithm itself is a piece of cake once understood.

Read more


Voronoi: A solution to proximity based problems

In computational geometry, Voronoi diagram is a partitioning of a plane with n points into n convex polygons such that each polygon contains exactly one generating point and every point in a given polygon is closer to its generating point than to any other. A Voronoi diagram is sometimes also known as a Dirichlet tessellation. GeoVoronoi is an extension of Voronoi optimized for geo locations.

vor1

To dive deeper into Voronoi geometry, read chapter seven of Computational Geometry: Algorithms and Applications. Or maybe play with this cool demo.

If you're working on any proximity-based problem, Voronoi diagram can be a lot of help. In layman's language, Voronoi diagram divides a 2-D plane with n sites into n zones, one for each sites, such that any point inside the zone is nearer to the site that owns the zone as compared to any other sites. In the above Voronoi diagram, 'a' is a site and 'v(a)' is its zone.

In my particular use case, I've been creating a proximity based mobile app that needs to know which site is nearest to the device during each location update. The zone information provided by Voronoi diagram saves me from polling among distances from each site upon each location update. Now I just need to check which zone the device is currently inside of and would poll among the zones only if the device moves out of the current zone. This optimizes the process multiple folds.

I'm extending this Javascript implementation of Voronoi diagram. Although it works perfectly for a normal X-Y plane, it wouldn't quite fit in for geo locations. So, I've written a geo wrapper over it, namely, GeoVoronoi which basically does the following patch-work:

  1. Longitudes don't stay linear near the international date line. They discontinue and go like '..., 178, 179, -179, -178,...'. GeoVoronoi would take care of this.
  2. Auto-boxing super area of sites with optimal padding. (Bbox in code).
  3. Keeping latitude-longitudes sanitized in terms of range and decimal places.

Usage

Input an array of sites(latitude-longitudes) and a voronoi-graph will be returned to you. The information inside voronoi graph can be used to do calculations, to determine zones and even to draw the Voronoi diagram on a plane, Google Map, etc.

I've created an npm package for geovoronoi here. To install this package use the following command:
npm install geovoronoi

Above code will generate voronoi-graph data. This voronoiGraph object contains following three major objects and a key-value for execution time:

  1. cells: This contains information for all the polygons(zone) along with their owner sites. A polygon is represented by halfedges (called so as most of them are shared among two adjacent polygons). Each half-edge has start and end vertices called 'va' and 'vb' respectively. Set of start vertices of all half-edges will be all the vertices of the polygon. Information of cells is enough for basic calculations.
  2. edges: This contains information about start and end points of all the edges in the resulting Voronoi diagram.
  3. vertices: This contains information about all the vertices in the resulting Voronoi diagram.

Please refer to this README for the data inside cells.

If you found this post interesting go explore more about Voronoi. Leave a comment about your use case. You might also want to take a look at my post about Ray casting. It will help in determining whether a point lies inside a polygon or not.


Communication patterns for application components

Activities, services, fragments, helper classes etc. are main components of Android applications but its tricky to establish communication between these components. It’s tricky when one cares about writing reusable code – loosely coupled, plug-n-play-able. The goal here is to avoid tight coupling.

Tight coupling - Components keep references of each other and call methods on them directly. In the code below, we are keeping a reference of MagazineActivity inside MenuFragment. So, MenuFragment is tightly coupled with MagazineActivity i.e., it cannot function without MagazineActivity.

Read more


Fragment view state retention: A dirty solution

This is the last part of this 6 part series about Fragment Oriented Architecture in Android applications. In the previous post I talked about managing sessions in fragment oriented application. In this post I am going to talk about retaining view hierarchy of a Fragment after removing it from container and then coming back to it by popping the backstack.

(Sample application's source code and README)

When a fragment gets replaced by another fragment and the transaction is added to back stack, the expectation after a popBackStack() is to return to the previous fragment with its UI state intact. Activity backstack takes care of this expectation quite cleanly until a low-memory situation occurs. But in case of fragments, this isn't the default behaviour. In a vanilla implementation, the replaced fragment's view-hierarchy would get recreated upon returning back to it. Reason is that during a replace operation, all the destructive life-cycle methods get called till onDestroyView(), which wipes out the view-hierarcy. Upon returning back, all the constructive lifecycle methods right from onCreateView() get called, thus, recreating the view-hierarchy totally afresh. Reason for this flow is to keep 'Fragments' memory friendly. Without the view-hierarchy, a fragment is just a java object with a bunch of instance variables.

Read more


Session Management

This is the fifth part of a 6 posts series on Fragment oriented application architecture. In the previous post I talked about efficiently handling back button press inside fragment. In this part I am going to talk about session management in Fragment oriented application, by explaining integration of Facebook SDK.

(Sample application's source code and README)

In a fragment oriented application, we can conveniently manage all session related code in the activity and all its fragments would utilise it. Facebook SDK is quite in sync with this approach. Implementation of Facebook session is closely bound to an activity. And then this session is accessible throughout the application. As has been discussed before, if an application requires to sign in from different portions of it, it will be way more convenient to have those portions as parts of the same activity. So that the authentication code need not be duplicated.

Read more