Added to test polygon point reduction algorithm and others.

Prepare for rectangle clipping.
Add Douglas-Peucker point simplification algorithm. Add point distance from
    line function. Add in/out/partial rect overlap function.

11 files changed, 555 insertions, 50 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index aa9c0a9..2056ead 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -21,10 +21,12 @@ roadster_SOURCES = \
 	main.c\
 	db.c\
 	downloadmanager.c\
+	directionswindow.c\
 	gui.c\
 	mainwindow.c\
 	gotowindow.c\
 	map.c\
+	mapinfowindow.c\
 	map_draw_cairo.c\
 	map_draw_gdk.c\
 	map_history.c\
@@ -50,7 +52,8 @@ roadster_SOURCES = \
 	road.c\
 	animator.c\
 	gfreelist.c\
-	tooltipwindow.c
+	tooltipwindow.c\
+	test_poly.c
 
 roadster_LDADD = \
 	$(GNOME_LIBS) \
diff --git a/src/gui.c b/src/gui.c
index ec56cb1..4c5910e 100644
--- a/src/gui.c
+++ b/src/gui.c
@@ -35,14 +35,21 @@
 #include "gotowindow.h"
 #include "importwindow.h"
 #include "searchwindow.h"
+#include "mapinfowindow.h"
 #include "locationeditwindow.h"
 
+#ifdef ENABLE_TEST_MODULES
+#include "test_poly.h"
+#endif
+
 void gui_init(void)
 {
 	GladeXML* pGladeXML = gui_load_xml(GLADE_FILE_NAME, NULL);
 	glade_xml_signal_autoconnect(pGladeXML);
 
 	// init all windows/dialogs
+	g_print("- initializing mapinfowindow\n");
+	mapinfowindow_init(pGladeXML);
 	g_print("- initializing mainwindow\n");
 	mainwindow_init(pGladeXML);
 	g_print("- initializing searchwindow\n");
@@ -51,6 +58,12 @@ void gui_init(void)
 	gotowindow_init(pGladeXML);
 	g_print("- initializing importwindow\n");
 	importwindow_init(pGladeXML);
+
+#ifdef ENABLE_TEST_MODULES
+	g_print("- initializing test_poly\n");
+	test_poly_init(pGladeXML);
+#endif
+
 	//datasetwindow_init(pGladeXML);
 	g_print("- initializing locationeditwindow\n");
 	locationeditwindow_init(pGladeXML);
diff --git a/src/main.h b/src/main.h
index bf7e5e7..8919d96 100644
--- a/src/main.h
+++ b/src/main.h
@@ -26,6 +26,8 @@
 
 //#define G_DISABLE_ASSERT
 
+#define ENABLE_TEST_MODULES
+
 #include <gtk/gtk.h>
 
 #define USE_GNOME_VFS		// comment this out to get a faster single-threaded compile (can't import, though)
diff --git a/src/mainwindow.c b/src/mainwindow.c
index 68ddd51..8dc24a2 100644
--- a/src/mainwindow.c
+++ b/src/mainwindow.c
@@ -48,6 +48,7 @@
 #include "glyph.h"
 #include "animator.h"
 #include "map_history.h"
+#include "mapinfowindow.h"
 
 #include "tooltipwindow.h"
 
@@ -447,7 +448,7 @@ void mainwindow_init(GladeXML* pGladeXML)
 	g_signal_connect(G_OBJECT(g_MainWindow.pWindow), "window_state_event", G_CALLBACK(mainwindow_on_window_state_change), NULL);
 	g_signal_connect(G_OBJECT(g_MainWindow.pWindow), "key_press_event", G_CALLBACK(mainwindow_on_key_press), NULL);
 	g_signal_connect(G_OBJECT(g_MainWindow.pWindow), "key_release_event", G_CALLBACK(mainwindow_on_key_release), NULL);
-	
+
 	// Drawing area
 	g_MainWindow.pDrawingArea = GTK_DRAWING_AREA(gtk_drawing_area_new());	
 
@@ -494,6 +495,8 @@ void mainwindow_init(GladeXML* pGladeXML)
 	// XXX: move map to starting location... for now it's (0,0)
 	mainwindow_add_history();
 	mainwindow_update_zoom_buttons();	// make sure buttons are grayed out
+
+	mapinfowindow_update(g_MainWindow.pMap);
 }
 
 gboolean mainwindow_locationset_list_is_separator_callback(GtkTreeModel *_unused, GtkTreeIter *pIter, gpointer __unused)
diff --git a/src/map.c b/src/map.c
index 97e7ccf..a5a3f5a 100644
--- a/src/map.c
+++ b/src/map.c
@@ -158,7 +158,7 @@ gchar* g_apszMapRenderTypeNames[] = {"lines", "polygons", "line-labels", "polygo
 // init the module
 void map_init(void)
 {
-	g_print("*********************************** %f\n", WORLD_FEET_PER_DEGREE);
+	//g_print("*********************************** %f\n", WORLD_FEET_PER_DEGREE);
 }
 
 gboolean map_new(map_t** ppMap, GtkWidget* pTargetWidget)
diff --git a/src/map_draw_gdk.c b/src/map_draw_gdk.c
index 4a538e8..c972531 100644
--- a/src/map_draw_gdk.c
+++ b/src/map_draw_gdk.c
@@ -38,6 +38,7 @@
 #include "db.h"
 #include "road.h"
 #include "map_style.h"
+#include "map_math.h"
 #include "locationset.h"
 #include "location.h"
 #include "scenemanager.h"
@@ -51,6 +52,13 @@ static void map_draw_gdk_layer_fill(map_t* pMap, GdkPixmap* pPixmap, rendermetri
 static void map_draw_gdk_locations(map_t* pMap, GdkPixmap* pPixmap, rendermetrics_t* pRenderMetrics);
 static void map_draw_gdk_locationset(map_t* pMap, GdkPixmap* pPixmap, rendermetrics_t* pRenderMetrics, locationset_t* pLocationSet, GPtrArray* pLocationsArray);
 
+typedef struct {
+	GdkPixmap* pPixmap;
+	GdkGC* pGC;
+	maplayerstyle_t* pLayerStyle;
+	rendermetrics_t* pRenderMetrics;
+} gdk_draw_context_t;
+
 //static void map_draw_gdk_tracks(map_t* pMap, GdkPixmap* pPixmap, rendermetrics_t* pRenderMetrics);
 
 void map_draw_gdk_set_color(GdkGC* pGC, color_t* pColor)
@@ -147,6 +155,53 @@ void map_draw_gdk(map_t* pMap, GPtrArray* pTiles, rendermetrics_t* pRenderMetric
 	TIMER_END(maptimer, "END RENDER MAP (gdk)");
 }
 
+// useful for filling the screen with a color.  not much else.
+static void map_draw_gdk_layer_fill(map_t* pMap, GdkPixmap* pPixmap, rendermetrics_t* pRenderMetrics, maplayerstyle_t* pLayerStyle)
+{
+	GdkGC* pGC = pMap->pTargetWidget->style->fg_gc[GTK_WIDGET_STATE(pMap->pTargetWidget)];
+
+	GdkGCValues gcValues;
+	if(pLayerStyle->pGlyphFill != NULL) {
+		// Instead of filling with a color, fill with a tiled image
+		gdk_gc_get_values(pGC, &gcValues);
+		gdk_gc_set_fill(pGC, GDK_TILED);
+		gdk_gc_set_tile(pGC, glyph_get_pixmap(pLayerStyle->pGlyphFill, pMap->pTargetWidget));
+		
+		// This makes the fill image scroll with the map, instead of staying still
+		gdk_gc_set_ts_origin(pGC, SCALE_X(pRenderMetrics, pRenderMetrics->fScreenLongitude), SCALE_Y(pRenderMetrics, pRenderMetrics->fScreenLatitude));
+	}
+	else {
+		// Simple color fill
+		map_draw_gdk_set_color(pGC, &(pLayerStyle->clrPrimary));
+	}
+
+	gdk_draw_rectangle(pPixmap, pMap->pTargetWidget->style->fg_gc[GTK_WIDGET_STATE(pMap->pTargetWidget)],
+			TRUE, 0,0, pMap->MapDimensions.uWidth, pMap->MapDimensions.uHeight);
+
+	if(pLayerStyle->pGlyphFill != NULL) {
+		// Restore fill style
+		gdk_gc_set_values(pGC, &gcValues, GDK_GC_FILL);
+	}
+}
+
+// 
+static void map_draw_gdk_polygons(const GArray* pMapPointsArray, const gdk_draw_context_t* pContext)
+{
+	// Copy all points into this array.  Yuuup this is slow. :)
+	GdkPoint aPoints[MAX_GDK_LINE_SEGMENTS];
+	mappoint_t* pPoint;
+
+	gint iPoint;
+	for(iPoint=0 ; iPoint<pMapPointsArray->len ; iPoint++) {
+		pPoint = &g_array_index(pMapPointsArray, mappoint_t, iPoint);
+
+		aPoints[iPoint].x = pContext->pLayerStyle->nPixelOffsetX + (gint)SCALE_X(pContext->pRenderMetrics, pPoint->fLongitude);
+		aPoints[iPoint].y = pContext->pLayerStyle->nPixelOffsetY + (gint)SCALE_Y(pContext->pRenderMetrics, pPoint->fLatitude);
+	}
+
+	gdk_draw_polygon(pContext->pPixmap, pContext->pGC, TRUE, aPoints, pMapPointsArray->len);
+}
+
 static void map_draw_gdk_layer_polygons(map_t* pMap, GdkPixmap* pPixmap, rendermetrics_t* pRenderMetrics, GPtrArray* pRoadsArray, maplayerstyle_t* pLayerStyle)
 {
 	mappoint_t* pPoint;
@@ -174,13 +229,21 @@ static void map_draw_gdk_layer_polygons(map_t* pMap, GdkPixmap* pPixmap, renderm
 		map_draw_gdk_set_color(pGC, &(pLayerStyle->clrPrimary));
 	}
 
+	gdk_draw_context_t context;
+	context.pPixmap = pPixmap;
+	context.pGC = pGC;
+	context.pLayerStyle = pLayerStyle;
+	context.pRenderMetrics = pRenderMetrics;
+
 	for(iString=0 ; iString<pRoadsArray->len ; iString++) {
 		pRoad = g_ptr_array_index(pRoadsArray, iString);
 
-		if(!map_rects_overlap(&(pRoad->rWorldBoundingBox), &(pRenderMetrics->rWorldBoundingBox))) {
+		EOverlapType eOverlapType = map_rect_a_overlap_type_with_rect_b(&(pRoad->rWorldBoundingBox), &(pRenderMetrics->rWorldBoundingBox));
+		if(eOverlapType == OVERLAP_NONE) {
 			continue;
 		}
 
+		// XXX: should we remove this?
 		if(pRoad->pMapPointsArray->len < 3) {
 			//g_warning("not drawing polygon with < 3 points\n");
 			continue;
@@ -191,17 +254,15 @@ static void map_draw_gdk_layer_polygons(map_t* pMap, GdkPixmap* pPixmap, renderm
 			continue;
 		}
 
-		GdkPoint aPoints[MAX_GDK_LINE_SEGMENTS];
-
-		for(iPoint=0 ; iPoint<pRoad->pMapPointsArray->len ; iPoint++) {
-			pPoint = &g_array_index(pRoad->pMapPointsArray, mappoint_t, iPoint);
-
-			aPoints[iPoint].x = pLayerStyle->nPixelOffsetX + (gint)SCALE_X(pRenderMetrics, pPoint->fLongitude);
-			aPoints[iPoint].y = pLayerStyle->nPixelOffsetY + (gint)SCALE_Y(pRenderMetrics, pPoint->fLatitude);
+		if(eOverlapType == OVERLAP_PARTIAL) {
+			// draw clipped
+			// XXX: Currently no clipping, just draw normally
+			map_draw_gdk_polygons(pRoad->pMapPointsArray, &context);
+		}
+		else {
+			// draw normally
+			map_draw_gdk_polygons(pRoad->pMapPointsArray, &context);
 		}
-
-		gdk_draw_polygon(pPixmap, pMap->pTargetWidget->style->fg_gc[GTK_WIDGET_STATE(pMap->pTargetWidget)],
-			TRUE, aPoints, pRoad->pMapPointsArray->len);
 	}
 	if(pLayerStyle->pGlyphFill != NULL) {
 		// Restore fill style
@@ -209,45 +270,34 @@ static void map_draw_gdk_layer_polygons(map_t* pMap, GdkPixmap* pPixmap, renderm
 	}
 }
 
-// useful for filling the screen with a color.  not much else.
-static void map_draw_gdk_layer_fill(map_t* pMap, GdkPixmap* pPixmap, rendermetrics_t* pRenderMetrics, maplayerstyle_t* pLayerStyle)
+static void map_draw_gdk_lines(const GArray* pMapPointsArray, const gdk_draw_context_t* pContext)
 {
-	GdkGC* pGC = pMap->pTargetWidget->style->fg_gc[GTK_WIDGET_STATE(pMap->pTargetWidget)];
-
-	GdkGCValues gcValues;
-	if(pLayerStyle->pGlyphFill != NULL) {
-		// Instead of filling with a color, fill with a tiled image
-		gdk_gc_get_values(pGC, &gcValues);
-		gdk_gc_set_fill(pGC, GDK_TILED);
-		gdk_gc_set_tile(pGC, glyph_get_pixmap(pLayerStyle->pGlyphFill, pMap->pTargetWidget));
-		
-		// This makes the fill image scroll with the map, instead of staying still
-		gdk_gc_set_ts_origin(pGC, SCALE_X(pRenderMetrics, pRenderMetrics->fScreenLongitude), SCALE_Y(pRenderMetrics, pRenderMetrics->fScreenLatitude));
-	}
-	else {
-		// Simple color fill
-		map_draw_gdk_set_color(pGC, &(pLayerStyle->clrPrimary));
-	}
+	// Copy all points into this array.  Yuuup this is slow. :)
+	GdkPoint aPoints[MAX_GDK_LINE_SEGMENTS];
+	mappoint_t* pPoint;
 
-	gdk_draw_rectangle(pPixmap, pMap->pTargetWidget->style->fg_gc[GTK_WIDGET_STATE(pMap->pTargetWidget)],
-			TRUE, 0,0, pMap->MapDimensions.uWidth, pMap->MapDimensions.uHeight);
+	gint iPoint;
+	for(iPoint=0 ; iPoint<pMapPointsArray->len ; iPoint++) {
+		pPoint = &g_array_index(pMapPointsArray, mappoint_t, iPoint);
 
-	if(pLayerStyle->pGlyphFill != NULL) {
-		// Restore fill style
-		gdk_gc_set_values(pGC, &gcValues, GDK_GC_FILL);
+		aPoints[iPoint].x = pContext->pLayerStyle->nPixelOffsetX + (gint)SCALE_X(pContext->pRenderMetrics, pPoint->fLongitude);
+		aPoints[iPoint].y = pContext->pLayerStyle->nPixelOffsetY + (gint)SCALE_Y(pContext->pRenderMetrics, pPoint->fLatitude);
 	}
+	
+	gdk_draw_lines(pContext->pPixmap, pContext->pGC, aPoints, pMapPointsArray->len);
 }
 
 static void map_draw_gdk_layer_lines(map_t* pMap, GdkPixmap* pPixmap, rendermetrics_t* pRenderMetrics, GPtrArray* pRoadsArray, maplayerstyle_t* pLayerStyle)
 {
 	road_t* pRoad;
-	mappoint_t* pPoint;
 	gint iString;
 	gint iPoint;
 
 	if(pLayerStyle->fLineWidth <= 0.0) return;			// Don't draw invisible lines
 	if(pLayerStyle->clrPrimary.fAlpha == 0.0) return;	// invisible?  (not that we respect it in gdk drawing anyway)
 
+	GdkGC* pGC = pMap->pTargetWidget->style->fg_gc[GTK_WIDGET_STATE(pMap->pTargetWidget)];
+
 	// Translate generic cap style into GDK constant
 	gint nCapStyle;
 	if(pLayerStyle->nCapStyle == MAP_CAP_STYLE_ROUND) {
@@ -278,10 +328,17 @@ static void map_draw_gdk_layer_lines(map_t* pMap, GdkPixmap* pPixmap, rendermetr
 
 	map_draw_gdk_set_color(pMap->pTargetWidget->style->fg_gc[GTK_WIDGET_STATE(pMap->pTargetWidget)], &(pLayerStyle->clrPrimary));
 
+	gdk_draw_context_t context;
+	context.pPixmap = pPixmap;
+	context.pGC = pGC;
+	context.pLayerStyle = pLayerStyle;
+	context.pRenderMetrics = pRenderMetrics;
+
 	for(iString=0 ; iString<pRoadsArray->len ; iString++) {
 		pRoad = g_ptr_array_index(pRoadsArray, iString);
 
-		if(!map_rects_overlap(&(pRoad->rWorldBoundingBox), &(pRenderMetrics->rWorldBoundingBox))) {
+		EOverlapType eOverlapType = map_rect_a_overlap_type_with_rect_b(&(pRoad->rWorldBoundingBox), &(pRenderMetrics->rWorldBoundingBox));
+		if(eOverlapType == OVERLAP_NONE) {
 			continue;
 		}
 
@@ -295,17 +352,14 @@ static void map_draw_gdk_layer_lines(map_t* pMap, GdkPixmap* pPixmap, rendermetr
 			continue;
 		}
 
-		// Copy all points into this array.  Yuuup this is slow. :)
-		GdkPoint aPoints[MAX_GDK_LINE_SEGMENTS];
-
-		for(iPoint=0 ; iPoint<pRoad->pMapPointsArray->len ; iPoint++) {
-			pPoint = &g_array_index(pRoad->pMapPointsArray, mappoint_t, iPoint);
-
-			aPoints[iPoint].x = pLayerStyle->nPixelOffsetX + (gint)SCALE_X(pRenderMetrics, pPoint->fLongitude);
-			aPoints[iPoint].y = pLayerStyle->nPixelOffsetY + (gint)SCALE_Y(pRenderMetrics, pPoint->fLatitude);
+		if(eOverlapType == OVERLAP_PARTIAL) {
+			// draw clipped
+			map_draw_gdk_lines(pRoad->pMapPointsArray, &context);
+		}
+		else {
+			// draw directly
+			map_draw_gdk_lines(pRoad->pMapPointsArray, &context);
 		}
-
-		gdk_draw_lines(pPixmap, pMap->pTargetWidget->style->fg_gc[GTK_WIDGET_STATE(pMap->pTargetWidget)], aPoints, pRoad->pMapPointsArray->len);
 	}
 }
 
diff --git a/src/map_hittest.c b/src/map_hittest.c
index 6b7ac6d..9ab938d 100644
--- a/src/map_hittest.c
+++ b/src/map_hittest.c
@@ -333,7 +333,7 @@ static gboolean map_hittest_locationselections(map_t* pMap, rendermetrics_t* pRe
 	return FALSE;
 }
 
-// Does the given point come close enough to the line segment to be considered a hit?
+
 static gboolean map_hittest_line(mappoint_t* pPoint1, mappoint_t* pPoint2, mappoint_t* pHitPoint, gdouble fMaxDistance, mappoint_t* pReturnClosestPoint, gdouble* pfReturnPercentAlongLine)
 {
 	if(pHitPoint->fLatitude < (pPoint1->fLatitude - fMaxDistance) && pHitPoint->fLatitude < (pPoint2->fLatitude - fMaxDistance)) return FALSE;
diff --git a/src/map_math.c b/src/map_math.c
index 6d820ff..3d63b80 100644
--- a/src/map_math.c
+++ b/src/map_math.c
@@ -23,6 +23,7 @@
 
 #include <gtk/gtk.h>
 #include "map.h"
+#include "map_math.h"
 
 // ========================================================
 //  Coordinate Conversion Functions
@@ -65,6 +66,20 @@ void map_windowpoint_to_mappoint(map_t* pMap, screenpoint_t* pScreenPoint, mappo
 	pMapPoint->fLatitude = pMap->MapCenter.fLatitude - map_pixels_to_degrees(pMap, nPixelDeltaY, pMap->uZoomLevel);
 }
 
+EOverlapType map_rect_a_overlap_type_with_rect_b(const maprect_t* pA, const maprect_t* pB)
+{
+	// First, quickly determine if there is no overlap
+	if(map_rects_overlap(pA,pB) == FALSE) return OVERLAP_NONE;
+
+	if(pA->A.fLatitude < pB->A.fLatitude) return OVERLAP_PARTIAL;
+	if(pA->B.fLatitude > pB->B.fLatitude) return OVERLAP_PARTIAL;
+
+	if(pA->A.fLongitude < pB->A.fLongitude) return OVERLAP_PARTIAL;
+	if(pA->B.fLongitude > pB->B.fLongitude) return OVERLAP_PARTIAL;
+
+	return OVERLAP_FULL;
+}
+
 gboolean map_rects_overlap(const maprect_t* p1, const maprect_t* p2)
 {
 	if(p1->B.fLatitude < p2->A.fLatitude) return FALSE;
@@ -159,6 +174,169 @@ gboolean map_math_maprects_equal(maprect_t* pA, maprect_t* pB)
 	return map_points_equal(&(pA->A), &(pB->A)) && map_points_equal(&(pA->B), &(pB->B));
 }
 
+//
+// clipping a map polygon (array of mappoints) to a maprect
+//
+typedef enum { EDGE_NORTH, EDGE_SOUTH, EDGE_EAST, EDGE_WEST, EDGE_FIRST=0, EDGE_LAST=3 } ERectEdge;
+
+// static map_math_clip_line_to_worldrect_edge_recursive(mappoint_t* pA, mappoint_t* pB, maprect_t* pRect, ERectEdge eEdge, GArray* pOutput)
+// {
+//
+// }
+
+gboolean map_math_mappoint_in_maprect(const mappoint_t* pPoint, const maprect_t* pRect)
+{
+	if(pPoint->fLatitude < pRect->A.fLatitude) return FALSE;
+	if(pPoint->fLatitude > pRect->B.fLatitude) return FALSE;
+	if(pPoint->fLongitude < pRect->A.fLongitude) return FALSE;
+	if(pPoint->fLongitude > pRect->B.fLongitude) return FALSE;
+	return TRUE;
+}
+
+void map_math_clip_pointstring_to_worldrect(GArray* pMapPointsArray, maprect_t* pRect, GArray* pOutput)
+{
+	gint nLen = pMapPointsArray->len;
+	if(nLen <= 2) return;
+
+	mappoint_t* pA = &g_array_index(pMapPointsArray, mappoint_t, 0);
+	mappoint_t* pB = NULL;
+
+	gboolean bPointAIsInside = map_math_mappoint_in_maprect(pA, pRect);
+
+	gint i;
+	for(i=1 ; i<pMapPointsArray->len ; i++) {
+		gint iEdge;
+		for(iEdge=EDGE_FIRST ; iEdge<=EDGE_LAST ; iEdge++) {
+			switch(iEdge) {
+			case EDGE_NORTH:
+				break;
+			case EDGE_SOUTH:
+				break;
+			case EDGE_EAST:
+				break;
+			case EDGE_WEST:
+				break;
+			}
+		}
+	}
+}
+
+void static map_math_simplify_pointstring_recursive(const GArray* pInput, gint8* pabInclude, gdouble fTolerance, gint iFirst, gint iLast)
+{
+	if(iFirst+1 >= iLast) return;	// no points between first and last?
+
+	mappoint_t* pA = &g_array_index(pInput, mappoint_t, iFirst);
+	mappoint_t* pB = &g_array_index(pInput, mappoint_t, iLast);
+
+	// Init to bad values
+	gint iFarthestIndex = -1;
+	gdouble fBiggestDistanceSquared = 0.0;
+
+	// Of all points between A and B, which is farthest from the line AB?
+	mappoint_t* pPoint;
+	gint i;
+	for(i=(iFirst+1) ; i<=(iLast-1) ; i++) {
+		pPoint = &g_array_index(pInput, mappoint_t, i);
+		gdouble fDistanceSquared = map_math_point_distance_squared_from_line(pPoint, pA, pB);
+
+		if(fDistanceSquared > fBiggestDistanceSquared) {
+			fBiggestDistanceSquared = fDistanceSquared;
+			iFarthestIndex = i;
+		}
+	}
+	if(fBiggestDistanceSquared > (fTolerance * fTolerance) && (iFarthestIndex != -1)) {	// add last test just in case fTolerance == 0.0
+		// Mark for inclusion
+		pabInclude[iFarthestIndex] = 1;
+
+		map_math_simplify_pointstring_recursive(pInput, pabInclude, fTolerance, iFirst, iFarthestIndex);
+		map_math_simplify_pointstring_recursive(pInput, pabInclude, fTolerance, iFarthestIndex, iLast);
+	}
+}
+
+void map_math_simplify_pointstring(const GArray* pInput, gdouble fTolerance, GArray* pOutput)
+{
+	if(pInput->len < 2) return;
+
+	gint8* pabInclude = g_new0(gint8, pInput->len + 20);
+
+	// Mark first and last points
+	pabInclude[0] = 1;
+	pabInclude[pInput->len-1] = 1;
+
+	map_math_simplify_pointstring_recursive(pInput, pabInclude, fTolerance, 0, pInput->len-1);  
+
+	//
+	// cleanup
+	//
+	mappoint_t* pPoint;
+	gint i;
+	for(i=0 ; i<pInput->len ; i++) {
+		pPoint = &g_array_index(pInput, mappoint_t, i);
+		if(pabInclude[i] == 1) {
+			g_array_append_val(pOutput, *pPoint);
+		}
+	}
+	g_free(pabInclude);
+}
+
+// Does the given point come close enough to the line segment to be considered a hit?
+gdouble map_math_point_distance_squared_from_line(mappoint_t* pHitPoint, mappoint_t* pPoint1, mappoint_t* pPoint2)
+{
+	// Some bad ASCII art demonstrating the situation:
+	//
+	//             / (u)
+	//          /  |
+	//       /     |
+	// (0,0) =====(a)========== (v)
+
+	// v is the translated-to-origin vector of line
+	// u is the translated-to-origin vector of the hitpoint
+	// a is the closest point on v to the end of u (the hit point)
+
+	//
+	// 1. Convert p1->p2 vector into a vector (v) that is assumed to come out of the origin (0,0)
+	//
+	mappoint_t v;
+	v.fLatitude = pPoint2->fLatitude - pPoint1->fLatitude;	// 10->90 becomes 0->80 (just store 80)
+	v.fLongitude = pPoint2->fLongitude - pPoint1->fLongitude;
+
+	gdouble fLengthV = sqrt((v.fLatitude*v.fLatitude) + (v.fLongitude*v.fLongitude));
+	if(fLengthV == 0.0) return FALSE;	// bad data: a line segment with no length?
+
+	//
+	// 2. Make a unit vector out of v (meaning same direction but length=1) by dividing v by v's length
+	//
+	mappoint_t unitv;
+	unitv.fLatitude = v.fLatitude / fLengthV;
+	unitv.fLongitude = v.fLongitude / fLengthV;	// unitv is now a unit (=1.0) length v
+
+	//
+	// 3. Translate the hitpoint in the same way we translated v
+	//
+	mappoint_t u;
+	u.fLatitude = pHitPoint->fLatitude - pPoint1->fLatitude;
+	u.fLongitude = pHitPoint->fLongitude - pPoint1->fLongitude;
+
+	//
+	// 4. Use the dot product of (unitv) and (u) to find (a), the point along (v) that is closest to (u). see diagram above.
+	//
+	gdouble fLengthAlongV = (unitv.fLatitude * u.fLatitude) + (unitv.fLongitude * u.fLongitude);
+
+	mappoint_t a;
+	a.fLatitude = v.fLatitude * (fLengthAlongV / fLengthV);	// multiply each component by the percentage
+	a.fLongitude = v.fLongitude * (fLengthAlongV / fLengthV);
+	// NOTE: (a) is *not* where it actually hit on the *map*.  don't draw this point!  we'd have to translate it back away from the origin.
+
+	//
+	// 5. Calculate the distance from the end of (u) to (a).  If it's less than the fMaxDistance, it's a hit.
+	//
+	gdouble fRise = u.fLatitude - a.fLatitude;
+	gdouble fRun = u.fLongitude - a.fLongitude;
+	gdouble fDistanceSquared = fRise*fRise + fRun*fRun;	// compare squared distances. same results but without the sqrt.
+
+	return fDistanceSquared;
+}
+
 
 #ifdef ROADSTER_DEAD_CODE
 /*
diff --git a/src/map_math.h b/src/map_math.h
index 5643b98..b7c6c99 100644
--- a/src/map_math.h
+++ b/src/map_math.h
@@ -24,7 +24,19 @@
 #ifndef _MAP_MATH_H_
 #define _MAP_MATH_H_
 
+typedef enum {
+	OVERLAP_FULL,
+	OVERLAP_NONE,
+	OVERLAP_PARTIAL
+} EOverlapType;
+
 gboolean map_math_screenpoint_in_screenrect(screenpoint_t* pPt, screenrect_t* pRect);
 gboolean map_math_maprects_equal(maprect_t* pA, maprect_t* pB);
 
+EOverlapType map_rect_a_overlap_type_with_rect_b(const maprect_t* pA, const maprect_t* pB);
+gboolean map_rects_overlap(const maprect_t* p1, const maprect_t* p2);
+
+void map_math_simplify_pointstring(const GArray* pInput, gdouble fTolerance, GArray* pOutput);
+gdouble map_math_point_distance_squared_from_line(mappoint_t* pHitPoint, mappoint_t* pPoint1, mappoint_t* pPoint2);
+
 #endif
diff --git a/src/test_poly.c b/src/test_poly.c
new file mode 100644
index 0000000..6208806
--- /dev/null
+++ b/src/test_poly.c
@@ -0,0 +1,209 @@
+#ifdef HAVE_CONFIG_H
+#  include <config.h>
+#endif
+
+#include <gtk/gtk.h>
+#include <glade/glade.h>
+#include <cairo.h>
+#include <cairo-xlib.h>
+
+#include "gui.h"
+#include "map.h"
+#include "util.h"
+
+struct {
+	GtkWindow* pWindow;
+
+	GtkHScale* pScale;
+	GtkVBox* pContentBox;
+	GtkButton* pClearButton;
+	GtkDrawingArea* pDrawingArea;
+	GtkLabel* pLabel;
+	
+	GArray* pPointsArray;
+} g_Test_Poly;
+
+static gboolean on_time_to_update(GtkWidget *pDrawingArea, GdkEventExpose *event, gpointer data);
+static void test_poly_draw();
+static gboolean on_mouse_button_click(GtkWidget* w, GdkEventButton *event);
+static gboolean on_clear_clicked(GtkWidget* w, GdkEventButton *event);
+
+void test_poly_init(GladeXML* pGladeXML)
+{
+	GLADE_LINK_WIDGET(pGladeXML, g_Test_Poly.pWindow, GTK_WINDOW, "test_polywindow");
+	GLADE_LINK_WIDGET(pGladeXML, g_Test_Poly.pScale, GTK_HSCALE, "test_poly_scale");
+	GLADE_LINK_WIDGET(pGladeXML, g_Test_Poly.pContentBox, GTK_VBOX, "test_poly_contentbox");
+	GLADE_LINK_WIDGET(pGladeXML, g_Test_Poly.pClearButton, GTK_BUTTON, "test_poly_clear_button");
+	GLADE_LINK_WIDGET(pGladeXML, g_Test_Poly.pLabel, GTK_LABEL, "test_polylabel");
+	GLADE_LINK_WIDGET(pGladeXML, g_Test_Poly.pDrawingArea, GTK_DRAWING_AREA, "test_polydrawingarea");
+
+	g_Test_Poly.pPointsArray = g_array_new(FALSE, FALSE, sizeof(mappoint_t));
+
+	// Drawing area
+	gtk_widget_set_double_buffered(GTK_WIDGET(g_Test_Poly.pDrawingArea), FALSE);
+	gtk_widget_add_events(GTK_WIDGET(g_Test_Poly.pDrawingArea), GDK_EXPOSURE_MASK | GDK_BUTTON_PRESS_MASK);
+	g_signal_connect(G_OBJECT(g_Test_Poly.pDrawingArea), "expose-event", G_CALLBACK(on_time_to_update), NULL);
+	g_signal_connect(G_OBJECT(g_Test_Poly.pDrawingArea), "button_press_event", G_CALLBACK(on_mouse_button_click), NULL);
+
+	// Scale
+	g_signal_connect(G_OBJECT(g_Test_Poly.pScale), "value-changed", G_CALLBACK(on_time_to_update), NULL);
+	// make it instant-change using our hacky callback
+	//g_signal_connect(G_OBJECT(g_Test_Poly.pScale), "change-value", G_CALLBACK(util_gtk_range_instant_set_on_value_changing_callback), NULL);
+
+	// "Clear" button
+	g_signal_connect(G_OBJECT(g_Test_Poly.pClearButton), "clicked", G_CALLBACK(on_clear_clicked), NULL);
+
+	// don't delete window on X, just hide it
+	g_signal_connect(G_OBJECT(g_Test_Poly.pWindow), "delete_event", G_CALLBACK(gtk_widget_hide), NULL);
+}
+
+void test_poly_show(GtkMenuItem *menuitem, gpointer user_data)
+{
+	gtk_widget_show(GTK_WIDGET(g_Test_Poly.pWindow));
+}
+
+static gboolean on_clear_clicked(GtkWidget* w, GdkEventButton *event)
+{
+	g_array_remove_range(g_Test_Poly.pPointsArray, 0, g_Test_Poly.pPointsArray->len);
+	gtk_widget_queue_draw(GTK_WIDGET(g_Test_Poly.pDrawingArea));
+}
+
+static gboolean on_mouse_button_click(GtkWidget* w, GdkEventButton *event)
+{
+	gint nX, nY;
+	gdk_window_get_pointer(w->window, &nX, &nY, NULL);
+
+	gint nWidth = GTK_WIDGET(g_Test_Poly.pDrawingArea)->allocation.width;
+	gint nHeight = GTK_WIDGET(g_Test_Poly.pDrawingArea)->allocation.height;
+
+	mappoint_t point;
+	point.fLongitude = (gdouble)nX / (gdouble)nWidth;
+	point.fLatitude = (gdouble)nY / (gdouble)nHeight;
+	g_array_append_val(g_Test_Poly.pPointsArray, point);
+
+	gtk_widget_queue_draw(GTK_WIDGET(g_Test_Poly.pDrawingArea));
+}
+
+void test_poly_draw_array(cairo_t* pCairo, GArray* pArray)
+{
+	if(pArray->len >= 1) {
+		mappoint_t* pPoint;
+		pPoint = &g_array_index(pArray, mappoint_t, 0);
+		cairo_move_to(pCairo, pPoint->fLongitude, pPoint->fLatitude);
+		cairo_arc(pCairo, pPoint->fLongitude, pPoint->fLatitude, 0.02, 0, 2*M_PI);
+		cairo_fill(pCairo);
+		cairo_move_to(pCairo, pPoint->fLongitude, pPoint->fLatitude);
+		gint i;
+		for(i=1 ; i<pArray->len ;i++) {
+			pPoint = &g_array_index(pArray, mappoint_t, i);
+			cairo_line_to(pCairo, pPoint->fLongitude, pPoint->fLatitude);
+		}
+		pPoint = &g_array_index(pArray, mappoint_t, 0);
+		cairo_line_to(pCairo, pPoint->fLongitude, pPoint->fLatitude);
+	}
+}
+
+static gboolean on_time_to_update(GtkWidget *pDrawingArea, GdkEventExpose *event, gpointer data)
+{
+	Display* dpy;
+	Drawable drawable;
+	dpy = gdk_x11_drawable_get_xdisplay(GTK_WIDGET(g_Test_Poly.pDrawingArea)->window);
+	Visual *visual = DefaultVisual (dpy, DefaultScreen (dpy));
+	gint width, height;
+	drawable = gdk_x11_drawable_get_xid(GTK_WIDGET(g_Test_Poly.pDrawingArea)->window);
+	gdk_drawable_get_size (GTK_WIDGET(g_Test_Poly.pDrawingArea)->window, &width, &height);
+	cairo_surface_t *pSurface = cairo_xlib_surface_create (dpy, drawable, visual, width, height);
+
+	gdouble fValue = gtk_range_get_value(g_Test_Poly.pScale);
+
+	cairo_t* pCairo = cairo_create (pSurface);
+
+	cairo_scale(pCairo, width, height);
+
+	cairo_set_source_rgba(pCairo, 1.0, 1.0, 1.0, 1.0);
+	cairo_rectangle(pCairo, 0.0, 0.0, 1.0, 1.0);
+	cairo_fill(pCairo);
+
+	// Draw lines
+	cairo_set_line_join(pCairo, CAIRO_LINE_JOIN_ROUND);
+	cairo_save(pCairo);
+	cairo_set_line_width(pCairo, 0.02);
+	cairo_set_source_rgba(pCairo, 1.0, 0.0, 0.0, 1.0);
+	test_poly_draw_array(pCairo, g_Test_Poly.pPointsArray);
+	cairo_stroke(pCairo);
+	cairo_restore(pCairo);
+
+	cairo_save(pCairo);
+	GArray* pSimplified = g_array_new(FALSE, FALSE, sizeof(mappoint_t));
+	map_math_simplify_pointstring(g_Test_Poly.pPointsArray, fValue, pSimplified);
+	cairo_set_line_width(pCairo, 0.01);
+	cairo_set_source_rgba(pCairo, 0.0, 1.0, 0.0, 0.5);
+	test_poly_draw_array(pCairo, pSimplified);
+	cairo_fill(pCairo);
+	cairo_restore(pCairo);
+
+	cairo_destroy(pCairo);
+
+	if(g_Test_Poly.pPointsArray->len == 0) {
+		gtk_label_set_markup(g_Test_Poly.pLabel, "<b>Click to create points</b>");
+	}
+	else {
+		gchar* pszMarkup = g_strdup_printf("%d points, %d simplified", g_Test_Poly.pPointsArray->len, pSimplified->len);
+		gtk_label_set_markup(g_Test_Poly.pLabel, pszMarkup);
+		g_free(pszMarkup);
+	}
+
+	g_array_free(pSimplified, TRUE);
+	return TRUE;
+}
+
+// static void paint (GtkWidget      *widget,GdkEventExpose *eev,gpointer        data)
+// {
+//   gint width, height;
+//   gint i;
+//   cairo_t *cr;
+//
+//   width  = widget->allocation.width;
+//   height = widget->allocation.height;
+//
+//   cr = gdk_cairo_create (widget->window);
+//
+//     /* clear background */
+//     cairo_set_source_rgb (cr, 1,1,1);
+//     cairo_paint (cr);
+//
+//
+//     cairo_select_font_face (cr, "Sans", CAIRO_FONT_SLANT_NORMAL,
+//                                         CAIRO_FONT_WEIGHT_BOLD);
+//
+//     /* enclosing in a save/restore pair since we alter the
+//      * font size
+//      */
+//     cairo_save (cr);
+//       cairo_set_font_size (cr, 40);
+//       cairo_move_to (cr, 40, 60);
+//       cairo_set_source_rgb (cr, 0,0,0);
+//       cairo_show_text (cr, "Hello World");
+//     cairo_restore (cr);
+//
+//     cairo_set_source_rgb (cr, 1,0,0);
+//     cairo_set_font_size (cr, 20);
+//     cairo_move_to (cr, 50, 100);
+//     cairo_show_text (cr, "greetings from gtk and cairo");
+//
+//     cairo_set_source_rgb (cr, 0,0,1);
+//
+//     cairo_move_to (cr, 0, 150);
+//     for (i=0; i< width/10; i++)
+//       {
+//         cairo_rel_line_to (cr, 5,  10);
+//         cairo_rel_line_to (cr, 5, -10);
+//       }
+//     cairo_stroke (cr);
+//
+//   cairo_destroy (cr);
+// }
+//
+// static gboolean on_expose_event(GtkWidget *pDrawingArea, GdkEventExpose *event, gpointer data)
+// {
+// }
diff --git a/src/test_poly.h b/src/test_poly.h
new file mode 100644
index 0000000..c0476f6
--- /dev/null
+++ b/src/test_poly.h
@@ -0,0 +1,31 @@
+/***************************************************************************
+ *            test_poly.h
+ *
+ *  Copyright  2005  Ian McIntosh
+ *  ian_mcintosh@linuxadvocate.org
+ ****************************************************************************/
+
+/*
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU Library General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ */
+
+#ifndef _TEST_POLY_H_
+#define _TEST_POLY_H_
+
+#include <glade/glade.h>
+
+void test_poly_init(GladeXML* pGladeXML);
+
+#endif