Weekly update

This past week focused on development of a basic data input page. I decided to use form variables (at least to start with) as the way to pass information between pages. I had to learn how to write the html to allow that plus some php to parse the passed information. I also had to figure out how to pass the variables between php and javascript to get the input data and viewer scripts I'd written to get along. Anyways, as a result I have a rudimentary input page tied to my viewer now. I, of course, still need to clean it up, add error handling, different input types, etc. But it's a start!

On the administrative side of things, I added my project blog to the Planet SoC site. Basically it's a neat aggregation of a bunch of blogs concerning many different Google Summer of Code projects. I also updated the wiki with my design doc.

To do for this week:
Get basic output page written and in synchrony with the other pages.
If time, add some functionality to the viewer (like changing colors).

Skeleton of data input working

I got a skeleton of the data input working this week. Basically, the input text field is just a large textarea form field. Then I use a php script to parse out the variables, then use the javascript code I used before to generate the map pies. Data input could certainly be cleaned up, but this was just so I could learn one way of passing data from page to page (through form variables).

Able to generate many pies

I got the script working to generate and manage many pies at once. The script generates 10 pies placed randomly on the map with random haplotype distributions with random (but consistent!) colors. The pies are draggable and zoomable, and the DOM node structure remains consistent with zooming.

updated project wiki to include design doc

Finally got around to putting the design doc up on the wiki. I didn't get a chance to incorporate the haplotype grouping feature into the design, but I image it would mean added a table of haplotyes x group identifier on the manual data input and the data management pages. Also, I'd like to incorporate Norm's suggestions of a grayscale feature and export as .ai feature eventually too.

More features to add

I was showing off the pie viewer prototype to Norm, and he had some great suggestions for features.

A black/white/grayscale option. Many journals prefer black and white figures, so it'd be great to be able to color pies with grayscale and maybe patterns.

Be able to save as an Illustrator or other vector based document. I'm creating all these svg's, so allowing output to be read by an svg master manipulator seems smart.

Weekly update

This past week I:

• Met with David and got feedback on my design document.
• Wrote a map preview app that uses javascript and generates a random pie on a google map that is draggable and zoomable.

Next week's goals:

• Update design document; post it to the wiki.
• Decide on how to pass information from page to page (through form variables, writing/reading a data file, a database server like MySQL).
• Design a data structure to be used.
• Write a simple input page that allows uploading of a data file.
• Link input page to preview page (the pie viewer that was written last week).

getting the preview pane working

I spent most of this week trying to get the basic functionality of the preview pane working. The goals were to draw a map with randomly generated pie charts and colors where the pies were draggable and zoomed appropriately. I succeeded in generating this zoomable and draggable pie chart. Try it out. The page generates a pie with random slices and colors. Try dragging the pie, zooming to new levels, and try dragging again.

These are the steps that I took to build that code:

1. Draw a circle on a map.
2. Draw multiple circles on a map.
3. Make the circles draggable.
4. Draw a pie on a map.
5. Make the pie draggable.
6. Make the pie zoomable.
7. Make the pie zoomable and draggable.

I ran into various bugs along the way that made this problem really challenging. Here are some of the implementation details:

• Drawing the circles in Google Maps (GM) is actually easier than in Google Earth because you can easily calculate the pixel coordinates of the 90 vertices that comprise the circle. GM provides functions like fromDivPixelToLatLng() and fromLatLngToDivPixel() that then make switching back and forth to latlong coordinates easier, and you don't have to do all the complicated haversine computations yourself.
• Making the circles draggable was a little difficult because you have to wrap the created circle svg's within appropriate HTML div elements. This turned out to be somewhat complicated because it involved manipulating the DOM node tree that simultaneously updated our array of svg elements.
• Drawing the pies instead of circles added another layer of complexity because not only does each svg of a pie slice need to be wrapped in its own div but then all the slices of the same pie need to be wrapped together in another div that was made draggable.
  
• One bug I ran into was how to get the pie pieces to fit together seamlessly. The random numbers generated for the dimensions of each slice didn't correspond exactly with the 90 evenly spaced vertices (one vertex every 5 degrees), but some simple rounding and modulo type operations fixed that. That means that the pies are not exact representations of the input data, they may be off 5 degrees or so for each slice, but I'm guessing most humans won't be able to notice that.
• So making the new pie divs draggable wasn't a problem, but making it work with the zoom function was a bear. After zooming, the pie would either become undraggable, we'd see too many copies of the pie, and/or not all of the copies would be the same or in the correct places. There were several issues to overcome. First, I had to wipe and redraw the overlays containing the pies. Second, I had to repackage the functions so that I could save and access the random data that had been generated (i.e. the slice angle data, slice colors). Third, I had to update the location information of the pie after it was dragged. The first two tasks were not bad, but the last bug took the longest to fix.
  
• At first, I tried to get the new location info from calculating the center point of the encapsulating div. Several problems with that approach: I could get the info for the left top corner of the div, but the height and width were zero, and the div's size was not only just large enough to fit the pie (the width of the div was not equal to the diameter of the circle) as I had assumed, and finally I realized that what was returned by style.left and style.top was NOT the coordinates of the top left corner but rather the offset of the coordinates in pixels.
  
• I could use the offset in pixels to calculate the new lat and long for the center of the pie. However, to convert from pixels to latlng units I needed to use a different function that incorporated zoom level information (different zooms will have different latlng to pixel relationships). This involves declaring a GProjection variable to get the fromLatLngToPixel(latlng, zoomLevel) function. Whew! But finally, we have pies we can move and zoom.

Links to useful documentation for working with javascript and Google Maps

Prototype is an excellent javascript library that basically implements all those functions that you wish came standard but didn't. Yay! Thanks to Cyrus and Jack who pointed this out to me. The documentation is pretty good too.

Javascript documentation. Fairly helpful, but not very complete. I ended up buying O'Reilly's javascript book this weekend to supplement this. The book's proven to be extremely helpful so far.

HTML DOM reference. Helpful, but doesn't have an 'DOM Element' section, which is annoying. The O'Reilly book does though, which once again is great.

HTML DOM Element reference. On Mozilla's development site. Has links to other references on javascript that might be worth checking out.

General HTML Tag reference.

Google Maps API reference. It has all the functions, but it's a bit difficult to parse. It can be difficult to find what a function belongs to -- the headings need to be set apart more. Also, some example syntax would be helpful. All in all, it's a necessary resource, but difficult to understand.

GPolygon class examples. On the Google Maps API forum. Many helpful links that showed how they implemented circles, making them draggable, resizable, etc. Very useful reference.

Firebug debugger. I've been using this debugger for inside website stuff. It's generally awesome. You can view the DOM hierarchy, set break points, and generally debug your code with it. Only complaints so far are that the debugging functionality appears to be a line off for some reason and sometimes the program fails to recognize the breakpoints you set (just blows right through them).

Meeting with David -- design doc changes

Met with David this week to go over my design document. Generally the comments were good, and we mostly talked about adding some features and how to pass data from page to page. Here are some notes and thoughts from the meeting:

Features to add:

• I should add a feature on the 'manage data' page to group haplotypes together.
• On the preview page there should be an expand option to make the preview map pane larger.
• Instead of having a special .pgv format for my application, can we fit everything within a .kml that our viewer can read as well?

Passing data:

• The next big design decision is how to pass the data from page to page. We have several options:
• All through form variables?
• By using a database server?
• By writing and accessing our own output files?
• What kind of data structure should be used to hold the data?

We also talked about what languages to implement all this in. I had been planning on using php for all the server talking stuff and javascript for within the webpage stuff, but David made the point that using two languages is probably totally unnecessary, can javascript be enough? I think that sounds great to just learn one. The only problem I see is that it may be difficult (or impossible) to do server interactive stuff using javascript. I'll have to investigate this more.

From this meeting, it became clear what my next step should be: to build a skeleton application. The goals are to

1. be able to display pies on a map
2. to link (and be able to pass data) from the input page to the display page.

David also encouraged me to use the programming resources at NESCent (namely Xianhua), so maybe next week after I've gotten my feet wet with javascript, we can meet up with Xianhua and ask some more detailed implementation questions.

Apologies -- a little behind on blogging

Sorry, got a bit behind on blogging. The next few posts concern my progress this past week.

Weekly update

This past week I put together a draft of my design document. I tried to be as comprehensive as possible and made some mock ups for each page the user will encounter. Any comments on it are appreciated!

After doing all this design work I realize that I need to learn a lot more javascript than I had expected. While I'll still be exporting KML to Google Earth, I'll be previewing the visualizations a lot more in Google Maps which uses javascript. This puts me a little behind, because I'll have to get caught up on javascript this week too.

To do this week:

• Meet with David and get feedback on design doc.
• Make changes to design doc; post on wiki.
• Familiarize self with javascript fundamentals
• Implement the basic pie chart generation functionality. Functionality should include:
• Draw a pie on a google map.
• Plots multiple objects (working up to pie charts, but starting with placemarks) on a map.
• Basic import of data.
• Basic export to kml.

Detailed design document, draft 1

If the user selects 'input manually',


The default numbers of haplotypes and populations are set to 10. Users can update these values to get the appropriate number of rows and columns in the data matrix. Unless the data matrix is small, the user will likely have to scroll within the table to input all the data. To facilitate this the population, lat, and long columns and the header row will be frozen. After the data is saved, the application checks the input. If the data is validated, we go to


We arrive at this page once the data have been validated (whether input by hand or uploaded). The purpose of this page is to allow the user to include/exclude populations and/or haplotypes. By default all populations and haplotypes are included. After any edits the user is taken to


This window previews and allows the user to edit the visualization. There are 3 possible visualizations: 1) Show just the sampling localities. On this option, the map options 'haplotype color', 'pie size (absolute)', and 'pie size (relative)' are grayed out. 2) Display with circles relative to the sample size for each locality. In this case, the map option 'marker appearance' is grayed out. 3) Display full haplotype information for each locality. In this case, the map option 'marker appearance' is grayed out.

When editing any of the map options a panel will pop out with options for that task. Map option definitions:

• marker appearance: select what icons you want to identify each population
• haplotype color: select colors for each haplotype
• pie size (absolute): set the max diameter for each circle or pie
• pie size (relative): choose if pies are all the same size or relative to the sample size; allows the user to set the bounds on the sample size bins

The map itself is fully functional. Users can zoom in, pan, and access satellite imagery as they can in other google maps applications. Furthermore, the users can click on drag any of the markers, circles, or pies to reposition them. This should be very useful especially for avoiding overlapping pies. If there's time, I'd like to add a button here for 'auto-fix overlapping pies', where the application detects collisions and repositions the pies for the user.

Below the preview screen is the legend. It shows the current color of each haplotype as well as the relative circle sizes and their corresponding sample sizes.

I know on the mock-up the preview screen is fairly small. However, the page will scale with the window, so it should be big enough for most folks. I will also consider moving the 'map options' below the map, so the map can be bigger. I was thinking, though, that the user might find it annoying to constantly scroll up and down to see the effects of the 'map options'.

Now to export the finalized map and legend.


From this page the user can export the visualization in four ways. It's important for the user to do the repositioning, coloring, and other editing work here before exporting to Google Earth. It's not possible to click and drag polygons in Google Earth as it is in Google Maps. If the user selects the .jpg option, they will be prompted to choose either saving the map and legend together or separately. The other formats handle the map and legend separately anyways.

Error handling: If the application has trouble reading the input file, then the validation will fail and generate this error page.

The user is then directed back to either uploading or manually inputting their data.

Overall flow chart for the application

In words:
The user starts by inputting their data. There are three options for data input. After the data has been input, we validate that the data is appropriate and interpretable. If not, we send an error message to the user, and ask them to resubmit their data. If the data input is successful, we display the data back to the user and allow the user to include/exclude any populations and/or haplotypes. Following data management, the user is taken to the preview visualization page. Here a google map is displayed showing a visualization of the data. There are various map and view options here that update the page. The user can also return to the data management screen and edit previous choices. Finally, the visualization can be exported in four formats.

Weekly update

This past week I...

• Explored Google Earth and its APIs.
• Figured out an algorithm for calculating vertices for drawing "circles" on a map.
• Figured out how to write a pie chart in KML.
• Explored Google Maps APIs.
• Learned some javascript.
• Learned how to embed Google Maps in a web page.
• Have a better idea of what the overall design of the program will be like.

Next week the focus is on fleshing out the application's design. I will...

• Produce a page by page description of what the user sees.
• To do so I will consider:
• How to input data. Are they going to upload files, input in a text box? What format?
• How to export data. Format? Data persistence? Can users store data, results, maps, etc.?
• What is the viewer? Google earth? Google maps?
• How large are the pie charts going to be in comparison with the geography?
  
• How do we deal with the problem of overlapping pie charts?
• How are we going to color the pie charts? What if there are large numbers of haplotypes, how do we color them all distinctly and usefully?
• The results of these decisions will be a comprehensive design document posted on the wiki.

Some notes on Javascript

To use the Google Maps API's I'll need to know javascript. Here are some things I learned today:

Javascript has funny objects. Even functions are objects. And there's a lot inheritance going on.

For instance, if you want to create a new function that is a subtype of some class; you must implement all the appropriate "Abstract Methods" of that class.

Javascript ties everything to your html document through the DOM and DOM events. Examples of DOM elements are <div>, <body>, etc. DOM events are events that are generated by certain actions in the document like loading, clicking, moving, dragging, etc. Easiest way to think of GM is that each map instance is tied to a specific <div> or other element in your DOM. Event handlers are functions that get called when a certain event occurs and then does something.

Some useful websites:
Google Maps API
HTML tag list
Javascript DOM reference

Playing with Google Maps

Yay! After playing around with Google Maps I feel fairly confident that we'll be able to at least preview the maps in GM and allow the user to manipulate the document in various ways.

For instance, I was able to create a rectangle overlay that was then draggable. You can imagine users dragging the pie charts around to avoid collisions and so forth. Pretty neat functionality!

image overlays vs. polygons idea revisited

I played around with the idea of using image overlays to create the pies vs. using polygons.

Overlays
Pros: In GE you can easily grab and move, resize, or rotate the image. This way, the user wouldn't totally be reliant on our application to manipulate the pie charts.
Cons: The images could get ugly if increased in size by too much. Also, we'd lose the ability to turn different aspects of the pies on and off (like the labels, particular haplotypes, etc.). And we wouldn't be able to change the colors of the different pie pieces without returning to the application.

Polygons
Pros: There's a lot of information retained in the file hierarchy. The user can turn various components on and off and recolor them easily. Plus, the image is likely to be crisper.
Cons: The user cannot move or resize the pies without going back to our application.

I think that having the ability to access the components of the pies (haplotypes, labels) easily outweighs the hassle of resizing and moving. To get around the hassle, our program will have to have some sort of collision detection mechanism, and some easy way to resize pies. Can we preview the map on google maps before exporting to GE? and allow the users to change things there? That may be the best work around. So I'll continue down the polygon path and leave behind image overlays.

Another thought on overlays: It would be nice to have a species distribution overlay function, where the user uploads an image file with the species distribution and can stretch it to fit the map. Also, I wonder if someone's already made overlays or paths of things of common interest, like where the ice margin was at the LGM, or if there's a repository of species distribution data.

my first pie!

I got my first pie working! It looks good. Not oblong anymore. And I figure using 360 vertices should make generating pie pieces of any size easier. I don't think it adds that much bulk to the code either, but if it's a problem we can always go down to 20 or so points.

I placed the label and pie pieces in different folders so you can click off the labels easier. Here's the KML.

Lat and Long in KML

While you can enter coordinates in "lat, long" pairs in the finder, in KML, within the tag, the order is "longitude, latitude, altitude".

finally have formula that's working to calculate locations of vertices

So, after poring over ink_polaroid's solution for what seems like forever, I finally figured out what I was doing wrong! Just a note: PHP and Excel's arguments for the atan2 function are reversed. What a headache for something so simple.

Here's the algorithm for calculating the latitude, phi2, and longitude, lambda2, of a point distance, d (in meters), away from a point with latitude, phi1, longitude, lambda1, and angle, theta (from vertical, parallel to longitude lines).

d_rad = d/6378137 (6378137 m is radius of Earth at the equator)
phi2 (in radians) = asin(sin(phi1)*cos(d_rad) + cos(phi1)*sin(d_rad)*cos(theta))
dlon = atan2(sin(theta)*sin(d_rad)*cos(phi1), cos(d_rad) - sin(phi1)*sin(phi2))
lambda2 (in radians) = Modulus(lambda1+dlon+PI, 2PI) - PI

Remember to change everything back into degrees for GE.

how about overlays instead of polygons?

Just another possibility -- how about using pie charts as overlays instead of polygons? Just another thing to explore this weekend...

oblong circles

I tried a bunch of tweaks to the formula that calculates the positions of the 20 vertices comprising the circle. Unfortunately, all of them are off enough that the circle is still oblong, and it seriously morphs depending on where on the globe the central point is. The formula that I ended up working was:

Length of a degree of longitude = cos (latitude) * 111.325 kilometers

from this source.

So my conclusion is that this formula must not be accurate enough. I spent most of the rest of the day yesterday searching various google earth forums, and happened on this post. It seems to calculate the vertices using the haversine formula and great circle distances. I think this is the next method to explore.