[cairo-commit] roadster/src Makefile.am, 1.24, 1.25 gui.c, 1.15, 1.16 main.h, 1.7, 1.8 mainwindow.c, 1.50, 1.51 map.c, 1.53, 1.54 map_draw_gdk.c, 1.27, 1.28 map_hittest.c, 1.1, 1.2 map_math.c, 1.2, 1.3 map_math.h, 1.1, 1.2 test_poly.c, NONE, 1.1 test_poly.h, NONE, 1.1

Ian McIntosh commit at pdx.freedesktop.org
Tue Oct 11 16:28:47 PDT 2005


Committed by: ian

Update of /cvs/cairo/roadster/src
In directory gabe:/tmp/cvs-serv21077/src

Modified Files:
	Makefile.am gui.c main.h mainwindow.c map.c map_draw_gdk.c 
	map_hittest.c map_math.c map_math.h 
Added Files:
	test_poly.c test_poly.h 
Log Message:
	* src/test_poly.c:
	* src/test_poly.h: Added to test polygon point reduction algorithm and others.
	* src/map_draw_gdk.c: Prepare for rectangle clipping.
	* src/map_math.c: Add Douglas-Peucker point simplification algorithm.  Add point distance from line function.  Add in/out/partial rect overlap function.


Index: Makefile.am
===================================================================
RCS file: /cvs/cairo/roadster/src/Makefile.am,v
retrieving revision 1.24
retrieving revision 1.25
diff -u -d -r1.24 -r1.25
--- Makefile.am	5 Oct 2005 06:09:36 -0000	1.24
+++ Makefile.am	11 Oct 2005 23:28:45 -0000	1.25
@@ -21,10 +21,12 @@
 	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 @@
 	road.c\
 	animator.c\
 	gfreelist.c\
-	tooltipwindow.c
+	tooltipwindow.c\
+	test_poly.c
 
 roadster_LDADD = \
 	$(GNOME_LIBS) \

Index: gui.c
===================================================================
RCS file: /cvs/cairo/roadster/src/gui.c,v
retrieving revision 1.15
retrieving revision 1.16
diff -u -d -r1.15 -r1.16
--- gui.c	1 Oct 2005 05:24:16 -0000	1.15
+++ gui.c	11 Oct 2005 23:28:45 -0000	1.16
@@ -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 @@
 	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);

Index: main.h
===================================================================
RCS file: /cvs/cairo/roadster/src/main.h,v
retrieving revision 1.7
retrieving revision 1.8
diff -u -d -r1.7 -r1.8
--- main.h	10 Oct 2005 07:07:36 -0000	1.7
+++ main.h	11 Oct 2005 23:28:45 -0000	1.8
@@ -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)

Index: mainwindow.c
===================================================================
RCS file: /cvs/cairo/roadster/src/mainwindow.c,v
retrieving revision 1.50
retrieving revision 1.51
diff -u -d -r1.50 -r1.51
--- mainwindow.c	10 Oct 2005 07:07:36 -0000	1.50
+++ mainwindow.c	11 Oct 2005 23:28:45 -0000	1.51
@@ -48,6 +48,7 @@
 #include "glyph.h"
 #include "animator.h"
 #include "map_history.h"
+#include "mapinfowindow.h"
 
 #include "tooltipwindow.h"
 
@@ -447,7 +448,7 @@
 	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 @@
 	// 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)

Index: map.c
===================================================================
RCS file: /cvs/cairo/roadster/src/map.c,v
retrieving revision 1.53
retrieving revision 1.54
diff -u -d -r1.53 -r1.54
--- map.c	10 Oct 2005 07:07:36 -0000	1.53
+++ map.c	11 Oct 2005 23:28:45 -0000	1.54
@@ -158,7 +158,7 @@
 // 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)

Index: map_draw_gdk.c
===================================================================
RCS file: /cvs/cairo/roadster/src/map_draw_gdk.c,v
retrieving revision 1.27
retrieving revision 1.28
diff -u -d -r1.27 -r1.28
--- map_draw_gdk.c	10 Oct 2005 07:07:36 -0000	1.27
+++ map_draw_gdk.c	11 Oct 2005 23:28:45 -0000	1.28
@@ -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_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 @@
 	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 @@
 		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 @@
 			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 @@
 	}
 }
 
-// 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 @@
 
 	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 @@
 			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);
 	}
 }
 

Index: map_hittest.c
===================================================================
RCS file: /cvs/cairo/roadster/src/map_hittest.c,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- map_hittest.c	6 Oct 2005 00:00:53 -0000	1.1
+++ map_hittest.c	11 Oct 2005 23:28:45 -0000	1.2
@@ -333,7 +333,7 @@
 	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;

Index: map_math.c
===================================================================
RCS file: /cvs/cairo/roadster/src/map_math.c,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- map_math.c	10 Oct 2005 07:07:36 -0000	1.2
+++ map_math.c	11 Oct 2005 23:28:45 -0000	1.3
@@ -23,6 +23,7 @@
 
 #include <gtk/gtk.h>
 #include "map.h"
+#include "map_math.h"
 
 // ========================================================
 //  Coordinate Conversion Functions
@@ -65,6 +66,20 @@
 	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 @@
 	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
 /*

Index: map_math.h
===================================================================
RCS file: /cvs/cairo/roadster/src/map_math.h,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- map_math.h	6 Oct 2005 00:02:39 -0000	1.1
+++ map_math.h	11 Oct 2005 23:28:45 -0000	1.2
@@ -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

--- NEW FILE: test_poly.c ---
#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)
// {
// }

--- NEW FILE: test_poly.h ---
/***************************************************************************
 *            test_poly.h
 *
 *  Copyright  2005  Ian McIntosh
 *  ian_mcintosh at 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



More information about the cairo-commit mailing list