<< The elegance of code as a measure of quality | Radial hierarchy >>

The fillet pseudo code

about 484days ago by thimp

To find the arc segment that forms the fillet between two line segments you first have to find the centre of the arc by intersecting the offset of the two lines:

The start and end point of the arc are found by creating lines through the new found centre, perpendicular to the two lines:

Now we have enough data to construct the fillet arc:
a centre;
a radius;
a start point (implicating a start angle);
and a endpoint (implicating an and angle).

if you write this algorithm in pseudo (C#) code, you end up with:

[copy code to clipboard]

   1: public static ArcSegment FilletArc(LineSegment Line1, LineSegment Line2, double Radius)

   2:         {

   3:             Point center = (Point) Line1.Offset(Radius).Intersect(Line2.Offset(Radius));

   4:             return new ArcSegment()

   5:                    {

   6:                        Center = center,

   7:                        // P2 is the intersection point of the returned linesegment

   8:                        StartPoint = Line1.PerpendicularLine(center).P2,

   9:                        EndPoint = Line2.PerpendicularLine(center).P2,

  10:                    };

  11:         }

That looks neat! A few hurdles to take, though. the function LineSegment.Offset(double radius) does not take into account that there are two possible sides to offset to, resulting in 4 possible fillets. I’ll have to ponder on that a little more. The rest is trivial and coded …. Material for a next post.

Categories:		C#
Actions:		E-mail \| del.icio.us \| Permalink \| Comments (7) \| Comment RSS

Comments

June 22. 2009 23:40

I've been searching for such an algorithm all night. Found a lot of other math problems, solving for radii and what not. Just when I thought I'm on my own (except the hope to check out Graphics Gems 3 in the library tomorrow), I found this elegant solution of yours, explained with great illutrations, too.

Many thanks! I'll try it out in my target language ActionScript 3.

Oh, those 4 possible fillets? If you wanted to tackle that anyway, that "next post" would help me out a lot as well (basically solving my problem completely :))

Yu-Chung Chen

June 24. 2009 10:47

I've successfully implemented your algorithm. Figuring out the correct side for offset took more lines than actually calculating the fillet, but it works now.

Thanks again.

Yu-Chung Chen

July 4. 2009 15:56