[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: gEDA-user: gEDA-dev: Arc intersection connectivity bug
On 11/15/09, Ineiev <ineiev@xxxxxxxxx> wrote:
> That resulted in arc.bis.patch.
Then, eliminate two precision losses.
I feel I ought to stop here: the patch fixes
many more bugs than originally reported.
Cheers,
Ineiev
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