From 6c9c0b8a29cd0eb64e3f1103ca3363ccff7b3eba Mon Sep 17 00:00:00 2001 From: neoraider Date: Sat, 23 Jun 2007 19:00:05 +0000 Subject: zoomedit: Implemented geometry functions. --- Makefile.am | 2 +- Makefile.in | 20 +++++- draw.c | 33 +++++++-- geometry.c | 218 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ geometry.h | 50 ++++++++++++++ level.c | 32 --------- level.h | 13 +--- 7 files changed, 315 insertions(+), 53 deletions(-) create mode 100644 geometry.c create mode 100644 geometry.h diff --git a/Makefile.am b/Makefile.am index 982a8f5..cc6a9ee 100644 --- a/Makefile.am +++ b/Makefile.am @@ -1,4 +1,4 @@ bin_PROGRAMS = zoomedit -zoomedit_SOURCES = zoomedit.c window.c ui.c draw.c level.c +zoomedit_SOURCES = zoomedit.c window.c ui.c draw.c level.c geometry.c zoomedit_CFLAGS = @GTK_CFLAGS@ zoomedit_LDADD = @GTK_LIBS@ \ No newline at end of file diff --git a/Makefile.in b/Makefile.in index 996f221..b6777e9 100644 --- a/Makefile.in +++ b/Makefile.in @@ -50,7 +50,8 @@ binPROGRAMS_INSTALL = $(INSTALL_PROGRAM) PROGRAMS = $(bin_PROGRAMS) am_zoomedit_OBJECTS = zoomedit-zoomedit.$(OBJEXT) \ zoomedit-window.$(OBJEXT) zoomedit-ui.$(OBJEXT) \ - zoomedit-draw.$(OBJEXT) zoomedit-level.$(OBJEXT) + zoomedit-draw.$(OBJEXT) zoomedit-level.$(OBJEXT) \ + zoomedit-geometry.$(OBJEXT) zoomedit_OBJECTS = $(am_zoomedit_OBJECTS) zoomedit_DEPENDENCIES = zoomedit_LINK = $(CCLD) $(zoomedit_CFLAGS) $(CFLAGS) $(AM_LDFLAGS) \ @@ -165,7 +166,7 @@ sysconfdir = @sysconfdir@ target_alias = @target_alias@ top_builddir = @top_builddir@ top_srcdir = @top_srcdir@ -zoomedit_SOURCES = zoomedit.c window.c ui.c draw.c level.c +zoomedit_SOURCES = zoomedit.c window.c ui.c draw.c level.c geometry.c zoomedit_CFLAGS = @GTK_CFLAGS@ zoomedit_LDADD = @GTK_LIBS@ all: config.h @@ -257,6 +258,7 @@ distclean-compile: -rm -f *.tab.c @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/zoomedit-draw.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/zoomedit-geometry.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/zoomedit-level.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/zoomedit-ui.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/zoomedit-window.Po@am__quote@ @@ -346,6 +348,20 @@ zoomedit-level.obj: level.c @AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ @am__fastdepCC_FALSE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(zoomedit_CFLAGS) $(CFLAGS) -c -o zoomedit-level.obj `if test -f 'level.c'; then $(CYGPATH_W) 'level.c'; else $(CYGPATH_W) '$(srcdir)/level.c'; fi` +zoomedit-geometry.o: geometry.c +@am__fastdepCC_TRUE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(zoomedit_CFLAGS) $(CFLAGS) -MT zoomedit-geometry.o -MD -MP -MF $(DEPDIR)/zoomedit-geometry.Tpo -c -o zoomedit-geometry.o `test -f 'geometry.c' || echo '$(srcdir)/'`geometry.c +@am__fastdepCC_TRUE@ mv -f $(DEPDIR)/zoomedit-geometry.Tpo $(DEPDIR)/zoomedit-geometry.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='geometry.c' object='zoomedit-geometry.o' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(zoomedit_CFLAGS) $(CFLAGS) -c -o zoomedit-geometry.o `test -f 'geometry.c' || echo '$(srcdir)/'`geometry.c + +zoomedit-geometry.obj: geometry.c +@am__fastdepCC_TRUE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(zoomedit_CFLAGS) $(CFLAGS) -MT zoomedit-geometry.obj -MD -MP -MF $(DEPDIR)/zoomedit-geometry.Tpo -c -o zoomedit-geometry.obj `if test -f 'geometry.c'; then $(CYGPATH_W) 'geometry.c'; else $(CYGPATH_W) '$(srcdir)/geometry.c'; fi` +@am__fastdepCC_TRUE@ mv -f $(DEPDIR)/zoomedit-geometry.Tpo $(DEPDIR)/zoomedit-geometry.Po +@AMDEP_TRUE@@am__fastdepCC_FALSE@ source='geometry.c' object='zoomedit-geometry.obj' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCC_FALSE@ DEPDIR=$(DEPDIR) $(CCDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCC_FALSE@ $(CC) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(AM_CPPFLAGS) $(CPPFLAGS) $(zoomedit_CFLAGS) $(CFLAGS) -c -o zoomedit-geometry.obj `if test -f 'geometry.c'; then $(CYGPATH_W) 'geometry.c'; else $(CYGPATH_W) '$(srcdir)/geometry.c'; fi` + ID: $(HEADERS) $(SOURCES) $(LISP) $(TAGS_FILES) list='$(SOURCES) $(HEADERS) $(LISP) $(TAGS_FILES)'; \ unique=`for i in $$list; do \ diff --git a/draw.c b/draw.c index 11840ee..f782ddd 100644 --- a/draw.c +++ b/draw.c @@ -1,5 +1,6 @@ #include "draw.h" #include "level.h" +#include "geometry.h" #include #include @@ -7,18 +8,31 @@ static double scale = 100.0; static double xTranslate = 0.0, yTranslate = 0.0; -static void room2path(cairo_t *cr, ROOM *room) { + +static void room2path(cairo_t *cr, ROOM *room, RECTANGLE *rect) { int i; + ROOM room2 = {0, NULL}; - + // no vertices if(room->nVertices == 0) return; - cairo_move_to(cr, room->vertices[0].x, room->vertices[0].y); + if(rect) + simplifyPolygon(room, rect, &room2); + else + room2 = *room; + + if(room2.nVertices == 0) return; - for(i = 1; i < room->nVertices; i++) - cairo_line_to(cr, room->vertices[i].x, room->vertices[i].y); + cairo_new_sub_path(cr); + + for(i = 0; i < room2.nVertices; i++) { + cairo_line_to(cr, room2.vertices[i].x, room2.vertices[i].y); + } cairo_close_path(cr); + + if(rect && room2.vertices) + free(room2.vertices); } gboolean drawTopView(GtkWidget *widget, GdkEventExpose *event, gpointer data) { @@ -26,21 +40,26 @@ gboolean drawTopView(GtkWidget *widget, GdkEventExpose *event, gpointer data) { ROOM room = {sizeof(vertices)/sizeof(vertices[0]), vertices}; LEVEL lvl = {1, &room}; cairo_t *cr; + RECTANGLE rect = {-5, -5, widget->allocation.width+10, widget->allocation.height+10}; int i; cr = gdk_cairo_create(widget->window); - cairo_rectangle(cr, event->area.x, event->area.y, event->area.width, event->area.height); + gdk_cairo_region(cr, event->region); cairo_clip(cr); cairo_translate(cr, getImageWidth()/2-xTranslate, getImageHeight()/2-yTranslate); cairo_scale(cr, scale, scale); + cairo_device_to_user(cr, &rect.x, &rect.y); + cairo_device_to_user_distance(cr, &rect.width, &rect.height); + cairo_set_line_width(cr, 1.0/scale); + cairo_set_line_join(cr, CAIRO_LINE_JOIN_MITER); for(i = 0; i < lvl.nRooms; i++) - room2path(cr, &lvl.rooms[i]); + room2path(cr, &lvl.rooms[i], &rect); cairo_set_source_rgba(cr, 0.0, 0.7, 1.0, 0.3); cairo_fill_preserve(cr); diff --git a/geometry.c b/geometry.c new file mode 100644 index 0000000..238e2fa --- /dev/null +++ b/geometry.c @@ -0,0 +1,218 @@ +#include "geometry.h" +#include +#include +#include + + +void addVertex(VERTEX_LIST *list, VERTEX *v) { + list->nVertices++; + list->vertices = realloc(list->vertices, list->nVertices*sizeof(VERTEX)); + list->vertices[list->nVertices-1] = *v; +} + +void insertVertex(VERTEX_LIST *list, VERTEX *v, unsigned int n) { + int i; + + if(n > list->nVertices) + n = list->nVertices; + + list->nVertices++; + list->vertices = realloc(list->vertices, list->nVertices*sizeof(VERTEX)); + + for(i = list->nVertices-1; i > n; i--) + list->vertices[i] = list->vertices[i-1]; + + list->vertices[n] = *v; +} + +void deleteVertex(VERTEX_LIST *list, unsigned int n) { + int i; + + list->nVertices--; + + for(i = n; i < list->nVertices; i++) + list->vertices[i] = list->vertices[i+1]; + + list->vertices = realloc(list->vertices, list->nVertices*sizeof(VERTEX)); +} + +double vertexDistanceSquare(const VERTEX *v1, const VERTEX *v2) { + return (v1->x-v2->x)*(v1->x-v2->x) + (v1->y-v2->y)*(v1->y-v2->y); +} + +double vertexDistance(const VERTEX *v1, const VERTEX *v2) { + return sqrt(vertexDistanceSquare(v1, v2)); +} + + +int vertexInRect(const VERTEX *v, const RECTANGLE *rect) { + int ret = EDGE_NONE; + + if(v->x < rect->x) ret |= EDGE_LEFT; + else if(v->x >= rect->x+rect->width) ret |= EDGE_RIGHT; + + if(v->y < rect->y) ret |= EDGE_TOP; + else if(v->y >= rect->y+rect->height) ret |= EDGE_BOTTOM; + + return ret; +} + +int lineIntersection(const LINE *la, const LINE *lb, VERTEX *v) { + double xa1 = la->v1.x, ya1 = la->v1.y; + double xa2 = la->v2.x, ya2 = la->v2.y; + double xb1 = lb->v1.x, yb1 = lb->v1.y; + double xb2 = lb->v2.x, yb2 = lb->v2.y; + double temp; + int switched = 0; + + + if(xa1 == xa2 && ya1 == ya2) return INTERSECTION_ERROR; + if(xb1 == xb2 && yb1 == yb2) return INTERSECTION_ERROR; + + if(xa1 == xa2 || xb1 == xb2) { + temp = xa1; xa1 = ya1; ya1 = temp; + temp = xa2; xa2 = ya2; ya2 = temp; + temp = xb1; xb1 = yb1; yb1 = temp; + temp = xb2; xb2 = yb2; yb2 = temp; + + switched = 1; + } + + double ma = (ya2-ya1)/(xa2-xa1); + double mb = (yb2-yb1)/(xb2-xb1); + double ba = ya1 - ma*xa1; + double bb = yb1 - mb*xb1; + + if(ma == mb) return (ba == bb) ? INTERSECTION_IDENTICAL : INTERSECTION_NONE; + + if(isinf(ma)) { + v->x = xa1; + v->y = yb1; + } + else if(isinf(mb)) { + v->x = xb1; + v->y = ya1; + } + else { + v->x = (bb-ba)/(ma-mb); + v->y = ma*v->x + ba; + } + + if(switched) { + temp = v->x; v->x = v->y; v->y = temp; + + //switch back everything for segment tests + temp = xa1; xa1 = ya1; ya1 = temp; + temp = xa2; xa2 = ya2; ya2 = temp; + temp = xb1; xb1 = yb1; yb1 = temp; + temp = xb2; xb2 = yb2; yb2 = temp; + } + + if(v->x < MIN(xa1,xa2) || v->x > MAX(xa1, xa2) || v->y < MIN(ya1,ya2) || v->y > MAX(ya1, ya2)) { + if(v->x < MIN(xb1,xb2) || v->x > MAX(xb1, xb2) || v->y < MIN(yb1,yb2) || v->y > MAX(yb1, yb2)) + return INTERSECTION_LINE_LINE; + else + return INTERSECTION_LINE_SEGMENT; + } + else if(v->x < MIN(xb1,xb2) || v->x > MAX(xb1, xb2) || v->y < MIN(yb1,yb2) || v->y > MAX(yb1, yb2)) + return INTERSECTION_SEGMENT_LINE; + else + return INTERSECTION_SEGMENT_SEGMENT; +} + +int lineRectIntersection(const LINE *l, const RECTANGLE *rect, int edge, VERTEX *v) { + const double minX = rect->x, maxX = rect->x+rect->width; + const double minY = rect->y, maxY = rect->y+rect->height; + const LINE top = {{minX, minY}, {maxX, minY}}; + const LINE bottom = {{minX, maxY}, {maxX, maxY}}; + const LINE left = {{minX, minY}, {minX, maxY}}; + const LINE right = {{maxX, minY}, {maxX, maxY}}; + + if((edge & EDGE_TOP) && (lineIntersection(&top, l, v) == INTERSECTION_SEGMENT_SEGMENT)) + return EDGE_TOP; + if((edge & EDGE_BOTTOM) && (lineIntersection(&bottom, l, v) == INTERSECTION_SEGMENT_SEGMENT)) + return EDGE_BOTTOM; + if((edge & EDGE_LEFT) && (lineIntersection(&left, l, v) == INTERSECTION_SEGMENT_SEGMENT)) + return EDGE_LEFT; + if((edge & EDGE_RIGHT) && (lineIntersection(&right, l, v) == INTERSECTION_SEGMENT_SEGMENT)) + return EDGE_RIGHT; + + v->x = v->y = 0; + + return EDGE_NONE; +} + +int lineRectIntersections(const LINE *line, const RECTANGLE *rect, int edge, VERTEX *v1, VERTEX *v2) { + int ret = EDGE_NONE; + + ret |= lineRectIntersection(line, rect, edge, v1); + ret |= lineRectIntersection(line, rect, EDGE_ALL^edge, v2); + + return ret; +} + +void simplifyPolygon(const POLYGON *in, const RECTANGLE *rect, POLYGON *out) { + int i, j; + int a; + int lastVertex, thisVertex; + VERTEX v, v2; + VERTEX_LIST vl = {0, NULL}; + LINE line; + LINE d1 = {{rect->x, rect->y}, {rect->x+rect->width, rect->y+rect->height}}; + LINE d2 = {{rect->x, rect->y+rect->height}, {rect->x+rect->width, rect->y}}; + + + thisVertex = vertexInRect(&in->vertices[0], rect); + + for(i = 0; i < in->nVertices; i++) { + line.v1 = in->vertices[i]; + line.v2 = in->vertices[(i+1)%in->nVertices]; + + lastVertex = thisVertex; + thisVertex = vertexInRect(&line.v2, rect); + + if(thisVertex == EDGE_NONE) { + if(lastVertex != EDGE_NONE && lineRectIntersection(&line, rect, lastVertex, &v)) + addVertex(&vl, &v); + + addVertex(&vl, &line.v2); + } + else if(lastVertex == EDGE_NONE) { + if(lineRectIntersection(&line, rect, thisVertex, &v)) + addVertex(&vl, &v); + } + else { + a = lineRectIntersections(&line, rect, lastVertex, &v, &v2); + + if((a & lastVertex) && (a & thisVertex)) { + addVertex(&vl, &v); + addVertex(&vl, &v2); + } + + if(lineIntersection(&line, &d1, &v) == INTERSECTION_SEGMENT_LINE) { + if(v.x <= rect->x) addVertex(&vl, &d1.v1); + else addVertex(&vl, &d1.v2); + } + + if(lineIntersection(&line, &d2, &v) == INTERSECTION_SEGMENT_LINE) { + if(v.x <= rect->x) addVertex(&vl, &d2.v1); + else addVertex(&vl, &d2.v2); + } + } + + while(vl.nVertices > 0) { + a = 0; + + for(j = 0; j < vl.nVertices; j++) { + if(vertexDistanceSquare(&line.v1, &vl.vertices[j]) < vertexDistanceSquare(&line.v1, &vl.vertices[a])) + a = j; + } + + if(out->nVertices == 0 || out->vertices[out->nVertices-1].x != vl.vertices[a].x || + out->vertices[out->nVertices-1].y != vl.vertices[a].y) + addVertex(out, &vl.vertices[a]); + + deleteVertex(&vl, a); + } + } +} diff --git a/geometry.h b/geometry.h new file mode 100644 index 0000000..c936e59 --- /dev/null +++ b/geometry.h @@ -0,0 +1,50 @@ +#ifndef GEOMETRY_H_ +#define GEOMETRY_H_ + + +#define EDGE_NONE 0 +#define EDGE_LEFT (1<<0) +#define EDGE_RIGHT (1<<1) +#define EDGE_TOP (1<<2) +#define EDGE_BOTTOM (1<<3) +#define EDGE_ALL (EDGE_LEFT|EDGE_RIGHT|EDGE_TOP|EDGE_BOTTOM) + +#define INTERSECTION_ERROR -1 +#define INTERSECTION_NONE 0 +#define INTERSECTION_IDENTICAL 1 +#define INTERSECTION_LINE_LINE 2 +#define INTERSECTION_LINE_SEGMENT 3 +#define INTERSECTION_SEGMENT_LINE 4 +#define INTERSECTION_SEGMENT_SEGMENT 5 + + +typedef struct _VERTEX { + double x, y; +} VERTEX; + +typedef struct _RECTANGLE { + double x, y, width, height; +} RECTANGLE; + +typedef struct _LINE { + VERTEX v1, v2; +} LINE; + +typedef struct _VERTEX_LIST { + unsigned int nVertices; + VERTEX *vertices; +} VERTEX_LIST, POLYGON; + + +void addVertex(VERTEX_LIST *list, VERTEX *v); +void insertVertex(VERTEX_LIST *list, VERTEX *v, unsigned int n); +void deleteVertex(VERTEX_LIST *list, unsigned int n); + + +int vertexInRect(const VERTEX *v, const RECTANGLE *rect); +int lineIntersection(const LINE *la, const LINE *lb, VERTEX *v); +int lineRectIntersection(const LINE *l, const RECTANGLE *rect, int edge, VERTEX *v); +int lineRectIntersections(const LINE *line, const RECTANGLE *rect, int edge, VERTEX *v1, VERTEX *v2); +void simplifyPolygon(const POLYGON *in, const RECTANGLE *rect, POLYGON *out); + +#endif /*GEOMETRY_H_*/ diff --git a/level.c b/level.c index 8dbe686..cb102a6 100644 --- a/level.c +++ b/level.c @@ -19,38 +19,6 @@ void deleteRoom(LEVEL *lvl, unsigned int n) { lvl->rooms = realloc(lvl->rooms, lvl->nRooms*sizeof(ROOM)); } -void addVertex(ROOM *room, VERTEX *v) { - room->nVertices++; - room->vertices = realloc(room->vertices, room->nVertices*sizeof(VERTEX)); - room->vertices[room->nVertices-1] = *v; -} - -void insertVertex(ROOM *room, VERTEX *v, unsigned int n) { - int i; - - if(n > room->nVertices) - n = room->nVertices; - - room->nVertices++; - room->vertices = realloc(room->vertices, room->nVertices*sizeof(VERTEX)); - - for(i = room->nVertices-1; i > n; i--) - room->vertices[i] = room->vertices[i-1]; - - room->vertices[n] = *v; -} - -void deleteVertex(ROOM *room, unsigned int n) { - int i; - - room->nVertices--; - - for(i = n; i < room->nVertices; i++) - room->vertices[i] = room->vertices[i+1]; - - room->vertices = realloc(room->vertices, room->nVertices*sizeof(VERTEX)); -} - void freeLevel(LEVEL *lvl) { int i; diff --git a/level.h b/level.h index db54320..afdf52e 100644 --- a/level.h +++ b/level.h @@ -1,14 +1,9 @@ #ifndef LEVEL_H_ #define LEVEL_H_ -typedef struct _VERTEX { - float x, y; -} VERTEX; +#include "geometry.h" -typedef struct _ROOM { - unsigned int nVertices; - VERTEX *vertices; -} ROOM; +typedef POLYGON ROOM; typedef struct _LEVEL { unsigned int nRooms; @@ -18,10 +13,6 @@ typedef struct _LEVEL { void addRoom(LEVEL *lvl, ROOM *room); void deleteRoom(LEVEL *lvl, unsigned int n); -void addVertex(ROOM *room, VERTEX *v); -void insertVertex(ROOM *room, VERTEX *v, unsigned int n); -void deleteVertex(ROOM *room, unsigned int n); - void freeLevel(LEVEL *lvl); #endif /*LEVEL_H_*/ -- cgit v1.2.3