[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
Re: gEDA-user: gEDA-dev: Arc intersection connectivity bug
On Thu, 2009-11-12 at 20:06 +0000, Ineiev wrote:
> Probably the function should be rewritten almost completely.
> I'll try tomorrow.
And this is what comes in the attachment.
First, I suggest computations against the centerlines
of arcs; this simplifies the geometry and does not
impose limitations because we have no square-ended arcs.
The general method is to use IsPointOnArc to test several
candidates and return false if all tests results are negative.
Thus, the suggested sequence is:
(1) check the ends of each arc against the other arc.
this is done unconditionally, as it would be needed
in all groups of cases (2)..(4) under certain conditions.
generally, the nearest distance from one arc to
another is achieved either on an end of the first
or the second arc, or on the line connecting
the centers of the arcs.
(2) check concentric arcs.
it is treated now almost correctly; but
the bounding boxes are irrelevant; also,
I'd s/l == 0\.0/l < 0\.5/ because I believe
that the compiler should have freedom to optimise
the former to false.
(3) check non-intersecting centerlines. test
the nearest to the other arc's center
point of circle (if it is included into the arc)
against the other arc; this is the only candidate
besides the arc endpoints for this case.
(4) check intersecting arcs. try points of intersections
against the other arc (if these points of intersection
lie on the arc), for each arc and
each point of intersection.
Other suggestions? any ideas?
diff --git a/src/find.c b/src/find.c
index b24512a..ca12b93 100644
--- a/src/find.c
+++ b/src/find.c
@@ -1327,11 +1327,45 @@ PVTouchesLine (LineTypePtr line)
return (False);
}
+static int
+radius_crosses_arc (float x, float y, ArcTypePtr arc)
+{
+ float alpha = atan2 (y - arc->Y, x - arc->X) * 180 / M_PI, start, delta;
+
+ start = (float) fmod (arc->StartAngle, 360);
+ delta = arc->Delta;
+ if (alpha < 0)
+ alpha += 360;
+ if (start < 0)
+ start += 360;
+ if (delta < 0)
+ {
+ start += delta;
+ delta = -delta;
+ }
+ return (start < alpha && start + delta > alpha);
+}
+/* reduce arc start angle and delta to 0..360 */
+static void
+normalize_angles (int *sa, int *d)
+{
+ if (*d < 0)
+ {
+ *sa = *sa + *d;
+ *d = - *d;
+ }
+ if (*d > 360) /* full circle */
+ *d = 360;
+ if (*sa < 0)
+ *sa = 360 - ((-*sa) % 360);
+ if (*sa >= 360)
+ *sa %= 360;
+}
/* ---------------------------------------------------------------------------
* 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 +1389,29 @@ 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;
+ float x, y, dx, dy, r1, r2, a, d, l, t, t1, t2, dl;
+ LocationType pdx, pdy;
BoxTypePtr box;
- BoxType box1, box2;
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;
+ t1 = MAX (t2 + fBloat, 0.0);
+ /* try the end points first */
+ box = GetArcEnds (Arc1);
+ if (IsPointOnArc ((float) box->X1, (float) box->Y1, t, Arc2)
+ || IsPointOnArc ((float) box->X2, (float) box->Y2, t, Arc2))
+ return (True);
+
+ box = GetArcEnds (Arc2);
+ if (IsPointOnArc ((float) box->X1, (float) box->Y1, t1, Arc1)
+ || IsPointOnArc ((float) box->X2, (float) box->Y2, t1, Arc1))
+ return (True);
+
/* concentric arcs, simpler intersection conditions */
- if (l == 0.0)
+ if (l < 0.5)
{
if ((Arc1->Width - t >= Arc2->Width - t2
&& Arc1->Width - t <=
@@ -1374,36 +1419,66 @@ 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 > sa2)
+ return (True);
+ }
+ if (sa2 > sa1)
+ {
+ if (sa2 < sa1 + d1)
+ return (True);
+ if (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 (Arc1->X + dx, Arc1->Y + dy, 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 (Arc2->X + dx, Arc2->Y + dy, t1, Arc1))
+ return (True);
+
+ return (False);
+ }
+
r1 *= r1;
- r2 = Arc2->Width + t2;
r2 *= r2;
a = 0.5 * (r1 - r2 + l) / l;
r1 = r1 / l;
@@ -1411,46 +1486,29 @@ ArcArcIntersect (ArcTypePtr Arc1, ArcTypePtr Arc2)
d = r1 - a * a + 1e-5;
/* the circles are too far apart to touch */
if (d < 0)
- return (False);
+ {
+ /* this may not occur */
+ return (False);
+ }
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 (x + dy, y - dx, 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 (x + dy, y - dx, 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 (x - dy, y + dx, 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 (x - dy, y + dx, t1, Arc1))
return (True);
+
return (False);
}
_______________________________________________
geda-user mailing list
geda-user@xxxxxxxxxxxxxx
http://www.seul.org/cgi-bin/mailman/listinfo/geda-user