Root/overlap.c

Source at commit a9ed5b30aa457704a4c0c912367bfe8c57db8d03 created 3 years 4 months ago.
By Werner Almesberger, fped.1: update for new options; fix typo; bump date
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
26int 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
65struct shape {
66    int circle;
67    struct coord center;
68    unit_type r;
69    struct coord min, max;
70};
71
72
73static 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
82static 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
99static 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
116static 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
134static int test_overlap(const struct inst *a, const struct inst *b,
135    const struct shape *other, enum allow_overlap allow);
136
137
138static 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
156static 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
178static 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
220int 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

Archive Download this file

Branches:
master



interactive