From 0fcdbb1904c2f1c32c80ebe4da367742ef6e00bc Mon Sep 17 00:00:00 2001 From: Nicolas Schodet Date: Sat, 5 May 2012 19:02:53 +0200 Subject: digital/avr/modules/math/geometry: slightly change intersection meaning When a segment end is exactly on the other segment, consider there is no intersection. --- digital/avr/modules/math/geometry/intersection.c | 11 +++++++---- digital/avr/modules/math/geometry/intersection.h | 3 ++- digital/avr/modules/math/geometry/test/test_geometry.c | 3 +++ 3 files changed, 12 insertions(+), 5 deletions(-) (limited to 'digital/avr/modules') diff --git a/digital/avr/modules/math/geometry/intersection.c b/digital/avr/modules/math/geometry/intersection.c index 1f8a9278..a1daf72d 100644 --- a/digital/avr/modules/math/geometry/intersection.c +++ b/digital/avr/modules/math/geometry/intersection.c @@ -25,18 +25,21 @@ #include "common.h" #include "intersection.h" -/** Compare a and b to determine if a / b is in [0:1]. Return non zero if +/** Compare a and b to determine if a / b is in ]0:1[. Return non zero if * true. */ static uint8_t intersection_div_is_in_0_1 (int32_t a, int32_t b) { + assert (b != 0); /* Test sign, a / b < 0 if different. */ - if ((a >> 31) ^ (b >> 31)) + if ((a ^ b) & 0x80000000) + return 0; + else if (a == 0) return 0; else if (a > 0) - return a <= b; + return a < b; else - return a >= b; + return a > b; } uint8_t diff --git a/digital/avr/modules/math/geometry/intersection.h b/digital/avr/modules/math/geometry/intersection.h index faff928c..c1998fb2 100644 --- a/digital/avr/modules/math/geometry/intersection.h +++ b/digital/avr/modules/math/geometry/intersection.h @@ -31,7 +31,8 @@ * - a, b: first line segment vertices. * - c, d: second line segment vertices. * - * If AB and CD are parallel, consider there is no intersection. */ + * If AB and CD are parallel or if a vertice is exactly on the other segment, + * consider there is no intersection. */ uint8_t intersection_segment_segment (const vect_t *a, const vect_t *b, const vect_t *c, const vect_t *d); diff --git a/digital/avr/modules/math/geometry/test/test_geometry.c b/digital/avr/modules/math/geometry/test/test_geometry.c index 3466ad06..35511fa8 100644 --- a/digital/avr/modules/math/geometry/test/test_geometry.c +++ b/digital/avr/modules/math/geometry/test/test_geometry.c @@ -245,6 +245,7 @@ test_intersection (void) vect_t v02 = { 0, 20 }; vect_t v20 = { 20, 0 }; vect_t v22 = { 20, 20 }; + vect_t v11 = { 10, 10 }; vect_t v44 = { 40, 40 }; test (intersection_segment_segment (&v00, &v22, &v20, &v02) == 1); test (intersection_segment_segment (&v00, &v22, &v02, &v20) == 1); @@ -255,6 +256,8 @@ 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); + test (intersection_segment_segment (&v44, &v00, &v11, &v20) == 0); + test (intersection_segment_segment (&v44, &v00, &v20, &v11) == 0); vect_t poly[] = { { 10, 0 }, { 0, 10 }, { -10, 0 }, { 0, -10 } }; vect_t a = { 20, 10 }; vect_t b = { 10, 20 }; -- cgit v1.2.3