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
|
#include "geometry.h"
static void edgeVertex(Vertex *v, int edge, const Rectangle *rect) {
if(edge == EDGE_NONE)
edge = rect->edges(*v);
if(edge & EDGE_LEFT) v->setX(rect->getVertex1().getX());
else if(edge & EDGE_RIGHT) v->setX(rect->getVertex2().getX());
if(edge & EDGE_TOP) v->setY(rect->getVertex1().getY());
else if(edge & EDGE_BOTTOM) v->setY(rect->getVertex2().getY());
}
static int simplifyVertex(Vertex *v, const Vertex *to, const Rectangle *rect) {
Line l(*v, *to);
int edge, edge2;
edge = rect->edges(*v);
if(edge == EDGE_NONE) return EDGE_NONE;
edge2 = rect->intersects(l, v, edge);
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(rect->getVertex1(), rect->getVertex2());
const Line d2(rect->getVertex1().getX(), rect->getVertex2().getY(), rect->getVertex2().getX(), rect->getVertex1().getY());
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(l.intersects(d1, &vi) == INTERSECTION_SEGMENT_LINE) {
edgeVertex(&vi, 0, rect);
out->push_back(vi);
}
else if(l.intersects(d1, &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);
}
}
|
