Root/
Source at commit fa98e58157b6f68396d302c32421e882ac87f45b created 6 years 10 months ago. By Werner Almesberger, fped.c (usage): fix typo "heigth" | |
---|---|
1 | /* |
2 | * overlap.c - Test for overlaps |
3 | * |
4 | * Written 2009, 2010 by Werner Almesberger |
5 | * Copyright 2009, 2010 by Werner Almesberger |
6 | * |
7 | * This program is free software; you can redistribute it and/or modify |
8 | * it under the terms of the GNU General Public License as published by |
9 | * the Free Software Foundation; either version 2 of the License, or |
10 | * (at your option) any later version. |
11 | */ |
12 | |
13 | |
14 | #include <stdlib.h> |
15 | |
16 | #include "coord.h" |
17 | #include "obj.h" |
18 | #include "inst.h" |
19 | #include "overlap.h" |
20 | |
21 | |
22 | /* |
23 | * @@@ result may be too optimistic if "b" is a rounded pad |
24 | */ |
25 | |
26 | int inside(const struct inst *a, const struct inst *b) |
27 | { |
28 | struct coord min_a, max_a; |
29 | struct coord min_b, max_b; |
30 | |
31 | min_a = a->base; |
32 | switch (a->obj->type) { |
33 | case ot_pad: |
34 | max_a = a->u.pad.other; |
35 | break; |
36 | case ot_hole: |
37 | max_a = a->u.hole.other; |
38 | break; |
39 | default: |
40 | abort(); |
41 | } |
42 | sort_coord(&min_a, &max_a); |
43 | |
44 | min_b = b->base; |
45 | switch (b->obj->type) { |
46 | case ot_pad: |
47 | max_b = b->u.pad.other; |
48 | break; |
49 | case ot_hole: |
50 | max_b = b->u.hole.other; |
51 | break; |
52 | default: |
53 | abort(); |
54 | } |
55 | sort_coord(&min_b, &max_b); |
56 | |
57 | return min_a.x >= min_b.x && max_a.x <= max_b.x && |
58 | min_a.y >= min_b.y && max_a.y <= max_b.y; |
59 | } |
60 | |
61 | |
62 | /* ----- Overlap test for primitives --------------------------------------- */ |
63 | |
64 | |
65 | struct shape { |
66 | int circle; |
67 | struct coord center; |
68 | unit_type r; |
69 | struct coord min, max; |
70 | }; |
71 | |
72 | |
73 | static int circle_circle_overlap(struct coord c1, unit_type r1, |
74 | struct coord c2, unit_type r2, enum allow_overlap allow) |
75 | { |
76 | if (allow == ao_touch) |
77 | return dist_point(c1, c2) < r1+r2; |
78 | return dist_point(c1, c2) <= r1+r2; |
79 | } |
80 | |
81 | |
82 | static int circle_rect_overlap(struct coord c, unit_type r, |
83 | struct coord min, struct coord max, enum allow_overlap allow) |
84 | { |
85 | if (allow == ao_touch) { |
86 | if (c.x <= min.x-r || c.x >= max.x+r) |
87 | return 0; |
88 | if (c.y <= min.y-r || c.y >= max.y+r) |
89 | return 0; |
90 | } |
91 | if (c.x < min.x-r || c.x > max.x+r) |
92 | return 0; |
93 | if (c.y < min.y-r || c.y > max.y+r) |
94 | return 0; |
95 | return 1; |
96 | } |
97 | |
98 | |
99 | static int rect_rect_overlap(struct coord min1, struct coord max1, |
100 | struct coord min2, struct coord max2, enum allow_overlap allow) |
101 | { |
102 | if (allow == ao_touch) { |
103 | if (max1.x <= min2.x || max2.x <= min1.x) |
104 | return 0; |
105 | if (max1.y <= min2.y || max2.y <= min1.y) |
106 | return 0; |
107 | } |
108 | if (max1.x < min2.x || max2.x < min1.x) |
109 | return 0; |
110 | if (max1.y < min2.y || max2.y < min1.y) |
111 | return 0; |
112 | return 1; |
113 | } |
114 | |
115 | |
116 | static int shapes_overlap(const struct shape *a, const struct shape *b, |
117 | enum allow_overlap allow) |
118 | { |
119 | if (a->circle && !b->circle) |
120 | return shapes_overlap(b, a, allow); |
121 | if (a->circle) /* b must be circle, too */ |
122 | return circle_circle_overlap(a->center, a->r, b->center, b->r, |
123 | allow); |
124 | if (b->circle) /* a must be rect */ |
125 | return circle_rect_overlap(b->center, b->r, a->min, a->max, |
126 | allow); |
127 | return rect_rect_overlap(a->min, a->max, b->min, b->max, allow); |
128 | } |
129 | |
130 | |
131 | /* ----- Recursive overlap tester ------------------------------------------ */ |
132 | |
133 | |
134 | static int test_overlap(const struct inst *a, const struct inst *b, |
135 | const struct shape *other, enum allow_overlap allow); |
136 | |
137 | |
138 | static int do_circle(const struct inst *next, const struct shape *other, |
139 | unit_type x, unit_type y, unit_type r, enum allow_overlap allow) |
140 | { |
141 | struct shape shape = { |
142 | .circle = 1, |
143 | .center = { |
144 | .x = x, |
145 | .y = y, |
146 | }, |
147 | .r = r, |
148 | }; |
149 | |
150 | if (next) |
151 | return test_overlap(next, NULL, &shape, allow); |
152 | return shapes_overlap(other, &shape, allow); |
153 | } |
154 | |
155 | |
156 | static int do_rect(const struct inst *next, const struct shape *other, |
157 | unit_type x, unit_type y, unit_type w, unit_type h, |
158 | enum allow_overlap allow) |
159 | { |
160 | struct shape shape = { |
161 | .circle = 0, |
162 | .min = { |
163 | .x = x, |
164 | .y = y, |
165 | }, |
166 | .max = { |
167 | .x = x+w, |
168 | .y = y+h, |
169 | }, |
170 | }; |
171 | |
172 | if (next) |
173 | return test_overlap(next, NULL, &shape, allow); |
174 | return shapes_overlap(other, &shape, allow); |
175 | } |
176 | |
177 | |
178 | static int test_overlap(const struct inst *a, const struct inst *b, |
179 | const struct shape *other, enum allow_overlap allow) |
180 | { |
181 | struct coord min, max; |
182 | unit_type h, w, r; |
183 | int rounded; |
184 | |
185 | min = a->base; |
186 | switch (a->obj->type) { |
187 | case ot_pad: |
188 | max = a->u.pad.other; |
189 | rounded = a->obj->u.pad.rounded; |
190 | break; |
191 | case ot_hole: |
192 | max = a->u.hole.other; |
193 | rounded = 1; |
194 | break; |
195 | default: |
196 | abort(); |
197 | } |
198 | sort_coord(&min, &max); |
199 | |
200 | h = max.y-min.y; |
201 | w = max.x-min.x; |
202 | |
203 | if (!rounded) |
204 | return do_rect(b, other, min.x, min.y, w, h, allow); |
205 | |
206 | if (h > w) { |
207 | r = w/2; |
208 | return do_circle(b, other, min.x+r, max.y-r, r, allow) || |
209 | do_rect(b, other, min.x, min.y+r, w, h-2*r, allow) || |
210 | do_circle(b, other, min.x+r, min.y+r, r, allow); |
211 | } else { |
212 | r = h/2; |
213 | return do_circle(b, other, min.x+r, min.y+r, r, allow) || |
214 | do_rect(b, other, min.x+r, min.y, w-2*r, h, allow) || |
215 | do_circle(b, other, max.x-r, min.y+r, r, allow); |
216 | } |
217 | } |
218 | |
219 | |
220 | int overlap(const struct inst *a, const struct inst *b, |
221 | enum allow_overlap allow) |
222 | { |
223 | if (allow == ao_any) |
224 | return 0; |
225 | return test_overlap(a, b, NULL, allow); |
226 | } |
227 |
Branches:
master