Wednesday, September 1, 2010

Building a Custom 2D Map Component from Scratch using Virtual Earth

References

  • Bing Maps Tile System (http://msdn.microsoft.com/en-us/library/bb259689.aspx) - Describes the tiling system and gives C# code for converting between coordinate systems.
  • Virtual Earth Deep Zooming (http://www.silverlightshow.net/items/Virtual-earth-deep-zooming.aspx) - Among other things it describes the URL format for tiles.
  • Calculate distance, bearing and more between two Latitude/Longitude points (http://www.movable-type.co.uk/scripts/latlong.html)
  • Geographic coordinate system (http://en.wikipedia.org/wiki/Geographic_coordinate_system) - Expressing latitude and longitude as linear units
  • Ricky's Bing Map Blog (http://rbrundritt.spaces.live.com/) - Almost everything you would ever need to know about working with Virtual Earth with examples and math.

Why? Because in the technology you are using a map component does not exist, or you are unable to use the existing map component for some reason.

Coordinate Systems There are several coordinate systems involved with using a tile service like Virtual Earth. Virtual Earth and other tile services divide the world in to fixed size tiles at different zoom levels denoted by z, where the number total number of tiles is 22z. The map in this example is at zoom level 3 so there are 64 tiles total, and is derived from the images in Virtual Earth article in the Microsoft Bing Help Docs (http://msdn.microsoft.com/en-us/library/bb259689.aspx).

01_coordinate_system

The world geographic coordinate system (represented in black) is in latitude and longitude and runs from approximately 85 to -85 latitudes and -180 to 180 longitudes. Due to the way the earth in compressed in a tiled map, the lines of latitude are now evenly spaced even through they are the same pixel distance apart. This requires a formula to be used to determining latitude that takes into account this difference.

The tile coordinate system (represented in red) is in row and column, and describes the position of tiles on the world map. All tiles are of a fixed size, though typically at a size of 256 pixels as in the example map, and run from top left to bottom right. Positions in between the upper left corners of tiles are represented using decimal values, so for example (1.5, 0.5) would be in the exact center of tile (1.0, 0.0).

The world pixel coordinate system (represented in blue) is in x and y, and runs from top left to bottom right. It is used to describe the tile coordinate system where tile (0, 0) corresponds to pixel (0, 0). The map size in pixels is ts(2z),where the tile size is denoted as ts and is 256 while z denotes the zoom level and is 3 in the case of the example map.

The screen pixel coordinate system (represented in green) is in x and y, and describes the position of the screen (actually the component displaying the map) in relation to the world map. Because at most zoom levels the world map in pixels is larger than any monitor can display, only the portion of the map which can be seen within the map component is rendered. This means that the size of the component being displayed is dynamic and dependent on the specific application’s usage, as well as how the local x and y relates to the global x and y of the world pixel coordinate system.

General Formulas and Notations

The following is a list of several commonly used formulas and terms.

02_formulas

Latitude and longitude to row by column

This formula is used to turn a latitude and longitude form the world geographic coordinate system into a and row by column value in the tile coordinate system.

03_lat_and_lon

World x and y to latitude and longitude

This formula is used to convert and x and y position in the world pixel coordinate system to a latitude and longitude in the world geographic coordinate system.

04_xy_to_lat_lon

Requesting Tiles

05_requesting_tiles

Tiles are requested based on retrieving them one at a time from a URL. How a URL is generated depends on the particular tile server and in the case of this map component only the Virtual Earth tile servers are used. The URL is used to specify the type of image, its zoom and location, and its file type. All files types in Virtual Earth are of PNG or JPG, and the location must be given using the quad key. The quad key is a compressed representation of the tile location using the row, column, and zoom.

The following shows how to generate a quad key using the row, column, and zoom using a Java-like syntax:

String tileToQuadKey(int r, int c, int z) {

String quadKey = "";

for (int i = z; i > 0; i—) {

char digit = '0'; int mask = 1 << (i - 1);

if ((c & mask) != 0)

digit++;

if ((r & mask) != 0) {

digit++; digit++;

}

quadKey += (digit + "");

}

return quadKey;

}

Tile Request and Display Optimization

Only the tiles which are within view of the screen (component) need to be displayed, which means that those should be the only ones to be requested. Once a tile is displayed in order to cut down on loading and rendering time the map component stores the tile, and when it is no longer in view keeps the tile in memory but removes it from the display. For example if the map is to be centered at the tile location of (3.5, 3.5) and is component displaying the map is only large enough to display half of each surrounding tile, than only 9 tiles need to be requested.

06_tile_request_1

In the event that the screen moves up into the next row of tiles the tiles that are now in view should be requested and displayed, while the three tiles that are no longer displayed should be cached.

07_tile_request_2

In order to know which tiles to display and where a center coordinate must be known. Given that center coordinate and the size of the area that will display the map, the tiles to be displayed and their position within that component can be determined.

Determining the tiles to be displayed in the current screen using a center coordinate

08_tiles_current_screen

Given a coordinate in latitude and longitude to be the center on the map to be displayed, that coordinate can be converted to a tile location in row by column. By using that row and column the range of tiles to be retrieved and displayed can be determined using the amount of space available on the screen and the tile size. The row and column minimums and maximums denote the range of tiles to be displayed, and the delta x and y are used to calculate the pixel distance from the center of the center tile to its upper left corner. This is used to determine how many tiles can fit above, below, to the right of, and to the left of the center tile according to its current position in the center of the screen.

For example if the center coordinate translated to (c, r) = (2.5, 4.5 ) at zoom level 3 and the screen was 512 by 512 pixels, then the column and row minimums and maximums would be calculated as approximately the tiles needed to cover the size of the current screen.

09_tiles_current_screen_example

Positioning tiles relative to center

With the range or rows and columns for all tiles to display, given the row and column of a tile its local position in x,y is calculated in the following way:

10_position_tiles_relative_to_center

The x,y local of the tile of the given row and column is calculated relative to the position of the center image. This is done so that panning movement can be calculated relative to the center position of the screen, in order to calculate a simple offset that can be applied to all tiles in order to handle map panning. For example if the center tile location was (c,r) = (2.5, 4.5) and the screen was 512 by 512 pixels, the position of the tile at (c,r) = (1, 3) relative to the center tile would be at (x,y) = (-256, -256).

11_position_tiles_relative_example

Handling Map Panning

The end result is that the user should be able to click and drag the map in order to move it around (or to pan). This requires keeping track of where the mouse was clicked, where it was dragged to, and when it was released (to stop worrying about where it is being dragged). During a drag the difference between the current mouse location and the location of the original click can be calculated, and then used to determine the new offset to apply to the map along with the new visible rows and columns.

12_map_panning

The variables such as the x,y and r,c min and max values need to be kept track of through the map component life cycle. This is because positioning is done using an offset based on the starting location of the center tile. The offset is calculated using the inverse of the change in mouse position during the click and drag. For example if the user clicks on the map and drags right, more of the map needs to be proportionally drawn to the left. The x and y min and max are used to track the size of the tile area in pixels, in order to determine the how many more tiles are needed at the new map boundaries in terms of rows and columns.

The following shows how the variables in the map panning equation are changed when the screen view (512 by 512 pixels) is moved up on the map by 256 pixels:

13_map_panning_example

Zooming in on a Set of Locations

14_zooming

A function available within most maps is the ability for the map to determine the zoom level to best fit a series of points, and center appropriately. This is generally done by determining the area required in order to display a number of points, and determining the closest matching meters/pixels zoom level and then centering appropriately.

Determining the geographic display area

The geographic display area is determined by taking the minimum and maximum latitudes and longitudes of the list of geographic position, which can be used to construct the geographic positions denoted as A,B, and C. Note that this method for determining geographic bounds will not work across the corners of the map.

15_geo_display_area

Calculating the distance between two geographic points

After determining the geographic display area that is required in terms of the rectangle ABC, the distance from geographic coordinates A to B and B to C needs to be calculated. This requires the ability to calculate the distance between two geographic coordinates, which is described in the following as the function d(A, B):

16_calc_geo_distance

Calculating the Desired Meters per Pixel

With the the ability to calculate the distance between geographic coordinates, the size of the geographic area to be zoomed in on can be calculated by determining the meters per pixel required to cover the area. This formula assumes a fairly square screen, because it takes the largest distance and meters against the smallest pixel length of the required screen area.

17_meters_per_pixel

For example using the distances AB and BC, since AB is the largest it is used to calculate the meters per pixels required to display all of the points within the area of rectangle ABC with center G.

18_meters_per_pixel_example

Finding Zoom Level based on Meters Per Pixel

19_table_meters

(Table from http://msdn.microsoft.com/en-us/library/bb259689.aspx)

Wednesday, March 24, 2010

A Flex Ant Build: Optimized Modules, Libraries, Runtime CSS, HTML Wrapper, Runtime Images

A common need in a system involving Flex is for the ability to build the Flex portion using Ant. While there are some online examples, there is not one that I have been able to find that does and describes all of the things I typically need to do in Flex . The things which I typically need to do are the following:
  • Build optimized modules without having to declare a separate compile target for every module
  • Include one or more SWC libraries
  • Compile the CSS into a SWF to be loaded at runtime
  • Create a custom HTML wrapper, that is also responsible for setting the application endpoint
  • Including images to be loaded at runtime
  • Uses a properties file to define all the elements
This build also assumes the following:
  • There is one source directory called "src"
  • Runtime images are somewhere under the source directory
  • CSS is somewhere under the source directory
  • All modules are in a single directory, that contains nothing but the modules
  • You have the Flex ant task JAR in libs
  • You have the Ant Contrib JAR in libs
  • You have a separate index.template.html for the build that contains ${} variables for the endpoint
For example the following is my example project directory structure:
The build works by executing these targets as part of its default target:
  • clean - deletes the deployment directory
  • compile - compiles the main application into its SWF
  • compile-modules - uses a "for" loop on all the MXML files in the modules directory and calls the "compile-module" target on them
  • compile-module - compiles a module into a SWF file, optimized for the main application
  • compile-css - compiles the CSS into a SWF
  • compile-wrapper - builds the HTML wrapper for the application, and includes the endpoint using FlashVars
  • copy-images - Copies runtime images from source into deployment
  • clean-up - deletes any generated files
Here are the build files:

Tuesday, February 9, 2010

Dear John, what is the easiest way to use Flex modules?

Question asked by Ezra.
When it comes to modules there are two general schools of practice:
  1. Load and cache
  2. Load and unload
Option 1 is by far the most simple, but since content is never unloaded the application has to be small enough to theoretically be loaded in its entirety. I tend to build most Flex applications under this model.
Option 2 is near impossible depending on the specific implementation. There are many areas beyond what I have written about that can prevent a module from from unloading. I have built applications under this model, and getting things to unload correctly is a massive undertaking.
Implementing option 1 can be as simple as putting a view stack in your main application file and using states to add ModuleLoaders to it, and as complicated as writing your own module manager utility to load modules based on some external configuration.
An important concept with modules that you must always consider though is compile by reference. When compiling a Flex application into a SWF file, it is that class which inherits from “mx.core.Application” and the referenced classes within its class hierarchy that are compiled into that SWF file along with other embedded resources. Classes that are not referenced in that class hierarchy are not compiled into the application SWF file. This concept of compilation by reference in a Flex application also applies to a Flex module.
Knowledge of compilation by reference and their effects on modules and applications is important, because if an application has reference to a module class in its class hierarchy that module class is compiled into both the module SWF file and application SWF file. This duplication of module class definitions is undesired behavior, since the main purpose of modules is to have code and resources in a location outside of the application SWF file and not within it. Beware that the several examples I have seen in Adobe documentation and elsewhere show the main application give direct reference to the module class that it is trying to load. This results in that module class being compiled into both the main application SWF and the module SWF, which defeats the purpose of using modules.
Modules are also effected greatly by optimization by eliminating class duplication. For example if your main application, ModuleA, and ModuleB reference FOO, if ModuleA and ModuleB are optimized for that application the class definition for FOO is compiled into the main application SWF file. If those modules were not optimized then the class definition for FOO would be compiled into the main application, ModuleA, and ModuleB SWF files.
All of this means that your modules should be optimized for your specific application, and that your application should not directly reference modules and your modules should not directly reference your application. The following is some pseudo-code that shows how to use states and modules loaders to create a modules application:
This example requires that both a ModuleA.mxml and ModuleB.mxml exist as Flex modules, which results in them getting compiled into their own SWF files. In order to interact with the application I typically create a singleton business object that maintains the current state of the application, shared data, and has the ability to change state.
For example:
[Bindable]
public class AppStateBO {
public static const STATE_A:String = "STATE_A";
public static const STATE_B:String = "STATE_B";
public var currentState:String = "";
//singleton stuff here
}
That why both the main application and each module can have access to the data they need to share and the ability to change the state of the application:
[Bindable]
var appState:AppStateBO = AppStateBO.getInstance();
...
appState.currentState = AppStateBO.STATE_A;
If the currentState attribute of the main application were bound to appState.currentState then any module with the app state singleton could change the state. There are of course many other ways to do this, but at a minimum you need something to be shared across the app and modules.

Dear John, How do I remove Flex bindings on an object?

Question asked by Joshua.
Removing bindings requires a trick with include namespace mx_internal, which will give you access to parts of components that you would normally not have access to.
According to the source code for Binding.as (which I believe is not included in the SDK), the bindings are stored in the following places within objects:
  • mx_internal _bindings:Array
  • mx_internal _watchers:Array
  • mx_internal _bindingsByDefinitions
  • mx_internal _bindingsBeginWithWord
The following function can then be used to clear bindings on an object:

Dear John, How do I unload Flex modules?

Question asked by Joshua.
Unloading modules is a difficult thing to do, and is near to impossible in Flash Player 9. Originally this article clued my into what was going on: http://www.gskinner.com/blog/archives/2008/04/failure_to_unlo.html. Essentially to get modules to truly unload you have to get rid of all the references to them, and be using the "Copied Domain Method." The copied domain method is described here in detail, along with its effects on memory: http://jvalentino.blogspot.com/2009/06/flex-memory-issue-4-modules-and.html.
Assuming you are using the Copied Domain Method, you then have to deal with the following areas of leakage as mentioned in the originating article:
I essentially handled these area of leakages by iterating recursively through every component within a module class after unloading, removing state, removing bindings, removing common listeners, reseting the EffectManager, and then forcing garbage collection using what is called the local connection hack.
The problem with this though is that there will always be memory accumulation even if references are removed. This is due to a largely unknown and undocumented issue known as "Rendering memory fragmentation." I have discussed this issue with several engineers at Adobe through a client which I cannot name, and they are at least passively aware of it but it is an issue with the Flash Player itself. The article at http://www.craftymind.com/2008/04/09/kick-starting-the-garbage-collector-in-actionscript-3-with-air/ hinted at what was going on, which lead me into a full investigation to verify the problem.
Basically the Flash Player operates on what is called an Elastic Racetrack (http://www.onflex.org/ted/2005/07/flash-player-mental-model-elastic.php), which ends up with the memory used of AS3 object allocation and the memory used for rendering getting on the same page in memory. When the garbage collection runs the allocation space is not cleaned because the blocks contain active rendering memory and vice versa. This makes it to where the garbage collector fails to clean things, which causes leaks. Since the issue is rendering related it is more prevalent in application that are graphically intense and run at large resolutions, like kiosks. It is for these reasons that I recommend that most applications pool modules, so that the rendering and object instantiations through allocations are minimal.
In the end it will depend on how many "modules" are in your application, how big they are, and if they are really modules. It is quite common for application to incorrectly use modules because they followed the examples released by Adobe, which cause the module definitions themselves to be compiled into both the module SWF and the main application SWF. Flex operates on a compile by reference basis, so if your application has direct reference to a module class that module class gets compiled into both the module SWF and the main application SWF.