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
|
#include "shape.h"
#ifdef DMALLOC
#include "dmalloc.h"
#endif
#ifndef min
#define min(A,B) ((A) < (B) ? (A) : (B))
#define max(A,B) ((A) > (B) ? (A) : (B))
#endif
#define NOT(x) (!(x))
#ifndef FALSE
#define FALSE 0
#define TRUE (NOT(FALSE))
#endif
ilrect_t il_get_bounding_rect(ilshape_t *shape)
{
ilrect_t rc;
switch (shape->type)
{
case IL_SPLINEGON:
case IL_POLYGON: {
int i;
ilcoord_t pt = shape->def.curve.p[0];
rc.ll.x = pt.x; rc.ll.y = pt.y;
rc.ur.x = pt.x; rc.ur.y = pt.y;
for (i=1; i<shape->def.curve.n; i++)
{
pt = shape->def.curve.p[i];
rc.ll.x = min (rc.ll.x, pt.x);
rc.ur.x = max (rc.ur.x, pt.x);
rc.ll.y = min (rc.ll.y, pt.y);
rc.ur.y = max (rc.ur.y, pt.y);
}
}
return rc;
case IL_CIRCLE:
case IL_ELLIPSE:rc.ll.x = - shape->def.ellipse.radius_a;
rc.ur.x = shape->def.ellipse.radius_a;
rc.ll.y = - shape->def.ellipse.radius_b;
rc.ur.y = shape->def.ellipse.radius_b;
return rc;
default: rc.ll.x = rc.ll.y = rc.ur.x = rc.ur.y = 0.0;
return rc;
}
}
static int same_side(ilcoord_t p0, ilcoord_t p1, ilcoord_t L0, ilcoord_t L1)
{
int s0,s1;
double a,b,c;
/* a x + b y = c */
a = -(L1.y - L0.y);
b = (L1.x - L0.x);
c = a * L0.x + b * L0.y;
s0 = (a*p0.x + b*p0.y - c >= 0);
s1 = (a*p1.x + b*p1.y - c >= 0);
return (s0 == s1);
}
static int point_in_poly(ilcoord_t P, ilshape_t *shape)
{
static int last; /* hint for converging on a given side of a poly */
static ilcoord_t O; /* origin */
int i, i1, j, sides, s;
ilcoord_t Q, R, *vertex;
assert (shape->type == IL_POLYGON);
sides = shape->def.curve.n;
vertex = shape->def.curve.p;
i = last % sides; /*in case last is left over from larger polygon*/
i1 = (i + 1) % sides;
Q = vertex[i];
R = vertex[i1];
if (NOT(same_side(P,O,Q,R))) return FALSE;
if ((s = same_side(P,Q,R,O)) && (same_side(P,R,O,Q))) return TRUE;
for (j = 1; j < sides; j++) {
if (s) {
i = i1; i1 = (i + 1) % sides;
}
else {
i1 = i; i = (i + sides - 1) % sides;
}
if (NOT(same_side(P,O,vertex[i],vertex[i1]))) {
last = i;
return FALSE;
}
}
last = i; /* in case next call is near the same side */
return TRUE;
}
static double CalcDistSquared (ilcoord_t pt)
{ return ((pt.x * pt.x) + (pt.y * pt.y)); }
int il_inshape(ilshape_t *shape, ilcoord_t pt) /* 0,1 predicate */
{
switch (shape->type)
{
case IL_CIRCLE: return CalcDistSquared(pt) <= (shape->def.ellipse.radius_a)*(shape->def.ellipse.radius_a);
case IL_ELLIPSE: if (shape->def.ellipse.radius_a > shape->def.ellipse.radius_b)
{
pt.y *= shape->def.ellipse.radius_a/shape->def.ellipse.radius_b;
return CalcDistSquared(pt) <= (shape->def.ellipse.radius_a)*(shape->def.ellipse.radius_a);
}
else if (shape->def.ellipse.radius_a < shape->def.ellipse.radius_b)
{
pt.x *= shape->def.ellipse.radius_b/shape->def.ellipse.radius_a;
return CalcDistSquared(pt) <= (shape->def.ellipse.radius_b)*(shape->def.ellipse.radius_b);
}
else return CalcDistSquared(pt) <= (shape->def.ellipse.radius_a)*(shape->def.ellipse.radius_a);
case IL_POLYGON:
return point_in_poly(pt,shape);
default: return 0;
}
}
ilcoord_t ilcoord(double x, double y)
{
ilcoord_t rv;
rv.x = x; rv.y = y;
return rv;
}
|
