summaryrefslogtreecommitdiff
path: root/digital/avr
diff options
context:
space:
mode:
authorNicolas Schodet2012-05-05 17:39:11 +0200
committerNicolas Schodet2012-05-05 17:39:11 +0200
commite50baf1bcea86bd969b7d87e9dd643607ef7f161 (patch)
tree3f4b2e01a3d0b9362d8bd88bc735155c19623d2b /digital/avr
parentacd8e0eefa259500bf1325fa6b84c3b615d00782 (diff)
digital/avr/modules/math/geometry: intersection with a polygon
Diffstat (limited to 'digital/avr')
-rw-r--r--digital/avr/modules/math/geometry/intersection.c17
-rw-r--r--digital/avr/modules/math/geometry/intersection.h9
-rw-r--r--digital/avr/modules/math/geometry/test/test_geometry.c13
3 files changed, 39 insertions, 0 deletions
diff --git a/digital/avr/modules/math/geometry/intersection.c b/digital/avr/modules/math/geometry/intersection.c
index 8438813b..1f8a9278 100644
--- a/digital/avr/modules/math/geometry/intersection.c
+++ b/digital/avr/modules/math/geometry/intersection.c
@@ -85,3 +85,20 @@ intersection_segment_segment (const vect_t *a, const vect_t *b,
}
}
}
+
+uint8_t
+intersection_segment_poly (const vect_t *a, const vect_t *b,
+ const vect_t *poly, uint8_t poly_size)
+{
+ uint8_t i;
+ assert (poly_size > 0);
+ for (i = 0; i < poly_size - 1; i++)
+ {
+ if (intersection_segment_segment (a, b, &poly[i], &poly[i + 1]))
+ return 1;
+ }
+ if (intersection_segment_segment (a, b, &poly[i], &poly[0]))
+ return 1;
+ return 0;
+}
+
diff --git a/digital/avr/modules/math/geometry/intersection.h b/digital/avr/modules/math/geometry/intersection.h
index 9f9cf161..faff928c 100644
--- a/digital/avr/modules/math/geometry/intersection.h
+++ b/digital/avr/modules/math/geometry/intersection.h
@@ -36,4 +36,13 @@ uint8_t
intersection_segment_segment (const vect_t *a, const vect_t *b,
const vect_t *c, const vect_t *d);
+/** Test intersection between a line segment and any line segment defining a
+ * polygon. Return non zero if they intersect.
+ * - a, b: line segment vertices.
+ * - poly: array of polygon vertices.
+ * - poly_size: number of polygon vertices. */
+uint8_t
+intersection_segment_poly (const vect_t *a, const vect_t *b,
+ const vect_t *poly, uint8_t poly_size);
+
#endif /* intersection_h */
diff --git a/digital/avr/modules/math/geometry/test/test_geometry.c b/digital/avr/modules/math/geometry/test/test_geometry.c
index 7b3c5e47..3466ad06 100644
--- a/digital/avr/modules/math/geometry/test/test_geometry.c
+++ b/digital/avr/modules/math/geometry/test/test_geometry.c
@@ -240,6 +240,7 @@ test_distance (void)
void
test_intersection (void)
{
+ uint8_t i;
vect_t v00 = { 0, 0 };
vect_t v02 = { 0, 20 };
vect_t v20 = { 20, 0 };
@@ -254,6 +255,18 @@ test_intersection (void)
test (intersection_segment_segment (&v22, &v44, &v02, &v20) == 0);
test (intersection_segment_segment (&v00, &v44, &v02, &v20) == 1);
test (intersection_segment_segment (&v44, &v00, &v02, &v20) == 1);
+ vect_t poly[] = { { 10, 0 }, { 0, 10 }, { -10, 0 }, { 0, -10 } };
+ vect_t a = { 20, 10 };
+ vect_t b = { 10, 20 };
+ vect_t o = { 0, 0 };
+ for (i = 0; i < 8; i++)
+ {
+ test (intersection_segment_poly (&a, &b, poly, UTILS_COUNT (poly)) == 0);
+ test (intersection_segment_poly (&o, &a, poly, UTILS_COUNT (poly)) == 1);
+ test (intersection_segment_poly (&o, &b, poly, UTILS_COUNT (poly)) == 1);
+ vect_rotate_uf016 (&a, G_ANGLE_UF016_DEG (45));
+ vect_rotate_uf016 (&b, G_ANGLE_UF016_DEG (45));
+ }
}
int