# r5704 - developers/werner/cncmap/zmap

werner at docs.openmoko.org werner at docs.openmoko.org
Fri Oct 23 01:27:55 CEST 2009

```Author: werner
Date: 2009-10-23 01:27:55 +0200 (Fri, 23 Oct 2009)
New Revision: 5704

Modified:
developers/werner/cncmap/zmap/zline.c
developers/werner/cncmap/zmap/zmap.c
Log:
More algorithm fixes. We should now be good, except for some corner cases.

- zmap/zmap.c (zmap_point): treat this as a linear equation with two unknowns.
The previous algorithm only worked if the points formed a triangle with a
right angle and the first point was at that angle.
- zmap/zline.c (zline): we still have to consider "old" points, as they may
replace different points as we crawl the line

Modified: developers/werner/cncmap/zmap/zline.c
===================================================================
--- developers/werner/cncmap/zmap/zline.c	2009-10-22 21:23:05 UTC (rev 5703)
+++ developers/werner/cncmap/zmap/zline.c	2009-10-22 23:27:55 UTC (rev 5704)
@@ -123,7 +123,6 @@
void (*point)(void *user, double x, double y, double z), void *user)
{
double t;
-	int n;
double best_t, tmp_t;
int best_next, best_old;
int i, tmp_i;
@@ -135,13 +134,13 @@
point(user, xa, ya, zmap_point(map[0], map[1], map[2], xa, ya));

t = 0;
-	n = map_n;
-	while (n > 3) {
+	while (1) {
best_t = 1;
best_next = best_old = -1;
for (i = 0; i != 3; i++) {
tmp_t = t;
-			tmp_i = next_closest(xa, ya, xb, yb, i, 3, n, &tmp_t);
+			tmp_i = next_closest(xa, ya, xb, yb, i, 3, map_n,
+			    &tmp_t);
DEBUG("%d: i = %d t = %g (@%g)\n", i, tmp_i, tmp_t, t);
if (tmp_t < best_t) {
best_t = tmp_t;
@@ -151,11 +150,8 @@
}
if (best_next == -1)
break;
-		DEBUG("swap %d vs. %d of %d\n", best_old, best_next, n);
-		swap(best_old, n-1);
-		if (best_next != n-1)
-			swap(best_old, best_next);
-		n--;
+		DEBUG("swap %d vs. %d\n", best_old, best_next);
+		swap(best_old, best_next);
t = best_t;
x = xa+(xb-xa)*t;
y = ya+(yb-ya)*t;

Modified: developers/werner/cncmap/zmap/zmap.c
===================================================================
--- developers/werner/cncmap/zmap/zmap.c	2009-10-22 21:23:05 UTC (rev 5703)
+++ developers/werner/cncmap/zmap/zmap.c	2009-10-22 23:27:55 UTC (rev 5704)
@@ -120,9 +120,9 @@
double zmap_point(struct xyz a, struct xyz b, struct xyz c, double x, double y)
{
double xp, yp;
-	double xu, yu, zu, u;
-	double xv, yv, zv, v;
-	double s, t;
+	double xu, yu, zu;
+	double xv, yv, zv;
+	double det, s, t;

DEBUG("point (%g, %g) -> (%g, %g) (%g, %g) (%g, %g)\n",
x, y, a.x, a.y, b.x, b.y, c.x, c.y);
@@ -132,15 +132,14 @@
xu = b.x-a.x;
yu = b.y-a.y;
zu = b.z-a.z;
-	u = hypot(xu, yu);

xv = c.x-a.x;
yv = c.y-a.y;
zv = c.z-a.z;
-	v = hypot(xv, yv);

-	s = (xp*xu+yp*yu)/u/u;
-	t = (xp*xv+yp*yv)/v/v;
+	det = xu*yv-yu*xv;
+	s = (xp*yv-yp*xv)/det;
+	t = (xu*yp-yu*xp)/det;

return a.z+s*zu+t*zv;
}

```