From e50baf1bcea86bd969b7d87e9dd643607ef7f161 Mon Sep 17 00:00:00 2001 From: Nicolas Schodet Date: Sat, 5 May 2012 17:39:11 +0200 Subject: digital/avr/modules/math/geometry: intersection with a polygon --- digital/avr/modules/math/geometry/intersection.c | 17 +++++++++++++++++ digital/avr/modules/math/geometry/intersection.h | 9 +++++++++ digital/avr/modules/math/geometry/test/test_geometry.c | 13 +++++++++++++ 3 files changed, 39 insertions(+) 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 -- cgit v1.2.3