55
56
return Geom::Circle(center, fabs(radius));
60
// Area of triangle given three corner points
61
static double area( Geom::Point a, Geom::Point b, Geom::Point c ) {
65
return( 0.5 * fabs( ( a[X]*(b[Y]-c[Y]) + b[X]*(c[Y]-a[Y]) + c[X]*(a[Y]-b[Y]) ) ) );
68
// Alternative touching circle routine directly using Beziers. Works only at end points.
69
static Circle touching_circle( CubicBezier const &curve, bool start ) {
75
double distance = Geom::distance( curve[1], curve[0] );
76
k = 4.0/3.0 * area( curve[0], curve[1], curve[2] ) /
77
(distance * distance * distance);
78
if( Geom::cross(curve[0]-curve[1], curve[1]-curve[2]) < 0 ) {
82
normal = Geom::Point(curve[1] - curve[0]).cw();
84
// std::cout << "Start k: " << k << " d: " << distance << " normal: " << normal << std::endl;
86
double distance = Geom::distance( curve[3], curve[2] );
87
k = 4.0/3.0 * area( curve[1], curve[2], curve[3] ) /
88
(distance * distance * distance);
89
if( Geom::cross(curve[1]-curve[2], curve[2]-curve[3]) < 0 ) {
93
normal = Geom::Point(curve[3] - curve[2]).cw();
95
// std::cout << "End k: " << k << " d: " << distance << " normal: " << normal << std::endl;
98
return Geom::Circle( Geom::Point(0,std::numeric_limits<float>::infinity()),
99
std::numeric_limits<float>::infinity());
102
Geom::Point center = p + normal * radius;
103
return Geom::Circle( center, fabs(radius) );
179
void extrapolate_join(join_data jd)
232
// Arcs line join. If two circles don't intersect, expand inner circle.
233
Geom::Point expand_circle( Geom::Circle &inner_circle, Geom::Circle const &outer_circle, Geom::Point const &start_pt, Geom::Point const &start_tangent ) {
234
// std::cout << "expand_circle:" << std::endl;
235
// std::cout << " outer_circle: radius: " << outer_circle.radius() << " center: " << outer_circle.center() << std::endl;
236
// std::cout << " start: point: " << start_pt << " tangent: " << start_tangent << std::endl;
238
if( !(outer_circle.contains(start_pt) ) ) {
239
// std::cout << " WARNING: Outer circle does not contain starting point!" << std::endl;
240
return Geom::Point(0,0);
243
Geom::Line secant1(start_pt, start_pt + start_tangent);
244
std::vector<Geom::ShapeIntersection> chord1_pts = outer_circle.intersect(secant1);
245
// std::cout << " chord1: " << chord1_pts[0].point() << ", " << chord1_pts[1].point() << std::endl;
246
Geom::LineSegment chord1(chord1_pts[0].point(), chord1_pts[1].point());
248
Geom::Line bisector = make_bisector_line( chord1 );
249
std::vector<Geom::ShapeIntersection> chord2_pts = outer_circle.intersect(bisector);
250
// std::cout << " chord2: " << chord2_pts[0].point() << ", " << chord2_pts[1].point() << std::endl;
251
Geom::LineSegment chord2(chord2_pts[0].point(), chord2_pts[1].point());
253
// Find D, point on chord2 and on circle closest to start point
254
Geom::Coord d0 = Geom::distance(chord2_pts[0].point(),start_pt);
255
Geom::Coord d1 = Geom::distance(chord2_pts[1].point(),start_pt);
256
// std::cout << " d0: " << d0 << " d1: " << d1 << std::endl;
257
Geom::Point d = (d0 < d1) ? chord2_pts[0].point() : chord2_pts[1].point();
258
Geom::Line da(d,start_pt);
260
// Chord through start point and point D
261
std::vector<Geom::ShapeIntersection> chord3_pts = outer_circle.intersect(da);
262
// std::cout << " chord3: " << chord3_pts[0].point() << ", " << chord3_pts[1].point() << std::endl;
264
// Find farthest point on chord3 and on circle (could be more robust)
265
Geom::Coord d2 = Geom::distance(chord3_pts[0].point(),d);
266
Geom::Coord d3 = Geom::distance(chord3_pts[1].point(),d);
267
// std::cout << " d2: " << d2 << " d3: " << d3 << std::endl;
269
// Find point P, the intersection of outer circle and new inner circle
270
Geom::Point p = (d2 > d3) ? chord3_pts[0].point() : chord3_pts[1].point();
272
// Find center of new circle: it is at the intersection of the bisector
273
// of the chord defined by the start point and point P and a line through
274
// the start point and parallel to the first bisector.
275
Geom::LineSegment chord4(start_pt,p);
276
Geom::Line bisector2 = make_bisector_line( chord4 );
277
Geom::Line diameter = make_parallel_line( start_pt, bisector );
278
std::vector<Geom::ShapeIntersection> center_new = bisector2.intersect( diameter );
279
// std::cout << " center_new: " << center_new[0].point() << std::endl;
280
Geom::Coord r_new = Geom::distance( center_new[0].point(), start_pt );
281
// std::cout << " r_new: " << r_new << std::endl;
283
inner_circle.setCenter( center_new[0].point() );
284
inner_circle.setRadius( r_new );
288
// Arcs line join. If two circles don't intersect, adjust both circles so they just touch.
289
// Increase (decrease) the radius of circle 1 and decrease (increase) of circle 2 by the same amount keeping the given points and tangents fixed.
290
Geom::Point adjust_circles( Geom::Circle &circle1, Geom::Circle &circle2, Geom::Point const &point1, Geom::Point const &point2, Geom::Point const &tan1, Geom::Point const &tan2 ) {
292
Geom::Point n1 = (circle1.center() - point1).normalized(); // Always points towards center
293
Geom::Point n2 = (circle2.center() - point2).normalized();
294
Geom::Point sum_n = n1 + n2;
296
double r1 = circle1.radius();
297
double r2 = circle2.radius();
298
double delta_r = r2 - r1;
299
Geom::Point c1 = circle1.center();
300
Geom::Point c2 = circle2.center();
301
Geom::Point delta_c = c2 - c1;
303
// std::cout << "adjust_circles:" << std::endl;
304
// std::cout << " norm: " << n1 << "; " << n2 << std::endl;
305
// std::cout << " sum_n: " << sum_n << std::endl;
306
// std::cout << " delta_r: " << delta_r << std::endl;
307
// std::cout << " delta_c: " << delta_c << std::endl;
309
// Quadratic equation
310
double A = 4 - sum_n.length() * sum_n.length();
311
double B = 4.0 * delta_r - 2.0 * Geom::dot( delta_c, sum_n );
312
double C = delta_r * delta_r - delta_c.length() * delta_c.length();
317
if( fabs(A) < 0.01 ) {
318
// std::cout << " A near zero! $$$$$$$$$$$$$$$$$$" << std::endl;
324
s1 = (-B + sqrt(B*B - 4*A*C))/(2*A);
325
s2 = (-B - sqrt(B*B - 4*A*C))/(2*A);
328
double dr = (fabs(s1)<=fabs(s2)?s1:s2);
330
// std::cout << " A: " << A << std::endl;
331
// std::cout << " B: " << B << std::endl;
332
// std::cout << " C: " << C << std::endl;
333
// std::cout << " s1: " << s1 << " s2: " << s2 << " dr: " << dr << std::endl;
335
circle1 = Geom::Circle( c1 - dr*n1, r1-dr );
336
circle2 = Geom::Circle( c2 + dr*n2, r2+dr );
338
// std::cout << " C1: " << circle1 << std::endl;
339
// std::cout << " C2: " << circle2 << std::endl;
340
// std::cout << " d': " << Geom::Point( circle1.center() - circle2.center() ).length() << std::endl;
342
Geom::Line bisector( circle1.center(), circle2.center() );
343
std::vector<Geom::ShapeIntersection> points = circle1.intersect( bisector );
344
Geom::Point p0 = points[0].point();
345
Geom::Point p1 = points[1].point();
346
// std::cout << " points: " << p0 << "; " << p1 << std::endl;
347
if( abs( Geom::distance( p0, circle2.center() ) - circle2.radius() ) <
348
abs( Geom::distance( p1, circle2.center() ) - circle2.radius() ) ) {
355
void extrapolate_join_internal(join_data jd, int alternative)
357
// std::cout << "\nextrapolate_join: entrance: alternative: " << alternative << std::endl;
181
358
using namespace Geom;
183
360
Geom::Path &res = jd.res;
187
364
Geom::Point endPt = outgoing.initialPoint();
188
365
Geom::Point tang1 = jd.in_tang;
189
366
Geom::Point tang2 = jd.out_tang;
367
// width is half stroke-width
190
368
double width = jd.width, miter = jd.miter;
192
Geom::Circle circle1 = Geom::touching_circle(Geom::reverse(incoming.toSBasis()), 0.);
193
Geom::Circle circle2 = Geom::touching_circle(outgoing.toSBasis(), 0);
370
// std::cout << " startPt: " << startPt << " endPt: " << endPt << std::endl;
371
// std::cout << " tang1: " << tang1 << " tang2: " << tang2 << std::endl;
372
// std::cout << " dot product: " << Geom::dot( tang1, tang2 ) << std::endl;
373
// std::cout << " width: " << width << std::endl;
375
// CIRCLE CALCULATION TESTING
376
Geom::Circle circle1 = touching_circle(Geom::reverse(incoming.toSBasis()), 0.);
377
Geom::Circle circle2 = touching_circle(outgoing.toSBasis(), 0);
378
// std::cout << " circle1: " << circle1 << std::endl;
379
// std::cout << " circle2: " << circle2 << std::endl;
380
if( Geom::CubicBezier const * in_bezier = dynamic_cast<Geom::CubicBezier const*>(&incoming) ) {
381
Geom::Circle circle_test1 = touching_circle(*in_bezier, false);
382
if( !Geom::are_near( circle1, circle_test1, 0.01 ) ) {
383
// std::cout << " Circle 1 error!!!!!!!!!!!!!!!!!" << std::endl;
384
// std::cout << " " << circle_test1 << std::endl;
387
if( Geom::CubicBezier const * out_bezier = dynamic_cast<Geom::CubicBezier const*>(&outgoing) ) {
388
Geom::Circle circle_test2 = touching_circle(*out_bezier, true);
389
if( !Geom::are_near( circle2, circle_test2, 0.01 ) ) {
390
// std::cout << " Circle 2 error!!!!!!!!!!!!!!!!!" << std::endl;
391
// std::cout << " " << circle_test2 << std::endl;
396
Geom::Point center1 = circle1.center();
397
Geom::Point center2 = circle2.center();
398
double side1 = tang1[Geom::X]*(startPt[Geom::Y]-center1[Geom::Y]) - tang1[Geom::Y]*(startPt[Geom::X]-center1[Geom::X]);
399
double side2 = tang2[Geom::X]*( endPt[Geom::Y]-center2[Geom::Y]) - tang2[Geom::Y]*( endPt[Geom::X]-center2[Geom::X]);
400
// std::cout << " side1: " << side1 << " side2: " << side2 << std::endl;
195
402
bool inc_ls = !circle1.center().isFinite();
196
403
bool out_ls = !circle2.center().isFinite();
200
407
Geom::EllipticalArc *arc1 = NULL;
201
408
Geom::EllipticalArc *arc2 = NULL;
409
Geom::LineSegment *seg1 = NULL;
410
Geom::LineSegment *seg2 = NULL;
206
415
if (!inc_ls && !out_ls) {
416
// std::cout << " two circles" << std::endl;
418
// See if tangent is backwards (radius < width/2 and circle is inside stroke).
419
Geom::Point node_on_path = startPt + Geom::rot90(tang1)*width;
420
// std::cout << " node_on_path: " << node_on_path << " -------------- " << std::endl;
423
if (circle1.radius() < width && distance( circle1.center(), node_on_path ) < width) {
426
if (circle2.radius() < width && distance( circle2.center(), node_on_path ) < width) {
429
// std::cout << " b1: " << (b1?"true":"false")
430
// << " b2: " << (b2?"true":"false") << std::endl;
208
433
points = circle1.intersect(circle2);
435
if (points.size() != 2) {
436
// std::cout << " Circles do not intersect, do backup" << std::endl;
437
switch (alternative) {
440
// Fallback to round if one path has radius smaller than half line width.
442
// std::cout << "At one least path has radius smaller than half line width." << std::endl;
443
return( round_join(jd) );
447
if( circle2.contains( startPt ) && !circle1.contains( endPt ) ) {
448
// std::cout << "Expand circle1" << std::endl;
449
p = expand_circle( circle1, circle2, startPt, tang1 );
450
points.push_back( ShapeIntersection( 0, 0, p) );
451
points.push_back( ShapeIntersection( 0, 0, p) );
452
} else if( circle1.contains( endPt ) && !circle2.contains( startPt ) ) {
453
// std::cout << "Expand circle2" << std::endl;
454
p = expand_circle( circle2, circle1, endPt, tang2 );
455
points.push_back( ShapeIntersection( 0, 0, p) );
456
points.push_back( ShapeIntersection( 0, 0, p) );
458
// std::cout << "Either both points inside or both outside" << std::endl;
459
return( miter_clip_join(jd) );
466
// Fallback to round if one path has radius smaller than half line width.
468
// std::cout << "At one least path has radius smaller than half line width." << std::endl;
469
return( round_join(jd) );
472
if( ( circle2.contains( startPt ) && !circle1.contains( endPt ) ) ||
473
( circle1.contains( endPt ) && !circle2.contains( startPt ) ) ) {
475
Geom::Point apex = adjust_circles( circle1, circle2, startPt, endPt, tang1, tang2 );
476
points.push_back( ShapeIntersection( 0, 0, apex) );
477
points.push_back( ShapeIntersection( 0, 0, apex) );
479
// std::cout << "Either both points inside or both outside" << std::endl;
480
return( miter_clip_join(jd) );
487
Geom::Line secant(startPt, startPt + tang1);
488
points = circle2.intersect(secant);
489
circle1.setRadius(std::numeric_limits<float>::infinity());
490
circle1.setCenter(Geom::Point(0,std::numeric_limits<float>::infinity()));
492
Geom::Line secant(endPt, endPt + tang2);
493
points = circle1.intersect(secant);
494
circle2.setRadius(std::numeric_limits<float>::infinity());
495
circle2.setCenter(Geom::Point(0,std::numeric_limits<float>::infinity()));
209
507
if (points.size() == 2) {
210
508
sol = pick_solution(points, tang2, endPt);
211
arc1 = circle1.arc(startPt, 0.5*(startPt+sol), sol);
212
arc2 = circle2.arc(sol, 0.5*(sol+endPt), endPt);
509
if( circle1.radius() != std::numeric_limits<float>::infinity() ) {
510
arc1 = circle1.arc(startPt, 0.5*(startPt+sol), sol);
512
seg1 = new Geom::LineSegment(startPt, sol);
514
if( circle2.radius() != std::numeric_limits<float>::infinity() ) {
515
arc2 = circle2.arc(sol, 0.5*(sol+endPt), endPt);
517
seg2 = new Geom::LineSegment(sol, endPt);
214
520
} else if (inc_ls && !out_ls) {
215
521
// Line and circle
522
// std::cout << " line circle" << std::endl;
216
523
points = circle2.intersect(Line(incoming.initialPoint(), incoming.finalPoint()));
217
524
if (points.size() == 2) {
218
525
sol = pick_solution(points, tang2, endPt);