1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
#include "geometry.h"
#include <math.h>
#include <stdlib.h>
#include <gtk/gtk.h>
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;
else return 0;
}
if(l->v1.getX() == l->v2.getX()) {
if(l->v1.getX() != v->getX()) return 0;
else if(v->getY() >= MIN(l->v1.getY(), l->v2.getY()) && v->getY() <= MAX(l->v1.getY(), l->v2.getY())) return 1;
else return 1;
}
if(l->v1.getY() == l->v2.getY()) {
if(l->v1.getY() != v->getY()) return 0;
else if(v->getX() >= MIN(l->v1.getX(), l->v2.getX()) && v->getX() <= MAX(l->v1.getX(), l->v2.getX())) return 1;
else return 1;
}
if((v->getX()-l->v1.getX())/(l->v2.getX()-l->v1.getX()) - (v->getY()-l->v1.getY())/(l->v2.getY()-l->v1.getY()) == 0) return 1;
else return 0;
}
int vertexInRect(const Vertex *v, const RECTANGLE *rect) {
int ret = EDGE_NONE;
if(v->getX() < rect->x) ret |= EDGE_LEFT;
else if(v->getX() >= rect->x+rect->width) ret |= EDGE_RIGHT;
if(v->getY() < rect->y) ret |= EDGE_TOP;
else if(v->getY() >= rect->y+rect->height) ret |= EDGE_BOTTOM;
return ret;
}
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 = {Vertex(minX, minY), Vertex(maxX, minY)};
const LINE bottom = {Vertex(minX, maxY), Vertex(maxX, maxY)};
const LINE left = {Vertex(minX, minY), Vertex(minX, maxY)};
const LINE right = {Vertex(maxX, minY), Vertex(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->setLocation(0, 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;
}
static void edgeVertex(Vertex *v, int edge, const RECTANGLE *rect) {
if(edge == EDGE_NONE)
edge = vertexInRect(v, rect);
if(edge & EDGE_LEFT) v->setX(rect->x);
else if(edge & EDGE_RIGHT) v->setX(rect->x+rect->width);
if(edge & EDGE_TOP) v->setY(rect->y);
else if(edge & EDGE_BOTTOM) v->setY(rect->y+rect->height);
}
static int simplifyVertex(Vertex *v, const Vertex *to, const RECTANGLE *rect) {
LINE l = {*v, *to};
int edge, edge2;
edge = vertexInRect(v, rect);
if(edge == EDGE_NONE) return EDGE_NONE;
edge2 = lineRectIntersection(&l, rect, edge, v);
if(edge2 != EDGE_NONE) return edge2;
edgeVertex(v, edge, rect);
return edge;
}
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)};
LINE l = {*v1, *v2};
Vertex v, vi;
int edge1, edge2;
v = *v1;
if((edge1 = simplifyVertex(&v, v2, rect)) != EDGE_NONE)
out->push_back(v);
v = *v2;
edge2 = simplifyVertex(&v, v1, rect);
if(edge1 != EDGE_NONE && edge2 != EDGE_NONE && !(edge1 & edge2)) {
if(lineIntersection(&l, &d1, &vi) == INTERSECTION_SEGMENT_LINE) {
edgeVertex(&vi, 0, rect);
out->push_back(vi);
}
else if(lineIntersection(&l, &d2, &vi) == INTERSECTION_SEGMENT_LINE) {
edgeVertex(&vi, 0, rect);
out->push_back(vi);
}
}
if(!last)
out->push_back(v);
}
void simplifyPolygon(const Polygon *in, const RECTANGLE *rect, Polygon *out) {
Vertex v;
if(in->empty()) return;
else if(in->size() == 1) {
out->push_back(in->front());
return;
}
v = in->front();
simplifyVertex(&v, &in->back(), rect);
out->push_back(v);
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);
}
}
|
