[gtk/glyphy2: 9/47] curve: Refine line-line intersection
- From: Matthias Clasen <matthiasc src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gtk/glyphy2: 9/47] curve: Refine line-line intersection
- Date: Sun, 3 Apr 2022 01:02:25 +0000 (UTC)
commit 418272570d685e8a297852bd8c18b3c07dfe3268
Author: Matthias Clasen <mclasen redhat com>
Date: Mon Mar 28 00:18:58 2022 -0400
curve: Refine line-line intersection
For collinear line segments, return up to 2 intersections
for the endpoints of the intersection (which is also a
line segment in this case).
Tests included.
gsk/gskcurveintersect.c | 107 +++++++++++++++++++++++++++++++++---
testsuite/gsk/curve-special-cases.c | 68 +++++++++++++++++++++++
2 files changed, 168 insertions(+), 7 deletions(-)
---
diff --git a/gsk/gskcurveintersect.c b/gsk/gskcurveintersect.c
index 486224b375..c33d560c79 100644
--- a/gsk/gskcurveintersect.c
+++ b/gsk/gskcurveintersect.c
@@ -33,7 +33,8 @@ line_intersect (const GskCurve *curve1,
const GskCurve *curve2,
float *t1,
float *t2,
- graphene_point_t *p)
+ graphene_point_t *p,
+ int n)
{
const graphene_point_t *pts1 = curve1->line.points;
const graphene_point_t *pts2 = curve2->line.points;
@@ -43,22 +44,114 @@ line_intersect (const GskCurve *curve1,
float b2 = pts2[0].y - pts2[1].y;
float det = a1 * b2 - b1 * a2;
- if (det != 0)
+ if (fabs(det) > 0.01)
{
float tt = ((pts1[0].x - pts2[0].x) * b2 - (pts1[0].y - pts2[0].y) * a2) / det;
float ss = - ((pts1[0].y - pts2[0].y) * a1 - (pts1[0].x - pts2[0].x) * b1) / det;
if (acceptable (tt) && acceptable (ss))
{
- p->x = pts1[0].x + tt * (pts1[1].x - pts1[0].x);
- p->y = pts1[0].y + tt * (pts1[1].y - pts1[0].y);
+ p[0].x = pts1[0].x + tt * (pts1[1].x - pts1[0].x);
+ p[0].y = pts1[0].y + tt * (pts1[1].y - pts1[0].y);
- *t1 = tt;
- *t2 = ss;
+ t1[0] = tt;
+ t2[0] = ss;
return 1;
}
}
+ else /* parallel lines */
+ {
+ float r = a1 * (pts1[1].y - pts2[0].y) - (pts1[1].x - pts2[0].x) * b1;
+ float dist = (r * r) / (a1 * a1 + b1 * b1);
+ float t, s, tt, ss;
+
+ if (dist > 0.01)
+ return 0;
+
+ if (pts1[1].x != pts1[0].x)
+ {
+ t = (pts2[0].x - pts1[0].x) / (pts1[1].x - pts1[0].x);
+ s = (pts2[1].x - pts1[0].x) / (pts1[1].x - pts1[0].x);
+ }
+ else
+ {
+ t = (pts2[0].y - pts1[0].y) / (pts1[1].y - pts1[0].y);
+ s = (pts2[1].y - pts1[0].y) / (pts1[1].y - pts1[0].y);
+ }
+
+ if ((t < 0 && s < 0) || (t > 1 && s > 1))
+ return 0;
+
+ if (acceptable (t))
+ {
+ t1[0] = t;
+ t2[0] = 0;
+ p[0] = pts2[0];
+ }
+ else if (t < 0)
+ {
+ if (pts2[1].x != pts2[0].x)
+ tt = (pts1[0].x - pts2[0].x) / (pts2[1].x - pts2[0].x);
+ else
+ tt = (pts1[0].y - pts2[0].y) / (pts2[1].y - pts2[0].y);
+
+ t1[0] = 0;
+ t2[0] = tt;
+ p[0] = pts1[0];
+ }
+ else
+ {
+ if (pts2[1].x != pts2[0].x)
+ tt = (pts1[1].x - pts2[0].x) / (pts2[1].x - pts2[0].x);
+ else
+ tt = (pts1[1].y - pts2[0].y) / (pts2[1].y - pts2[0].y);
+
+ t1[0] = 1;
+ t2[0] = tt;
+ p[0] = pts1[1];
+ }
+
+ if (acceptable (s))
+ {
+ if (t2[0] == 1)
+ return 1;
+
+ t1[1] = s;
+ t2[1] = 1;
+ p[1] = pts2[1];
+ }
+ else if (s < 0)
+ {
+ if (t1[0] == 0)
+ return 1;
+
+ if (pts2[1].x != pts2[0].x)
+ ss = (pts1[0].x - pts2[0].x) / (pts2[1].x - pts2[0].x);
+ else
+ ss = (pts1[0].y - pts2[0].y) / (pts2[1].y - pts2[0].y);
+
+ t1[1] = 0;
+ t2[1] = ss;
+ p[1] = pts1[0];
+ }
+ else
+ {
+ if (t1[0] == 1)
+ return 1;
+
+ if (pts2[1].x != pts2[0].x)
+ ss = (pts1[1].x - pts2[0].x) / (pts2[1].x - pts2[0].x);
+ else
+ ss = (pts1[1].y - pts2[0].y) / (pts2[1].y - pts2[0].y);
+
+ t1[1] = 1;
+ t2[1] = ss;
+ p[1] = pts1[1];
+ }
+
+ return 2;
+ }
return 0;
}
@@ -451,7 +544,7 @@ gsk_curve_intersect (const GskCurve *curve1,
* Everything else is done via bisection.
*/
if (op1 == GSK_PATH_LINE && op2 == GSK_PATH_LINE)
- return line_intersect (curve1, curve2, t1, t2, p);
+ return line_intersect (curve1, curve2, t1, t2, p, n);
else if (op1 == GSK_PATH_LINE && op2 == GSK_PATH_CURVE)
return line_curve_intersect (curve1, curve2, t1, t2, p, n);
else if (op1 == GSK_PATH_CURVE && op2 == GSK_PATH_LINE)
diff --git a/testsuite/gsk/curve-special-cases.c b/testsuite/gsk/curve-special-cases.c
index 1bb16c9a48..14dd527878 100644
--- a/testsuite/gsk/curve-special-cases.c
+++ b/testsuite/gsk/curve-special-cases.c
@@ -223,6 +223,73 @@ test_errant_intersection2 (void)
g_assert_true (n == 1);
}
+static void
+test_line_intersection_parallel (void)
+{
+ GskCurve l1;
+ GskCurve l2;
+ graphene_point_t p1[1];
+ graphene_point_t p2[2];
+ float t1[3], t2[3];
+ graphene_point_t s[3];
+ int n;
+
+ graphene_point_init (&p1[0], 0, 100);
+ graphene_point_init (&p1[1], 100, 100);
+ gsk_curve_init (&l1, gsk_pathop_encode (GSK_PATH_LINE, p1));
+
+ graphene_point_init (&p2[0], 0, 110);
+ graphene_point_init (&p2[1], 100, 110);
+ gsk_curve_init (&l2, gsk_pathop_encode (GSK_PATH_LINE, p2));
+
+ n = gsk_curve_intersect (&l1, &l2, t1, t2, s, G_N_ELEMENTS (s));
+
+ g_assert_true (n == 0);
+
+ graphene_point_init (&p2[0], 110, 100);
+ graphene_point_init (&p2[1], 210, 100);
+ gsk_curve_init (&l2, gsk_pathop_encode (GSK_PATH_LINE, p2));
+
+ n = gsk_curve_intersect (&l1, &l2, t1, t2, s, G_N_ELEMENTS (s));
+
+ g_assert_true (n == 0);
+
+ graphene_point_init (&p2[0], 0, 100);
+ graphene_point_init (&p2[1], -100, 100);
+ gsk_curve_init (&l2, gsk_pathop_encode (GSK_PATH_LINE, p2));
+
+ n = gsk_curve_intersect (&l1, &l2, t1, t2, s, G_N_ELEMENTS (s));
+
+ g_assert_true (n == 1);
+ g_assert_cmpfloat_with_epsilon (t1[0], 0, 0.001);
+ g_assert_cmpfloat_with_epsilon (t2[0], 0, 0.001);
+
+ graphene_point_init (&p2[0], 20, 100);
+ graphene_point_init (&p2[1], 80, 100);
+ gsk_curve_init (&l2, gsk_pathop_encode (GSK_PATH_LINE, p2));
+
+ n = gsk_curve_intersect (&l1, &l2, t1, t2, s, G_N_ELEMENTS (s));
+
+ g_assert_true (n == 2);
+ g_assert_cmpfloat_with_epsilon (t1[0], 0.2, 0.001);
+ g_assert_cmpfloat_with_epsilon (t1[1], 0.8, 0.001);
+ g_assert_cmpfloat_with_epsilon (t2[0], 0, 0.001);
+ g_assert_cmpfloat_with_epsilon (t2[1], 1, 0.001);
+
+ graphene_point_init (&p2[0], 150, 100);
+ graphene_point_init (&p2[1], 50, 100);
+ gsk_curve_init (&l2, gsk_pathop_encode (GSK_PATH_LINE, p2));
+
+ n = gsk_curve_intersect (&l1, &l2, t1, t2, s, G_N_ELEMENTS (s));
+
+ g_assert_true (n == 2);
+ g_assert_cmpfloat_with_epsilon (t1[0], 1, 0.001);
+ g_assert_cmpfloat_with_epsilon (t1[1], 0.5, 0.001);
+ g_assert_cmpfloat_with_epsilon (t2[0], 0.5, 0.001);
+ g_assert_cmpfloat_with_epsilon (t2[1], 1, 0.001);
+
+}
+
int
main (int argc,
char *argv[])
@@ -234,6 +301,7 @@ main (int argc,
g_test_add_func ("/curve/special/degenerate-tangents", test_curve_degenerate_tangents);
g_test_add_func ("/curve/errant-intersection", test_errant_intersection);
g_test_add_func ("/curve/errant-intersection2", test_errant_intersection2);
+ g_test_add_func ("/curve/line-intersection-parallel", test_line_intersection_parallel);
return g_test_run ();
}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]