diff options
| -rw-r--r-- | Line.cpp | 72 | ||||
| -rw-r--r-- | Line.h | 23 | ||||
| -rw-r--r-- | Makefile.am | 2 | ||||
| -rw-r--r-- | Makefile.in | 35 | ||||
| -rw-r--r-- | Polygon.cpp | 118 | ||||
| -rw-r--r-- | Polygon.h | 19 | ||||
| -rw-r--r-- | draw.cpp | 40 | ||||
| -rw-r--r-- | edit.cpp | 109 | ||||
| -rw-r--r-- | edit.h | 4 | ||||
| -rw-r--r-- | geometry.cpp | 240 | ||||
| -rw-r--r-- | geometry.h | 32 | ||||
| -rw-r--r-- | level.cpp | 8 | ||||
| -rw-r--r-- | level.h | 3 | ||||
| -rw-r--r-- | window.cpp | 14 |
14 files changed, 378 insertions, 341 deletions
diff --git a/Line.cpp b/Line.cpp new file mode 100644 index 0000000..c755050 --- /dev/null +++ b/Line.cpp @@ -0,0 +1,72 @@ +#include "Line.h" +#include <math.h> + + +int lineIntersection(const LINE *la, const LINE *lb, Vertex *v) { + double xa1 = la->v1.getX(), ya1 = la->v1.getY(); + double xa2 = la->v2.getX(), ya2 = la->v2.getY(); + double xb1 = lb->v1.getX(), yb1 = lb->v1.getY(); + double xb2 = lb->v2.getX(), yb2 = lb->v2.getY(); + double temp; + int switched = 0; + Vertex v2; + + + if(!v) v = &v2; + + 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; + } + + if(xa1 == xa2 && xb1 == xb2) + return (xa1 == xb1) ? INTERSECTION_IDENTICAL : INTERSECTION_NONE; + + if(xa1 == xa2) { + v->setX(xa1); + v->setY(yb1); + } + else if(xb1 == xb2) { + v->setX(xb1); + v->setY(ya1); + } + else { + 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; + + v->setX((bb-ba)/(ma-mb)); + v->setY(ma*v->getX() + ba); + } + + if(switched) { + temp = v->getX(); v->setX(v->getY()); v->setY(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->getX() < fmin(xa1,xa2) || v->getX() > fmax(xa1, xa2) || v->getY() < fmin(ya1,ya2) || v->getY() > fmax(ya1, ya2)) { + if(v->getX() < fmin(xb1,xb2) || v->getX() > fmax(xb1, xb2) || v->getY() < fmin(yb1,yb2) || v->getY() > fmax(yb1, yb2)) + return INTERSECTION_LINE_LINE; + else + return INTERSECTION_LINE_SEGMENT; + } + else if(v->getX() < fmin(xb1,xb2) || v->getX() > fmax(xb1, xb2) || v->getY() < fmin(yb1,yb2) || v->getY() > fmax(yb1, yb2)) + return INTERSECTION_SEGMENT_LINE; + else + return INTERSECTION_SEGMENT_SEGMENT; +} @@ -0,0 +1,23 @@ +#ifndef LINE_H_ +#define LINE_H_ + +#include "Vertex.h" + + +#define INTERSECTION_ERROR -1 +#define INTERSECTION_NONE 0 +#define INTERSECTION_IDENTICAL 1 +#define INTERSECTION_LINE 2 +#define INTERSECTION_LINE_LINE 2 +#define INTERSECTION_LINE_SEGMENT 3 +#define INTERSECTION_SEGMENT_LINE 6 +#define INTERSECTION_SEGMENT_SEGMENT 7 + +typedef struct _LINE { + Vertex v1, v2; +} LINE; + + +int lineIntersection(const LINE *la, const LINE *lb, Vertex *v); + +#endif /*LINE_H_*/ diff --git a/Makefile.am b/Makefile.am index 1f2cd8f..b327e10 100644 --- a/Makefile.am +++ b/Makefile.am @@ -1,4 +1,4 @@ bin_PROGRAMS = zoomedit -zoomedit_SOURCES = zoomedit.cpp window.cpp ui.cpp draw.cpp level.cpp geometry.cpp edit.cpp Vertex.cpp +zoomedit_SOURCES = zoomedit.cpp window.cpp ui.cpp draw.cpp level.cpp geometry.cpp edit.cpp Vertex.cpp Line.cpp Polygon.cpp zoomedit_CPPFLAGS = @GTK_CFLAGS@ zoomedit_LDADD = @GTK_LIBS@
\ No newline at end of file diff --git a/Makefile.in b/Makefile.in index 6a054d5..d6e0969 100644 --- a/Makefile.in +++ b/Makefile.in @@ -52,7 +52,8 @@ am_zoomedit_OBJECTS = zoomedit-zoomedit.$(OBJEXT) \ zoomedit-window.$(OBJEXT) zoomedit-ui.$(OBJEXT) \ zoomedit-draw.$(OBJEXT) zoomedit-level.$(OBJEXT) \ zoomedit-geometry.$(OBJEXT) zoomedit-edit.$(OBJEXT) \ - zoomedit-Vertex.$(OBJEXT) + zoomedit-Vertex.$(OBJEXT) zoomedit-Line.$(OBJEXT) \ + zoomedit-Polygon.$(OBJEXT) zoomedit_OBJECTS = $(am_zoomedit_OBJECTS) zoomedit_DEPENDENCIES = DEFAULT_INCLUDES = -I.@am__isrc@ @@ -170,7 +171,7 @@ sysconfdir = @sysconfdir@ target_alias = @target_alias@ top_builddir = @top_builddir@ top_srcdir = @top_srcdir@ -zoomedit_SOURCES = zoomedit.cpp window.cpp ui.cpp draw.cpp level.cpp geometry.cpp edit.cpp Vertex.cpp +zoomedit_SOURCES = zoomedit.cpp window.cpp ui.cpp draw.cpp level.cpp geometry.cpp edit.cpp Vertex.cpp Line.cpp Polygon.cpp zoomedit_CPPFLAGS = @GTK_CFLAGS@ zoomedit_LDADD = @GTK_LIBS@ all: config.h @@ -261,6 +262,8 @@ mostlyclean-compile: distclean-compile: -rm -f *.tab.c +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/zoomedit-Line.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/zoomedit-Polygon.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/zoomedit-Vertex.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/zoomedit-draw.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/zoomedit-edit.Po@am__quote@ @@ -396,6 +399,34 @@ zoomedit-Vertex.obj: Vertex.cpp @AMDEP_TRUE@@am__fastdepCXX_FALSE@ DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@ @am__fastdepCXX_FALSE@ $(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(zoomedit_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -c -o zoomedit-Vertex.obj `if test -f 'Vertex.cpp'; then $(CYGPATH_W) 'Vertex.cpp'; else $(CYGPATH_W) '$(srcdir)/Vertex.cpp'; fi` +zoomedit-Line.o: Line.cpp +@am__fastdepCXX_TRUE@ $(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(zoomedit_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -MT zoomedit-Line.o -MD -MP -MF $(DEPDIR)/zoomedit-Line.Tpo -c -o zoomedit-Line.o `test -f 'Line.cpp' || echo '$(srcdir)/'`Line.cpp +@am__fastdepCXX_TRUE@ mv -f $(DEPDIR)/zoomedit-Line.Tpo $(DEPDIR)/zoomedit-Line.Po +@AMDEP_TRUE@@am__fastdepCXX_FALSE@ source='Line.cpp' object='zoomedit-Line.o' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCXX_FALSE@ DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCXX_FALSE@ $(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(zoomedit_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -c -o zoomedit-Line.o `test -f 'Line.cpp' || echo '$(srcdir)/'`Line.cpp + +zoomedit-Line.obj: Line.cpp +@am__fastdepCXX_TRUE@ $(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(zoomedit_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -MT zoomedit-Line.obj -MD -MP -MF $(DEPDIR)/zoomedit-Line.Tpo -c -o zoomedit-Line.obj `if test -f 'Line.cpp'; then $(CYGPATH_W) 'Line.cpp'; else $(CYGPATH_W) '$(srcdir)/Line.cpp'; fi` +@am__fastdepCXX_TRUE@ mv -f $(DEPDIR)/zoomedit-Line.Tpo $(DEPDIR)/zoomedit-Line.Po +@AMDEP_TRUE@@am__fastdepCXX_FALSE@ source='Line.cpp' object='zoomedit-Line.obj' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCXX_FALSE@ DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCXX_FALSE@ $(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(zoomedit_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -c -o zoomedit-Line.obj `if test -f 'Line.cpp'; then $(CYGPATH_W) 'Line.cpp'; else $(CYGPATH_W) '$(srcdir)/Line.cpp'; fi` + +zoomedit-Polygon.o: Polygon.cpp +@am__fastdepCXX_TRUE@ $(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(zoomedit_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -MT zoomedit-Polygon.o -MD -MP -MF $(DEPDIR)/zoomedit-Polygon.Tpo -c -o zoomedit-Polygon.o `test -f 'Polygon.cpp' || echo '$(srcdir)/'`Polygon.cpp +@am__fastdepCXX_TRUE@ mv -f $(DEPDIR)/zoomedit-Polygon.Tpo $(DEPDIR)/zoomedit-Polygon.Po +@AMDEP_TRUE@@am__fastdepCXX_FALSE@ source='Polygon.cpp' object='zoomedit-Polygon.o' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCXX_FALSE@ DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCXX_FALSE@ $(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(zoomedit_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -c -o zoomedit-Polygon.o `test -f 'Polygon.cpp' || echo '$(srcdir)/'`Polygon.cpp + +zoomedit-Polygon.obj: Polygon.cpp +@am__fastdepCXX_TRUE@ $(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(zoomedit_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -MT zoomedit-Polygon.obj -MD -MP -MF $(DEPDIR)/zoomedit-Polygon.Tpo -c -o zoomedit-Polygon.obj `if test -f 'Polygon.cpp'; then $(CYGPATH_W) 'Polygon.cpp'; else $(CYGPATH_W) '$(srcdir)/Polygon.cpp'; fi` +@am__fastdepCXX_TRUE@ mv -f $(DEPDIR)/zoomedit-Polygon.Tpo $(DEPDIR)/zoomedit-Polygon.Po +@AMDEP_TRUE@@am__fastdepCXX_FALSE@ source='Polygon.cpp' object='zoomedit-Polygon.obj' libtool=no @AMDEPBACKSLASH@ +@AMDEP_TRUE@@am__fastdepCXX_FALSE@ DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@ +@am__fastdepCXX_FALSE@ $(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(zoomedit_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -c -o zoomedit-Polygon.obj `if test -f 'Polygon.cpp'; then $(CYGPATH_W) 'Polygon.cpp'; else $(CYGPATH_W) '$(srcdir)/Polygon.cpp'; fi` + ID: $(HEADERS) $(SOURCES) $(LISP) $(TAGS_FILES) list='$(SOURCES) $(HEADERS) $(LISP) $(TAGS_FILES)'; \ unique=`for i in $$list; do \ diff --git a/Polygon.cpp b/Polygon.cpp new file mode 100644 index 0000000..05d06ca --- /dev/null +++ b/Polygon.cpp @@ -0,0 +1,118 @@ +#include "Polygon.h" +#include <math.h> + + +double Polygon::area() const { + double d = 0.0; + + for(const_iterator it = begin(); it != end(); it++) { + const_iterator it2 = it+1; + if(it2 == end()) it2 = begin(); + + d += (it2->getX()+it->getX())*(it2->getY()-it->getY()); + } + + return fabs(d/2); +} + +double Polygon::perimeter() const { + double d = 0.0; + + for(const_iterator it = begin(); it != end(); it++) { + const_iterator it2 = it+1; + if(it2 == end()) it2 = begin(); + + d += it->distance(*it2); + } + + return d; +} + +int Polygon::quadrant(const Vertex &v) const { + if(v.getX() > 0 && v.getY() >= 0) return 1; + if(v.getX() >= 0 && v.getY() < 0) return 2; + if(v.getX() < 0 && v.getY() <= 0) return 3; + if(v.getX() <= 0 && v.getY() > 0) return 4; + + return 0; +} + +bool Polygon::contains(const Vertex &v) const { + int d = 0; + int q, ql, q2; + LINE d1 = {Vertex(-1, -1), Vertex(1, 1)}; + LINE d2 = {Vertex(-1, 1), Vertex(1, -1)}; + LINE l; + Vertex v2; + + + if(empty()) return false; + + v2 = back() - v; + q = quadrant(v2); + + if(q == 0) return true; + + for(const_iterator it = begin(); it != end(); it++) { + ql = q; + + v2 = *it - v; + q = quadrant(v2); + + if(q == 0) return true; + + switch(q-ql) { + case 0: + break; + case 1: + case -3: + d++; + break; + case 3: + case -1: + d--; + break; + default: + l.v1 = ((it == begin()) ? back() : *(it-1)) - v; + l.v2 = v2; + + if(q == 1 || q == 3) { + if(!(lineIntersection(&l, &d2, &v2) & INTERSECTION_LINE)) return false; + + q2 = quadrant(v2); + if(q2 == 0) return true; + + if((q == 1 && q2 == 2) || (q == 3 && q2 == 4)) d -= 2; + else d += 2; + } + else { + if(!(lineIntersection(&l, &d1, &v2) & INTERSECTION_LINE)) return false; + + q2 = quadrant(v2); + if(q2 == 0) return true; + + if((q == 2 && q2 == 3) || (q == 4 && q2 == 1)) d -= 2; + else d += 2; + } + } + } + + return (d != 0); +} + +bool Polygon::intersects(const LINE *l) const { + LINE line; + + for(Polygon::const_iterator it = begin(); it != end(); it++) { + Polygon::const_iterator it2 = it+1; + if(it2 == end()) it2 = begin(); + + line.v1 = *it; + line.v2 = *it2; + + if(lineIntersection(l, &line, NULL) == INTERSECTION_SEGMENT_SEGMENT) + return true; + } + + return false; +} diff --git a/Polygon.h b/Polygon.h new file mode 100644 index 0000000..2a79a94 --- /dev/null +++ b/Polygon.h @@ -0,0 +1,19 @@ +#ifndef POLYGON_H_ +#define POLYGON_H_ + +#include "Vertex.h" +#include "Line.h" +#include <vector> + +class Polygon : public std::vector<Vertex> { + private: + int quadrant(const Vertex &v) const; + public: + double area() const; + double perimeter() const; + + bool contains(const Vertex &v) const; + bool intersects(const LINE *l) const; +}; + +#endif /*POLYGON_H_*/ @@ -68,31 +68,27 @@ static void drawGrid(cairo_t *cr, const RECTANGLE *rect) { } } -static void polygon2path(cairo_t *cr, const POLYGON *polygon, const RECTANGLE *rect, gboolean close) { - int i; - POLYGON polygon2 = {0, NULL}; +static void polygon2path(cairo_t *cr, const Polygon *polygon, const RECTANGLE *rect, gboolean close) { + Polygon polygon2; // no vertices - if(polygon->nVertices == 0) return; + if(polygon->empty()) return; if(rect) simplifyPolygon(polygon, rect, &polygon2); else polygon2 = *polygon; - if(polygon2.nVertices == 0) return; + if(polygon2.empty()) return; cairo_new_sub_path(cr); - for(i = 0; i < polygon2.nVertices; i++) { - cairo_line_to(cr, polygon2.vertices[i].getX(), polygon2.vertices[i].getY()); + for(Polygon::iterator it = polygon2.begin(); it != polygon2.end(); it++) { + cairo_line_to(cr, it->getX(), it->getY()); } if(close) cairo_close_path(cr); - - if(rect && polygon2.vertices) - free(polygon2.vertices); } gboolean drawTopView(GtkWidget *widget, GdkEventExpose *event, gpointer data) { @@ -201,7 +197,7 @@ gboolean drawTopView(GtkWidget *widget, GdkEventExpose *event, gpointer data) { cairo_fill_preserve(cr); - if(getActiveRoom()->polygon.nVertices && getHoveredVertex()) { + if(!getActiveRoom()->polygon.empty() && getHoveredVertex()) { vertexOk = isVertexOk(getHoveredVertex()); if(vertexOk) @@ -214,11 +210,10 @@ gboolean drawTopView(GtkWidget *widget, GdkEventExpose *event, gpointer data) { cairo_set_source_rgba(cr, 0.0, 0.7, 1.0, 0.7); cairo_stroke(cr); - if(getActiveRoom()->polygon.nVertices && getHoveredVertex() && !vertexOk) { + if(!getActiveRoom()->polygon.empty() && getHoveredVertex() && !vertexOk) { cairo_set_source_rgba(cr, 1.0, 0.3, 0.3, 0.7); - i = getActiveRoom()->polygon.nVertices - 1; - cairo_move_to(cr, getActiveRoom()->polygon.vertices[i].getX(), getActiveRoom()->polygon.vertices[i].getY()); + cairo_move_to(cr, getActiveRoom()->polygon.back().getX(), getActiveRoom()->polygon.back().getY()); cairo_line_to(cr, getHoveredVertex()->getX(), getHoveredVertex()->getY()); cairo_stroke(cr); @@ -253,13 +248,14 @@ void viewToImage(Vertex *v) { double getImageWidth() { const LEVEL *level = getLevel(); double min = 0.0, max = 0.0; - int i, j; + int i; + if(level) { for(i = 0; i < level->nRooms; i++) { - for(j = 0; j < level->rooms[i].polygon.nVertices; j++) { - min = MIN(min, level->rooms[i].polygon.vertices[j].getX()); - max = MAX(max, level->rooms[i].polygon.vertices[j].getX()); + for(Polygon::iterator it = level->rooms[i].polygon.begin(); it != level->rooms[i].polygon.end(); it++) { + min = MIN(min, it->getX()); + max = MAX(max, it->getX()); } } } @@ -270,13 +266,13 @@ double getImageWidth() { double getImageHeight() { const LEVEL *level = getLevel(); double min = 0.0, max = 0.0; - int i, j; + int i; if(level) { for(i = 0; i < level->nRooms; i++) { - for(j = 0; j < level->rooms[i].polygon.nVertices; j++) { - min = MIN(min, level->rooms[i].polygon.vertices[j].getY()); - max = MAX(max, level->rooms[i].polygon.vertices[j].getY()); + for(Polygon::iterator it = level->rooms[i].polygon.begin(); it != level->rooms[i].polygon.end(); it++) { + min = MIN(min, it->getY()); + max = MAX(max, it->getY()); } } } @@ -1,7 +1,6 @@ #include "edit.h" #include "level.h" #include "geometry.h" -#include <stdlib.h> static int editMode = EDIT_MODE_VIEW; @@ -48,9 +47,9 @@ void setHoveredVertex(Vertex *v) { hoveredRoom = NULL; for(i = 0; i < l->nRooms; i++) { - if(vertexInPolygon(v, &l->rooms[i].polygon)) { - //hoveredRoom = &l->rooms[i]; - //break; + if(l->rooms[i].polygon.contains(*v)) { + hoveredRoom = &l->rooms[i]; + break; } } } @@ -62,8 +61,7 @@ void setHoveredVertex(Vertex *v) { void startAddMode() { activeRoom = (ROOM*)calloc(1, sizeof(ROOM)); - activeRoom->polygon.nVertices = 0; - activeRoom->polygon.vertices = NULL; + activeRoom->polygon = Polygon(); activeRoom->name = (char*)calloc(1, sizeof(unsigned char)); editMode = EDIT_MODE_ADD; @@ -77,94 +75,101 @@ ROOM *getHoveredRoom() { return hoveredRoom; } -static int isLineOk(LINE *l) { +static bool isLineOk(LINE *l) { LEVEL *lvl = getLevel(); LINE l2; - int i; if(activeRoom) { - for(i = 0; i+2 < activeRoom->polygon.nVertices; i++) { - l2.v1 = activeRoom->polygon.vertices[i]; - l2.v2 = activeRoom->polygon.vertices[i+1]; + for(int i = 0; i+2 < activeRoom->polygon.size(); i++) { + l2.v1 = activeRoom->polygon[i]; + l2.v2 = activeRoom->polygon[i+1]; - if(lineIntersection(l, &l2, NULL) == INTERSECTION_SEGMENT_SEGMENT) return 0; + if(lineIntersection(l, &l2, NULL) == INTERSECTION_SEGMENT_SEGMENT) return false; } - if(activeRoom->polygon.nVertices > 1) { - l2.v1 = activeRoom->polygon.vertices[activeRoom->polygon.nVertices-2]; - l2.v2 = activeRoom->polygon.vertices[activeRoom->polygon.nVertices-1]; - if(vertexOnLine(&l->v2, &l2)) return 0; + if(activeRoom->polygon.size() > 1) { + l2.v1 = activeRoom->polygon[activeRoom->polygon.size()-2]; + l2.v2 = activeRoom->polygon.back(); + if(vertexOnLine(&l->v2, &l2)) return false; } } - for(i = 0; i < lvl->nRooms; i++) { - if(linePolygonIntersection(l, &lvl->rooms[i].polygon)) - return 0; + for(int i = 0; i < lvl->nRooms; i++) { + if(lvl->rooms[i].polygon.intersects(l)) + return false; } - return 1; + return true; } -int isVertexOk(Vertex *v) { +bool isVertexOk(Vertex *v) { LEVEL *lvl = getLevel(); LINE l; int i; + for(i = 0; i < lvl->nRooms; i++) { - if(vertexInPolygon(v, &lvl->rooms[i].polygon)) return 0; + if(lvl->rooms[i].polygon.contains(*v)) return false; } - if(!(getActiveRoom() && getActiveRoom()->polygon.nVertices)) - return 1; + if(!(getActiveRoom() && !getActiveRoom()->polygon.empty())) + return true; - l.v1 = getActiveRoom()->polygon.vertices[getActiveRoom()->polygon.nVertices-1]; + l.v1 = getActiveRoom()->polygon.back(); l.v2 = *v; - + return isLineOk(&l); } -int isPolygonOk(POLYGON *polygon) { +bool isPolygonOk(Polygon *polygon) { LEVEL *lvl = getLevel(); LINE l, l2; - int i, j; - if(!polygon->nVertices) return 0; + if(polygon->empty()) return false; - for(i = 0; i < lvl->nRooms; i++) { - if(!lvl->rooms[i].polygon.nVertices) continue; + for(int i = 0; i < lvl->nRooms; i++) { + if(lvl->rooms[i].polygon.empty()) continue; - if(vertexInPolygon(&polygon->vertices[0], &lvl->rooms[i].polygon)) - return 0; + if(lvl->rooms[i].polygon.contains(polygon->front())); + return false; - if(vertexInPolygon(&lvl->rooms[i].polygon.vertices[0], polygon)) - return 0; + if(polygon->contains(lvl->rooms[i].polygon.front())); + return false; } - if(polygon->nVertices == 1) - return 1; + if(polygon->size() == 1) + return true; - for(i = 0; i < polygon->nVertices; i++) { - l.v1 = polygon->vertices[i]; - l.v2 = polygon->vertices[(i+1)%polygon->nVertices]; + for(Polygon::const_iterator it = polygon->begin(); it != polygon->end(); it++) { + Polygon::const_iterator it2 = it+1; + if(it2 == polygon->end()) it2 = polygon->begin(); + + l.v1 = *it; + l.v2 = *it2; - for(j = 0; j < lvl->nRooms; j++) { - if(linePolygonIntersection(&l, &lvl->rooms[j].polygon)) - return 0; + for(int i = 0; i < lvl->nRooms; i++) { + if(lvl->rooms[i].polygon.intersects(&l)) + return false; } - for(j = i+2; j < polygon->nVertices; j++) { - if(i == 0 && j == polygon->nVertices-1) continue; - - l2.v1 = polygon->vertices[j]; - l2.v2 = polygon->vertices[(j+1)%polygon->nVertices]; - - if(lineIntersection(&l, &l2, NULL) == INTERSECTION_SEGMENT_SEGMENT) - return 0; + if(it2 != polygon->begin()) { + for(Polygon::const_iterator it3 = it2+1; it3 != polygon->end(); it3++) { + Polygon::const_iterator it4 = it3+1; + if(it4 == polygon->end()) it4 = polygon->begin(); + + if(it == polygon->begin() && it4 == polygon->begin()) continue; + + l2.v1 = *it3; + l2.v2 = *it4; + + if(lineIntersection(&l, &l2, NULL) == INTERSECTION_SEGMENT_SEGMENT) + return false; + } } } - return 1; + return true; } @@ -21,7 +21,7 @@ ROOM *getHoveredRoom(); Vertex *getHoveredVertex(); void setHoveredVertex(Vertex *v); -int isVertexOk(Vertex *v); -int isPolygonOk(POLYGON *polygon); +bool isVertexOk(Vertex *v); +bool isPolygonOk(Polygon *polygon); #endif /*EDIT_H_*/ diff --git a/geometry.cpp b/geometry.cpp index e709fb8..e3adb6b 100644 --- a/geometry.cpp +++ b/geometry.cpp @@ -4,39 +4,6 @@ #include <gtk/gtk.h> -void addVertex(VERTEX_LIST *list, const Vertex *v) { - list->nVertices++; - list->vertices = (Vertex*)realloc(list->vertices, list->nVertices*sizeof(Vertex)); - list->vertices[list->nVertices-1] = *v; -} - -void insertVertex(VERTEX_LIST *list, const Vertex *v, unsigned int n) { - int i; - - if(n > list->nVertices) - n = list->nVertices; - - list->nVertices++; - list->vertices = (Vertex*)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 = (Vertex*)realloc(list->vertices, list->nVertices*sizeof(Vertex)); -} - - int vertexOnLine(const Vertex *v, const LINE *l) { if(l->v1.getX() == l->v2.getX() && l->v1.getY() == l->v2.getY()) { if(l->v1.getX() == v->getX() && l->v1.getY() == v->getY()) return 1; @@ -70,166 +37,6 @@ int vertexInRect(const Vertex *v, const RECTANGLE *rect) { return ret; } -static int quadrant(Vertex *v) { - if(v->getX() > 0 && v->getY() >= 0) return 1; - if(v->getX() >= 0 && v->getY() < 0) return 2; - if(v->getX() < 0 && v->getY() <= 0) return 3; - if(v->getX() <= 0 && v->getY() > 0) return 4; - - return 0; -} - -gboolean vertexInPolygon(const Vertex *v, const POLYGON *p) { - int d = 0, i, li; - int q, ql, q2; - LINE d1 = {Vertex(-1, -1), Vertex(1, 1)}; - LINE d2 = {Vertex(-1, 1), Vertex(1, -1)}; - LINE l; - Vertex v2; - - - if(p->nVertices == 0) return FALSE; - - v2 = p->vertices[p->nVertices-1] - *v; - q = quadrant(&v2); - - if(q == 0) return TRUE; - - for(i = 0; i < p->nVertices; i++) { - ql = q; - - - v2 = p->vertices[i] - *v; - - if(q == 0) return TRUE; - - switch(q-ql) { - case 0: - break; - case 1: - case -3: - d++; - break; - case 3: - case -1: - d--; - break; - default: - l.v1 = p->vertices[(i>0)?i-1:p->nVertices-1] - *v; - l.v2 = v2; - - if(q == 1 || q == 3) { - if(!(lineIntersection(&l, &d2, &v2) & INTERSECTION_LINE)) return FALSE; - - q2 = quadrant(&v2); - if(q2 == 0) return TRUE; - - if((q == 1 && q2 == 2) || (q == 3 && q2 == 4)) d -= 2; - else d += 2; - } - else { - if(!(lineIntersection(&l, &d1, &v2) & INTERSECTION_LINE)) return FALSE; - - q2 = quadrant(&v2); - if(q2 == 0) return TRUE; - - if((q == 2 && q2 == 3) || (q == 4 && q2 == 1)) d -= 2; - else d += 2; - } - } - } - - return (d == 0) ? FALSE : TRUE; -} - -double polygonPerimeter(const POLYGON *p) { - int i; - double d = 0.0; - - for(i = 0; i < p->nVertices; i++) - d += p->vertices[i].distance(p->vertices[(i+1)%p->nVertices]); - - return d; -} - -double polygonArea(const POLYGON *p) { - int i; - double d = 0.0; - - for(i = 0; i < p->nVertices; i++) - d += (p->vertices[(i+1)%p->nVertices].getX()+p->vertices[i].getX())*(p->vertices[(i+1)%p->nVertices].getY()-p->vertices[i].getY()); - - return fabs(d/2); -} - -int lineIntersection(const LINE *la, const LINE *lb, Vertex *v) { - double xa1 = la->v1.getX(), ya1 = la->v1.getY(); - double xa2 = la->v2.getX(), ya2 = la->v2.getY(); - double xb1 = lb->v1.getX(), yb1 = lb->v1.getY(); - double xb2 = lb->v2.getX(), yb2 = lb->v2.getY(); - double temp; - int switched = 0; - Vertex v2; - - - if(v == NULL) v = &v2; - - 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; - } - - if(xa1 == xa2 && xb1 == xb2) - return (xa1 == xb1) ? INTERSECTION_IDENTICAL : INTERSECTION_NONE; - - if(xa1 == xa2) { - v->setX(xa1); - v->setY(yb1); - } - else if(xb1 == xb2) { - v->setX(xb1); - v->setY(ya1); - } - else { - 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; - - v->setX((bb-ba)/(ma-mb)); - v->setY(ma*v->getX() + ba); - } - - if(switched) { - temp = v->getX(); v->setX(v->getY()); v->setY(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->getX() < MIN(xa1,xa2) || v->getX() > MAX(xa1, xa2) || v->getY() < MIN(ya1,ya2) || v->getY() > MAX(ya1, ya2)) { - if(v->getX() < MIN(xb1,xb2) || v->getX() > MAX(xb1, xb2) || v->getY() < MIN(yb1,yb2) || v->getY() > MAX(yb1, yb2)) - return INTERSECTION_LINE_LINE; - else - return INTERSECTION_LINE_SEGMENT; - } - else if(v->getX() < MIN(xb1,xb2) || v->getX() > MAX(xb1, xb2) || v->getY() < MIN(yb1,yb2) || v->getY() > 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; @@ -262,21 +69,6 @@ int lineRectIntersections(const LINE *line, const RECTANGLE *rect, int edge, Ver return ret; } -gboolean linePolygonIntersection(const LINE *l, const POLYGON *p) { - int i; - LINE line; - - for(i = 0; i < p->nVertices; i++) { - line.v1 = p->vertices[i]; - line.v2 = p->vertices[(i+1)%p->nVertices]; - - if(lineIntersection(l, &line, NULL) == INTERSECTION_SEGMENT_SEGMENT) - return TRUE; - } - - return FALSE; -} - static void edgeVertex(Vertex *v, int edge, const RECTANGLE *rect) { if(edge == EDGE_NONE) @@ -306,7 +98,7 @@ static int simplifyVertex(Vertex *v, const Vertex *to, const RECTANGLE *rect) { -static void addSimplifiedLine(const Vertex *v1, const Vertex *v2, const RECTANGLE *rect, int last, POLYGON *out) { +static void addSimplifiedLine(const Vertex *v1, const Vertex *v2, const RECTANGLE *rect, int last, Polygon *out) { const LINE d1 = {Vertex(rect->x, rect->y), Vertex(rect->x+rect->width, rect->y+rect->height)}; const LINE d2 = {Vertex(rect->x, rect->y+rect->height), Vertex(rect->x+rect->width, rect->y)}; @@ -317,7 +109,7 @@ static void addSimplifiedLine(const Vertex *v1, const Vertex *v2, const RECTANGL v = *v1; if((edge1 = simplifyVertex(&v, v2, rect)) != EDGE_NONE) - addVertex(out, &v); + out->push_back(v); v = *v2; edge2 = simplifyVertex(&v, v1, rect); @@ -325,33 +117,35 @@ static void addSimplifiedLine(const Vertex *v1, const Vertex *v2, const RECTANGL if(edge1 != EDGE_NONE && edge2 != EDGE_NONE && !(edge1 & edge2)) { if(lineIntersection(&l, &d1, &vi) == INTERSECTION_SEGMENT_LINE) { edgeVertex(&vi, 0, rect); - addVertex(out, &vi); + out->push_back(vi); } else if(lineIntersection(&l, &d2, &vi) == INTERSECTION_SEGMENT_LINE) { edgeVertex(&vi, 0, rect); - addVertex(out, &vi); + out->push_back(vi); } } if(!last) - addVertex(out, &v); + out->push_back(v); } -void simplifyPolygon(const POLYGON *in, const RECTANGLE *rect, POLYGON *out) { +void simplifyPolygon(const Polygon *in, const RECTANGLE *rect, Polygon *out) { Vertex v; - int i; - if(in->nVertices == 0) return; - else if(in->nVertices == 1) { - addVertex(out, &in->vertices[0]); + if(in->empty()) return; + else if(in->size() == 1) { + out->push_back(in->front()); return; } - v = in->vertices[0]; - simplifyVertex(&v, &in->vertices[in->nVertices-1], rect); - addVertex(out, &v); + v = in->front(); + simplifyVertex(&v, &in->back(), rect); + out->push_back(v); - for(i = 0; i < in->nVertices; i++) { - addSimplifiedLine(&in->vertices[i], &in->vertices[(i+1)%in->nVertices], rect, (i == in->nVertices-1), out); + for(Polygon::const_iterator it = in->begin(); it != in->end(); it++) { + Polygon::const_iterator it2 = it+1; + if(it2 == in->end()) it2 = in->begin(); + + addSimplifiedLine(&*it, &*it2, rect, (it2 == in->begin()), out); } } @@ -3,6 +3,8 @@ #include "Vertex.h" +#include "Polygon.h" +#include "Line.h" #include <glib.h> #define EDGE_NONE 0 @@ -12,45 +14,21 @@ #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 2 -#define INTERSECTION_LINE_LINE 2 -#define INTERSECTION_LINE_SEGMENT 3 -#define INTERSECTION_SEGMENT_LINE 6 -#define INTERSECTION_SEGMENT_SEGMENT 7 + 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, const Vertex *v); -void insertVertex(VERTEX_LIST *list, const Vertex *v, unsigned int n); -void deleteVertex(VERTEX_LIST *list, unsigned int n); int vertexOnLine(const Vertex *v, const LINE *l); int vertexInRect(const Vertex *v, const RECTANGLE *rect); -gboolean vertexInPolygon(const Vertex *v, const POLYGON *p); -double polygonPerimeter(const POLYGON *p); -double polygonArea(const POLYGON *p); -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); -gboolean linePolygonIntersection(const LINE *l, const POLYGON *p); -void simplifyPolygon(const POLYGON *in, const RECTANGLE *rect, POLYGON *out); +//gboolean linePolygonIntersection(const LINE *l, const POLYGON *p); +void simplifyPolygon(const Polygon *in, const RECTANGLE *rect, Polygon *out); #endif /*GEOMETRY_H_*/ @@ -15,7 +15,10 @@ void setLevel(LEVEL *l) { void addRoom(LEVEL *lvl, const ROOM *room) { lvl->nRooms++; - lvl->rooms = (ROOM*)realloc(lvl->rooms, lvl->nRooms*sizeof(ROOM)); + if(lvl->nRooms > 1) + lvl->rooms = (ROOM*)realloc(lvl->rooms, lvl->nRooms*sizeof(ROOM)); + else + lvl->rooms = (ROOM*)calloc(1, sizeof(ROOM)); lvl->rooms[lvl->nRooms-1] = *room; } @@ -36,9 +39,6 @@ void freeLevel(LEVEL *lvl) { if(lvl) { if(lvl->rooms) { for(i = 0; i < lvl->nRooms; i++) { - if(lvl->rooms[i].polygon.vertices) - free(lvl->rooms[i].polygon.vertices); - if(lvl->rooms[i].name) free(lvl->rooms[i].name); } @@ -2,9 +2,10 @@ #define LEVEL_H_ #include "geometry.h" +#include "Polygon.h" typedef struct _ROOM { - POLYGON polygon; + Polygon polygon; char *name; } ROOM; @@ -52,7 +52,7 @@ static gboolean buttonEvent(GtkWidget *widget, GdkEventButton *event, gpointer u viewToImage(&v); if(isVertexOk(&v)) { - addVertex(&getActiveRoom()->polygon, &v); + getActiveRoom()->polygon.push_back(v); updateSidebar(); } } @@ -68,10 +68,11 @@ gboolean crossingNotifyEvent(GtkWidget *widget, GdkEventCrossing *event, gpointe Vertex v(event->x, event->y); + switch(event->type) { case GDK_ENTER_NOTIFY: viewToImage(&v); - + setHoveredVertex(&v); break; @@ -87,7 +88,6 @@ gboolean motionNotifyEvent(GtkWidget *widget, GdkEventMotion *event, gpointer us Vertex v(event->x, event->y); ROOM *last = getHoveredRoom(); - viewToImage(&v); setHoveredVertex(&v); @@ -165,7 +165,7 @@ static void sidebarButtonClicked(GtkButton *button, gpointer user_data) { gtk_widget_queue_draw(drawingArea); } else if(button == GTK_BUTTON(buttonAddDo)) { - if(getActiveRoom() &&getActiveRoom()->polygon.nVertices > 2 && isPolygonOk(&getActiveRoom()->polygon)) { + if(getActiveRoom() && getActiveRoom()->polygon.size() > 2 && isPolygonOk(&getActiveRoom()->polygon)) { addRoom(getLevel(), getActiveRoom()); setActiveRoom(&getLevel()->rooms[getLevel()->nRooms-1]); } @@ -313,11 +313,11 @@ void updateSidebar() { gtk_entry_set_text(GTK_ENTRY(entryName), getActiveRoom()->name); gtk_widget_set_sensitive(entryName, TRUE); - string = g_strdup_printf("%.2f", polygonArea(&getActiveRoom()->polygon)); + string = g_strdup_printf("%.2f", getActiveRoom()->polygon.area()); gtk_label_set_text(GTK_LABEL(labelArea), string); g_free(string); - string = g_strdup_printf("%.2f", polygonPerimeter(&getActiveRoom()->polygon)); + string = g_strdup_printf("%.2f", getActiveRoom()->polygon.perimeter()); gtk_label_set_text(GTK_LABEL(labelPerimeter), string); g_free(string); } @@ -335,7 +335,7 @@ void updateSidebar() { gtk_widget_show(sidebarAdd); if(getActiveRoom()) { - if(getActiveRoom()->polygon.nVertices > 2 && isPolygonOk(&getActiveRoom()->polygon)) + if(getActiveRoom()->polygon.size() > 2 && isPolygonOk(&getActiveRoom()->polygon)) gtk_widget_set_sensitive(buttonAddDo, TRUE); else gtk_widget_set_sensitive(buttonAddDo, FALSE); |