[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: gEDA-user: more kvetch re: pcb Arcs



On Tue, 2010-02-02 at 11:48 -0600, Mark Rages wrote:
> Gentlemen of geda-user,
> 
> May I direct your attention to the bug report I filed last week
> http://sourceforge.net/tracker/?func=detail&aid=2942582&group_id=73743&atid=538811
> 
> The design I'm working on has a lot of these long, swooping arcs, and
> the pcb's intersection-handling code just isn't working on it at all.
> 
> I can click on one half of an arc and it is not selected, but clicking
> on the other half works.

I think this issue is a known one, and there is a patch from Iniev which
may fix it. I'm sorry I've not got around to applying it in git HEAD.
Perhaps one of the other PCB developers could take a look.

> If I can't get this working in the next few days, I'll probably be
> buying a license for Altium and a Windows computer.  The thought
> depresses me.

Appealing for help is good, but "threats" to go use a competitor product
are not likely to engender much support.

In any case, try Iniev's patch (attached), and let us know if this
helps.

Best wishes,

Peter C.
diff --git a/src/find.c b/src/find.c
index 1962234..6fb62b6 100644
--- a/src/find.c
+++ b/src/find.c
@@ -1327,11 +1327,61 @@ PVTouchesLine (LineTypePtr line)
   return (False);
 }
 
+/* reduce arc start angle and delta to 0..360 */
+static void
+normalize_angles (int *sa, int *d)
+{
+  if (*d < 0)
+    {
+      *sa += *d;
+      *d = - *d;
+    }
+  if (*d > 360) /* full circle */
+    *d = 360;
+  if (*sa < 0)
+    *sa = 360 - ((-*sa) % 360);
+  if (*sa >= 360)
+    *sa %= 360;
+}
+
+static int
+radius_crosses_arc (double x, double y, ArcTypePtr arc)
+{
+  double alpha = atan2 (y - arc->Y, -x + arc->X) * RAD_TO_DEG;
+  int sa = arc->StartAngle, d = arc->Delta;
+
+  normalize_angles (&sa, &d);
+  if (alpha < 0)
+    alpha += 360;
+  if ((double)sa <= alpha)
+    return (double)(sa + d) >= alpha;
+  return (double)(sa + d - 360) >= alpha;
+}
+
+static void
+get_arc_ends (double *box, ArcTypePtr arc)
+{
+  double ca, sa, angle;
+
+  angle  = arc->StartAngle;
+  angle *= M180;
+  ca = cos (angle);
+  sa = sin (angle);
+  box[0] = arc->X - arc->Width * ca;
+  box[1] = arc->Y + arc->Height * sa;
+
+  angle  = arc->StartAngle + arc->Delta;
+  angle *= M180;
+  ca = cos (angle);
+  sa = sin (angle);
+  box[2] = arc->X - arc->Width * ca;
+  box[3] = arc->Y + arc->Height * sa;
+}
 /* ---------------------------------------------------------------------------
  * check if two arcs intersect
  * first we check for circle intersections,
  * then find the actual points of intersection
- * and test them to see if they are on both arcs
+ * and test them to see if they are on arcs
  *
  * consider a, the distance from the center of arc 1
  * to the point perpendicular to the intersecting points.
@@ -1355,18 +1405,32 @@ PVTouchesLine (LineTypePtr line)
 static Boolean
 ArcArcIntersect (ArcTypePtr Arc1, ArcTypePtr Arc2)
 {
-  register float x, y, dx, dy, r1, r2, a, d, l, t, t2;
-  register LocationType pdx, pdy;
-  BoxTypePtr box;
-  BoxType box1, box2;
+  double x, y, dx, dy, r1, r2, a, d, l, t, t1, t2, dl;
+  LocationType pdx, pdy;
+  double box[4];
+
+  t = 0.5 * Arc1->Thickness + fBloat;
+  if (t < 0) /* too thin arc */
+    return (False);
+  t2 = 0.5 * Arc2->Thickness;
+  t1 = t2 + fBloat;
+  if (t1 < 0) /* too thin arc */
+    return (False);
+  /* try the end points first */
+  get_arc_ends (box, Arc1);
+  if (IsPointOnArc ((float) box[0], (float) box[1], (float)t, Arc2)
+      || IsPointOnArc ((float) box[2], (float) box[3], (float)t, Arc2))
+    return (True);
 
+  get_arc_ends (box, Arc2);
+  if (IsPointOnArc ((float) box[0], (float) box[1], (float)t1, Arc1)
+      || IsPointOnArc ((float) box[2], (float) box[3], (float)t1, Arc1))
+    return (True);
   pdx = Arc2->X - Arc1->X;
   pdy = Arc2->Y - Arc1->Y;
   l = pdx * pdx + pdy * pdy;
-  t = MAX (0.5 * Arc1->Thickness + fBloat, 0.0);
-  t2 = 0.5 * Arc2->Thickness;
   /* concentric arcs, simpler intersection conditions */
-  if (l == 0.0)
+  if (l < 0.5)
     {
       if ((Arc1->Width - t >= Arc2->Width - t2
            && Arc1->Width - t <=
@@ -1374,82 +1438,93 @@ ArcArcIntersect (ArcTypePtr Arc1, ArcTypePtr Arc2)
           || (Arc1->Width + t >=
               Arc2->Width - t2 && Arc1->Width + t <= Arc2->Width + t2))
         {
-          if ((Arc2->BoundingBox.X1 +
-               MAX (Arc2->Thickness + Bloat,
-                    0) >= Arc1->BoundingBox.X1
-               && Arc2->BoundingBox.X1 <=
-               Arc1->BoundingBox.X2
-               && Arc2->BoundingBox.Y1 +
-               MAX (Arc2->Thickness + Bloat,
-                    0) >= Arc1->BoundingBox.Y1
-               && Arc2->BoundingBox.Y1 <=
-               Arc1->BoundingBox.Y2)
-              || (Arc2->BoundingBox.X2 +
-                  MAX (Arc2->Thickness +
-                       Bloat,
-                       0) >=
-                  Arc1->BoundingBox.X1
-                  && Arc2->BoundingBox.X2 <=
-                  Arc1->BoundingBox.X2
-                  && Arc2->BoundingBox.Y2 +
-                  MAX (Arc2->Thickness +
-                       Bloat,
-                       0) >=
-                  Arc1->BoundingBox.Y1
-                  && Arc2->BoundingBox.Y2 <= Arc1->BoundingBox.Y2))
-            return (True);
+	  int sa1 = Arc1->StartAngle, d1 = Arc1->Delta;
+	  int sa2 = Arc2->StartAngle, d2 = Arc2->Delta;
+	  /* NB the endpoints have already been checked,
+	     so we just compare the angles */
+
+	  normalize_angles (&sa1, &d1);
+	  normalize_angles (&sa2, &d2);
+	  /* cases like sa1 == sa2 are catched when checking the endpoints */
+	  if (sa1 > sa2)
+	    {
+	      if (sa1 < sa2 + d2)
+		return (True);
+	      if (sa1 + d1 > 360 && sa1 + d1 - 360 > sa2)
+		return (True);
+	    }
+	  if (sa2 > sa1)
+	    {
+	      if (sa2 < sa1 + d1)
+		return (True);
+	      if (sa2 + d2 > 360 && sa2 + d2 - 360 > sa1)
+		return (True);
+	    }
         }
       return (False);
     }
-  r1 = Arc1->Width + t;
+  r1 = Arc1->Width;
+  r2 = Arc2->Width;
+  dl = sqrt (l);
+  if (dl > r1 + r2 || dl + r1 < r2
+      || dl + r2 < r1) /* arcs centerlines are too far or too near */
+    {
+      /* check the nearst to the other arc center point */
+      dx = pdx * r1 / dl;
+      dy = pdy * r1 / dl;
+      if (dl + r1 < r2) /* Arc1 inside Arc2 */
+	{
+	  dx = - dx;
+	  dy = - dy;
+	}
+
+      if (radius_crosses_arc (Arc1->X + dx, Arc1->Y + dy, Arc1)
+	  && IsPointOnArc ((float)(Arc1->X + dx), (float)(Arc1->Y + dy),
+			   (float)t, Arc2))
+	return (True);
+
+      dx = - pdx * r2 / dl;
+      dy = - pdy * r2 / dl;
+      if (dl + r2 < r1) /* Arc2 inside Arc1 */
+	{
+	  dx = - dx;
+	  dy = - dy;
+	}
+
+      if (radius_crosses_arc (Arc2->X + dx, Arc2->Y + dy, Arc2)
+	  && IsPointOnArc ((float)(Arc2->X + dx), (float)(Arc2->Y + dy),
+			   (float)t1, Arc1))
+	return (True);
+      return (False);
+    }
+
   r1 *= r1;
-  r2 = Arc2->Width + t2;
   r2 *= r2;
   a = 0.5 * (r1 - r2 + l) / l;
   r1 = r1 / l;
-  /* add a tiny positive number for round-off problems */
-  d = r1 - a * a + 1e-5;
-  /* the circles are too far apart to touch */
+  d = r1 - a * a;
+  /* the circles are too far apart to touch or probably just touch:
+     check the nearest point */
   if (d < 0)
-    return (False);
-  d = sqrt (d);
+    d = 0;
+  else
+    d = sqrt (d);
   x = Arc1->X + a * pdx;
   y = Arc1->Y + a * pdy;
   dx = d * pdx;
   dy = d * pdy;
-  if (x + dy >= Arc1->BoundingBox.X1
-      && x + dy <= Arc1->BoundingBox.X2
-      && y - dx >= Arc1->BoundingBox.Y1
-      && y - dx <= Arc1->BoundingBox.Y2
-      && x + dy >= Arc2->BoundingBox.X1
-      && x + dy <= Arc2->BoundingBox.X2
-      && y - dx >= Arc2->BoundingBox.Y1 && y - dx <= Arc2->BoundingBox.Y2)
+  if (radius_crosses_arc (x + dy, y - dx, Arc1)
+      && IsPointOnArc ((float)(x + dy), (float)(y - dx), (float)t, Arc2))
     return (True);
-
-  if (x - dy >= Arc1->BoundingBox.X1
-      && x - dy <= Arc1->BoundingBox.X2
-      && y + dx >= Arc1->BoundingBox.Y1
-      && y + dx <= Arc1->BoundingBox.Y2
-      && x - dy >= Arc2->BoundingBox.X1
-      && x - dy <= Arc2->BoundingBox.X2
-      && y + dx >= Arc2->BoundingBox.Y1 && y + dx <= Arc2->BoundingBox.Y2)
+  if (radius_crosses_arc (x + dy, y - dx, Arc2)
+      && IsPointOnArc ((float)(x + dy), (float)(y - dx), (float)t1, Arc1))
     return (True);
 
-  /* try the end points in case the ends don't actually pierce the outer radii */
-  box = GetArcEnds (Arc1);
-  box1 = *box;
-  box = GetArcEnds (Arc2);
-  box2 = *box;
-  if (IsPointOnArc
-      ((float) box1.X1, (float) box1.Y1, t,
-       Arc2) || IsPointOnArc ((float) box1.X2, (float) box1.Y2, t, Arc2))
+  if (radius_crosses_arc (x - dy, y + dx, Arc1)
+      && IsPointOnArc ((float)(x - dy), (float)(y + dx), (float)t, Arc2))
     return (True);
-
-  if (IsPointOnArc
-      ((float) box2.X1, (float) box2.Y1,
-       MAX (t2 + fBloat, 0.0), Arc1)
-      || IsPointOnArc ((float) box2.X2,
-                       (float) box2.Y2, MAX (t2 + fBloat, 0.0), Arc1))
+  if (radius_crosses_arc (x - dy, y + dx, Arc2)
+      && IsPointOnArc ((float)(x - dy), (float)(y + dx), (float)t1, Arc1))
     return (True);
   return (False);
 }
diff --git a/src/search.c b/src/search.c
index 07015f0..4d450d3 100644
--- a/src/search.c
+++ b/src/search.c
@@ -1040,32 +1040,35 @@ IsPointInBox (LocationType X, LocationType Y, BoxTypePtr box, BDimension Radius)
 Boolean
 IsPointOnArc (float X, float Y, float Radius, ArcTypePtr Arc)
 {
-
-  register float x, y, dx, dy, r1, r2, a, d, l;
-  register float pdx, pdy;
-  int ang1, ang2, delta;
+  double x, y, dx, dy, r1, r2, a, d, l;
+  double pdx, pdy;
+  double ang1, ang2, ang0, delta;
   int startAngle, arcDelta;
 
   pdx = X - Arc->X;
   pdy = Y - Arc->Y;
   l = pdx * pdx + pdy * pdy;
+  Radius += 0.5 * Arc->Thickness;
+  if (Radius < 0) /* thin arc: trivial condition */
+    return (False);
   /* concentric arcs, simpler intersection conditions */
-  if (l == 0.0)
+  if (l < 0.5)
     {
-      if (Arc->Width <= Radius + 0.5 * Arc->Thickness)
+      if (Arc->Width <= Radius)
 	return (True);
       else
 	return (False);
     }
   r1 = Arc->Width;
+  r2 = Radius;
+  if (sqrt (l) < r2 - r1) /* the arc merged in the circle */
+    return (True);
   r1 *= r1;
-  r2 = Radius + 0.5 * Arc->Thickness;
   r2 *= r2;
   a = 0.5 * (r1 - r2 + l) / l;
   r1 = r1 / l;
-  /* add a tiny positive number for round-off problems */
-  d = r1 - a * a + 1e-5;
-  /* the circles are too far apart to touch */
+  d = r1 - a * a;
+  /* the circles are too far apart to touch or probably just touch */
   if (d < 0)
     return (False);
   /* project the points of intersection */
@@ -1077,32 +1080,38 @@ IsPointOnArc (float X, float Y, float Radius, ArcTypePtr Arc)
   /* arrgh! calculate the angles, and put them in a standard range */
   startAngle = Arc->StartAngle;
   arcDelta = Arc->Delta;
-  while (startAngle < 0)
-    startAngle += 360;
   if (arcDelta < 0)
     {
       startAngle += arcDelta;
       arcDelta = -arcDelta;
-      while (startAngle < 0)
-	startAngle += 360;
     }
+  if (arcDelta > 360)
+    arcDelta = 360;
+  while (startAngle < 0)
+    startAngle += 360;
+  while (startAngle > 360)
+    startAngle -= 360;
   ang1 = RAD_TO_DEG * atan2 ((y + dy), -(x + dx));
   if (ang1 < 0)
     ang1 += 360;
   ang2 = RAD_TO_DEG * atan2 ((y - dy), -(x - dx));
   if (ang2 < 0)
     ang2 += 360;
+  if (ang1 > ang2)
+    {
+      ang0 = ang1;
+      ang1 = ang2;
+      ang2 = ang0;
+    }
   delta = ang2 - ang1;
-  if (delta > 180)
-    delta -= 360;
-  else if (delta < -180)
-    delta += 360;
-  if (delta < 0)
+  /* ang0 does not belong to intersection range */
+  ang0 = RAD_TO_DEG * atan2 (-pdy, pdx);
+  if (ang0 < 0)
+    ang0 += 360;
+  if (ang0 > ang1 && ang0 < ang2) /* we need the other part of circle */
     {
-      ang1 += delta;
-      delta = -delta;
-      while (ang1 < 0)
-	ang1 += 360;
+      ang1 = ang2;
+      delta = 360 - delta;
     }
   if (ang1 >= startAngle && ang1 <= startAngle + arcDelta)
     return (True);

_______________________________________________
geda-user mailing list
geda-user@xxxxxxxxxxxxxx
http://www.seul.org/cgi-bin/mailman/listinfo/geda-user