1 /****************************************************************************
2 **
3 ** This file is part of the LibreCAD project, a 2D CAD program
4 **
5 ** Copyright (C) 2015 A. Stebich (librecad@mail.lordofbikes.de)
6 ** Copyright (C) 2010 R. van Twisk (librecad@rvt.dds.nl)
7 ** Copyright (C) 2001-2003 RibbonSoft. All rights reserved.
8 **
9 **
10 ** This file may be distributed and/or modified under the terms of the
11 ** GNU General Public License version 2 as published by the Free Software
12 ** Foundation and appearing in the file gpl-2.0.txt included in the
13 ** packaging of this file.
14 **
15 ** This program is distributed in the hope that it will be useful,
16 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
17 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 ** GNU General Public License for more details.
19 **
20 ** You should have received a copy of the GNU General Public License
21 ** along with this program; if not, write to the Free Software
22 ** Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
23 **
24 ** This copyright notice MUST APPEAR in all copies of the script!
25 **
26 **********************************************************************/
27
28 #include <vector>
29 #include "rs_information.h"
30 #include "rs_entitycontainer.h"
31 #include "rs_vector.h"
32
33 #include "rs_arc.h"
34 #include "rs_circle.h"
35 #include "rs_constructionline.h"
36 #include "rs_ellipse.h"
37 #include "rs_line.h"
38 #include "rs_polyline.h"
39 #include "lc_quadratic.h"
40 #include "lc_splinepoints.h"
41 #include "rs_math.h"
42 #include "lc_rect.h"
43 #include "rs_debug.h"
44
45 /**
46 * Default constructor.
47 *
48 * @param container The container to which we will add
49 * entities. Usually that's an RS_Graphic entity but
50 * it can also be a polyline, text, ...
51 */
RS_Information(RS_EntityContainer & container)52 RS_Information::RS_Information(RS_EntityContainer& container):
53 container(&container)
54 {
55 }
56
57
58
59 /**
60 * @return true: if the entity is a dimensioning entity.
61 * false: otherwise
62 */
isDimension(RS2::EntityType type)63 bool RS_Information::isDimension(RS2::EntityType type) {
64 switch(type){
65 case RS2::EntityDimAligned:
66 case RS2::EntityDimLinear:
67 case RS2::EntityDimRadial:
68 case RS2::EntityDimDiametric:
69 case RS2::EntityDimAngular:
70 return true;
71 default:
72 return false;
73 }
74 }
75
76
77
78 /**
79 * @retval true the entity can be trimmed.
80 * i.e. it is in a graphic or in a polyline.
81 */
isTrimmable(RS_Entity * e)82 bool RS_Information::isTrimmable(RS_Entity* e) {
83 if (e) {
84 if (e->getParent()) {
85 switch(e->getParent()->rtti()){
86 case RS2::EntityPolyline:
87 case RS2::EntityContainer:
88 case RS2::EntityGraphic:
89 case RS2::EntityBlock:
90 return true;
91 default:
92 return false;
93 }
94 }
95 }
96
97 return false;
98 }
99
100
101 /**
102 * @retval true the two entities can be trimmed to each other;
103 * i.e. they are in a graphic or in the same polyline.
104 */
isTrimmable(RS_Entity * e1,RS_Entity * e2)105 bool RS_Information::isTrimmable(RS_Entity* e1, RS_Entity* e2) {
106 if (e1 && e2) {
107 if (e1->getParent() && e2->getParent()) {
108 if (e1->getParent()->rtti()==RS2::EntityPolyline &&
109 e2->getParent()->rtti()==RS2::EntityPolyline &&
110 e1->getParent()==e2->getParent()) {
111
112 // in the same polyline
113 RS_Polyline* pl = static_cast<RS_Polyline *>(e1->getParent());
114 int idx1 = pl->findEntity(e1);
115 int idx2 = pl->findEntity(e2);
116 RS_DEBUG->print("RS_Information::isTrimmable: "
117 "idx1: %d, idx2: %d", idx1, idx2);
118 if (abs(idx1-idx2)==1 ||
119 (pl->isClosed() && abs(idx1-idx2)==int(pl->count()-1))) {
120 // directly following entities
121 return true;
122 }
123 else {
124 // not directly following entities
125 return false;
126 }
127 }
128 else if ((e1->getParent()->rtti()==RS2::EntityContainer ||
129 e1->getParent()->rtti()==RS2::EntityGraphic ||
130 e1->getParent()->rtti()==RS2::EntityBlock) &&
131 (e2->getParent()->rtti()==RS2::EntityContainer ||
132 e2->getParent()->rtti()==RS2::EntityGraphic ||
133 e2->getParent()->rtti()==RS2::EntityBlock)) {
134
135 // normal entities:
136 return true;
137 }
138 }
139 else {
140 // independent entities with the same parent:
141 return (e1->getParent()==e2->getParent());
142 }
143 }
144
145 return false;
146 }
147
148
149 /**
150 * Gets the nearest end point to the given coordinate.
151 *
152 * @param coord Coordinate (typically a mouse coordinate)
153 *
154 * @return the coordinate found or an invalid vector
155 * if there are no elements at all in this graphics
156 * container.
157 */
getNearestEndpoint(const RS_Vector & coord,double * dist) const158 RS_Vector RS_Information::getNearestEndpoint(const RS_Vector& coord,
159 double* dist) const {
160 return container->getNearestEndpoint(coord, dist);
161 }
162
163
164 /**
165 * Gets the nearest point to the given coordinate which is on an entity.
166 *
167 * @param coord Coordinate (typically a mouse coordinate)
168 * @param dist Pointer to a double which will contain the
169 * measured distance after return or nullptr
170 * @param entity Pointer to a pointer which will point to the
171 * entity on which the point is or nullptr
172 *
173 * @return the coordinate found or an invalid vector
174 * if there are no elements at all in this graphics
175 * container.
176 */
getNearestPointOnEntity(const RS_Vector & coord,bool onEntity,double * dist,RS_Entity ** entity) const177 RS_Vector RS_Information::getNearestPointOnEntity(const RS_Vector& coord,
178 bool onEntity,
179 double* dist,
180 RS_Entity** entity) const {
181
182 return container->getNearestPointOnEntity(coord, onEntity, dist, entity);
183 }
184
185
186 /**
187 * Gets the nearest entity to the given coordinate.
188 *
189 * @param coord Coordinate (typically a mouse coordinate)
190 * @param dist Pointer to a double which will contain the
191 * masured distance after return
192 * @param level Level of resolving entities.
193 *
194 * @return the entity found or nullptr if there are no elements
195 * at all in this graphics container.
196 */
getNearestEntity(const RS_Vector & coord,double * dist,RS2::ResolveLevel level) const197 RS_Entity* RS_Information::getNearestEntity(const RS_Vector& coord,
198 double* dist,
199 RS2::ResolveLevel level) const {
200
201 return container->getNearestEntity(coord, dist, level);
202 }
203
204
205
206 /**
207 * Calculates the intersection point(s) between two entities.
208 *
209 * @param onEntities true: only return intersection points which are
210 * on both entities.
211 * false: return all intersection points.
212 *
213 * @todo support more entities
214 *
215 * @return All intersections of the two entities. The tangent flag in
216 * RS_VectorSolutions is set if one intersection is a tangent point.
217 */
getIntersection(RS_Entity const * e1,RS_Entity const * e2,bool onEntities)218 RS_VectorSolutions RS_Information::getIntersection(RS_Entity const* e1,
219 RS_Entity const* e2, bool onEntities) {
220
221 RS_VectorSolutions ret;
222 const double tol = 1.0e-4;
223
224 if (!(e1 && e2) ) {
225 RS_DEBUG->print("RS_Information::getIntersection() for nullptr entities");
226 return ret;
227 }
228 if (e1->getId() == e2->getId()) {
229 RS_DEBUG->print("RS_Information::getIntersection() of the same entity");
230 return ret;
231 }
232
233 // unsupported entities / entity combinations:
234 if (
235 e1->rtti()==RS2::EntityMText || e2->rtti()==RS2::EntityMText ||
236 e1->rtti()==RS2::EntityText || e2->rtti()==RS2::EntityText ||
237 isDimension(e1->rtti()) || isDimension(e2->rtti())) {
238 return ret;
239 }
240
241 if (onEntities && !(e1->isConstruction() || e2->isConstruction())) {
242 // a little check to avoid doing unneeded intersections, an attempt to avoid O(N^2) increasing of checking two-entity information
243 LC_Rect const rect1{e1->getMin(), e1->getMax()};
244 LC_Rect const rect2{e2->getMin(), e2->getMax()};
245
246 if (onEntities && !rect1.intersects(rect2, RS_TOLERANCE)) {
247 return ret;
248 }
249 }
250
251 //avoid intersections between line segments the same spline
252 /* ToDo: 24 Aug 2011, Dongxu Li, if rtti() is not defined for the parent, the following check for splines may still cause segfault */
253 if ( e1->getParent() && e1->getParent() == e2->getParent()) {
254 if ( e1->getParent()->rtti()==RS2::EntitySpline ) {
255 //do not calculate intersections from neighboring lines of a spline
256 if ( abs(e1->getParent()->findEntity(e1) - e1->getParent()->findEntity(e2)) <= 1 ) {
257 return ret;
258 }
259 }
260 }
261
262 if(e1->rtti() == RS2::EntitySplinePoints || e2->rtti() == RS2::EntitySplinePoints)
263 {
264 ret = LC_SplinePoints::getIntersection(e1, e2);
265 }
266 else
267 {
268 // issue #484 , quadratic intersection solver is not robust enough for quadratic-quadratic
269 // TODO, implement a robust algorithm for quadratic based solvers, and detecting entity type
270 // circles/arcs can be removed
271 auto isArc = [](RS_Entity const* e) {
272 auto type = e->rtti();
273 return type == RS2::EntityCircle || type == RS2::EntityArc;
274 };
275
276 if(isArc(e1) && isArc(e2)){
277 //use specialized arc-arc intersection solver
278 ret=getIntersectionArcArc(e1, e2);
279 }else{
280 const auto qf1=e1->getQuadratic();
281 const auto qf2=e2->getQuadratic();
282 ret=LC_Quadratic::getIntersection(qf1,qf2);
283 }
284 }
285 RS_VectorSolutions ret2;
286 for(const RS_Vector& vp: ret){
287 if (!vp.valid) continue;
288 if (onEntities) {
289 //ignore intersections not on entity
290 if (!(
291 (e1->isConstruction(true) || e1->isPointOnEntity(vp, tol)) &&
292 (e2->isConstruction(true) || e2->isPointOnEntity(vp, tol))
293 )
294 ) {
295 // std::cout<<"Ignored intersection "<<vp<<std::endl;
296 // std::cout<<"because: e1->isPointOnEntity(ret.get(i), tol)="<<e1->isPointOnEntity(vp, tol)
297 // <<"\t(e2->isPointOnEntity(ret.get(i), tol)="<<e2->isPointOnEntity(vp, tol)<<std::endl;
298 continue;
299 }
300 }
301 // need to test whether the intersection is tangential
302 RS_Vector direction1=e1->getTangentDirection(vp);
303 RS_Vector direction2=e2->getTangentDirection(vp);
304 if( direction1.valid && direction2.valid && fabs(fabs(direction1.dotP(direction2)) - sqrt(direction1.squared()*direction2.squared())) < sqrt(tol)*tol )
305 ret2.setTangent(true);
306 //TODO, make the following tangential test, nearest test work for all entity types
307
308 // RS_Entity *lpLine = nullptr,
309 // *lpCircle = nullptr;
310 // if( RS2::EntityLine == e1->rtti() && RS2::EntityCircle == e2->rtti()) {
311 // lpLine = e1;
312 // lpCircle = e2;
313 // }
314 // else if( RS2::EntityCircle == e1->rtti() && RS2::EntityLine == e2->rtti()) {
315 // lpLine = e2;
316 // lpCircle = e1;
317 // }
318 // if( nullptr != lpLine && nullptr != lpCircle) {
319 // double dist = 0.0;
320 // RS_Vector nearest = lpLine->getNearestPointOnEntity( lpCircle->getCenter(), false, &dist);
321
322 // // special case: line touches circle tangent
323 // if( nearest.valid && fabs( dist - lpCircle->getRadius()) < tol) {
324 // ret.set(i,nearest);
325 // ret2.setTangent(true);
326 // }
327 // }
328 ret2.push_back(vp);
329 }
330
331 return ret2;
332 }
333
334
335
336 /**
337 * @return Intersection between two lines.
338 */
getIntersectionLineLine(RS_Line * e1,RS_Line * e2)339 RS_VectorSolutions RS_Information::getIntersectionLineLine(RS_Line* e1,
340 RS_Line* e2) {
341
342 RS_VectorSolutions ret;
343
344 if (!(e1 && e2)) {
345 RS_DEBUG->print("RS_Information::getIntersectionLineLin() for nullptr entities");
346 return ret;
347 }
348
349 RS_Vector p1 = e1->getStartpoint();
350 RS_Vector p2 = e1->getEndpoint();
351 RS_Vector p3 = e2->getStartpoint();
352 RS_Vector p4 = e2->getEndpoint();
353
354 double num = ((p4.x-p3.x)*(p1.y-p3.y) - (p4.y-p3.y)*(p1.x-p3.x));
355 double div = ((p4.y-p3.y)*(p2.x-p1.x) - (p4.x-p3.x)*(p2.y-p1.y));
356
357 if (fabs(div)>RS_TOLERANCE &&
358 fabs(remainder(e1->getAngle1()-e2->getAngle1(), M_PI))>=RS_TOLERANCE*10.) {
359 double u = num / div;
360
361 double xs = p1.x + u * (p2.x-p1.x);
362 double ys = p1.y + u * (p2.y-p1.y);
363 ret = RS_VectorSolutions({RS_Vector(xs, ys)});
364 }
365
366 // lines are parallel
367 else {
368 ret = RS_VectorSolutions();
369 }
370
371 return ret;
372 }
373
374
375
376 /**
377 * @return One or two intersection points between given entities.
378 */
getIntersectionLineArc(RS_Line * line,RS_Arc * arc)379 RS_VectorSolutions RS_Information::getIntersectionLineArc(RS_Line* line,
380 RS_Arc* arc) {
381
382 RS_VectorSolutions ret;
383
384 if (!(line && arc)) return ret;
385
386 double dist=0.0;
387 RS_Vector nearest;
388 nearest = line->getNearestPointOnEntity(arc->getCenter(), false, &dist);
389
390 // special case: arc touches line (tangent):
391 if (nearest.valid && fabs(dist - arc->getRadius()) < 1.0e-4) {
392 ret = RS_VectorSolutions({nearest});
393 ret.setTangent(true);
394 return ret;
395 }
396
397 RS_Vector p = line->getStartpoint();
398 RS_Vector d = line->getEndpoint() - line->getStartpoint();
399 double d2=d.squared();
400 RS_Vector c = arc->getCenter();
401 double r = arc->getRadius();
402 RS_Vector delta = p - c;
403 if (d2<RS_TOLERANCE2) {
404 //line too short, still check the whether the line touches the arc
405 if ( fabs(delta.squared() - r*r) < 2.*RS_TOLERANCE*r ){
406 return RS_VectorSolutions({line->getMiddlePoint()});
407 }
408 return ret;
409 }
410
411
412 //intersection
413 // solution = p + t d;
414 //| p -c+ t d|^2 = r^2
415 // |d|^2 t^2 + 2 (p-c).d t + |p-c|^2 -r^2 = 0
416 double a1 = RS_Vector::dotP(delta,d);
417 double term1 = a1*a1 - d2*(delta.squared()-r*r);
418 // std::cout<<" discriminant= "<<term1<<std::endl;
419 if( term1 < - RS_TOLERANCE) {
420 // std::cout<<"no intersection\n";
421 return ret;
422 }else{
423 term1=fabs(term1);
424 // std::cout<< "term1="<<term1 <<" threshold: "<< RS_TOLERANCE * d2 <<std::endl;
425 if( term1 < RS_TOLERANCE * d2 ) {
426 //tangential;
427 // ret=RS_VectorSolutions(p - d*(a1/d2));
428 ret=RS_VectorSolutions({line->getNearestPointOnEntity(c, false)});
429 ret.setTangent(true);
430 // std::cout<<"Tangential point: "<<ret<<std::endl;
431 return ret;
432 }
433 double t = sqrt(fabs(term1));
434 //two intersections
435 return RS_VectorSolutions({ p + d*(t-a1)/d2, p -d*(t+a1)/d2});
436 }
437
438 // // root term:
439 // term1 = r*r - delta.squared() + term1*term1/d.squared();
440 // double term = RS_Math::pow(RS_Vector::dotP(d, delta), 2.0)
441 // - RS_Math::pow(d.magnitude(), 2.0)
442 // * (RS_Math::pow(delta.magnitude(), 2.0) - RS_Math::pow(r, 2.0));
443 // std::cout<<"old term= "<<term<<"\tnew term= "<<term1<<std::endl;
444
445 // // no intersection:
446 // if (term<0.0) {
447 // ret = RS_VectorSolutions() ;
448 // }
449
450 // // one or two intersections:
451 // else {
452 // double t1 = (- RS_Vector::dotP(d, delta) + sqrt(term))
453 // / RS_Math::pow(d.magnitude(), 2.0);
454 // double t2;
455 // bool tangent = false;
456
457 // // only one intersection:
458 // if (fabs(term)<RS_TOLERANCE) {
459 // t2 = t1;
460 // tangent = true;
461 // }
462
463 // // two intersections
464 // else {
465 // t2 = (-RS_Vector::dotP(d, delta) - sqrt(term))
466 // / RS_Math::pow(d.magnitude(), 2.0);
467 // }
468
469 // RS_Vector sol1;
470 // RS_Vector sol2(false);
471
472 // sol1 = p + d * t1;
473
474 // if (!tangent) {
475 // sol2 = p + d * t2;
476 // }
477
478 // ret = RS_VectorSolutions(sol1, sol2);
479 // ret.setTangent(tangent);
480 // }
481
482 // std::cout<<"ret= "<<ret<<std::endl;
483 // return ret;
484 }
485
486
487
488 /**
489 * @return One or two intersection points between given entities.
490 */
getIntersectionArcArc(RS_Entity const * e1,RS_Entity const * e2)491 RS_VectorSolutions RS_Information::getIntersectionArcArc(RS_Entity const* e1,
492 RS_Entity const* e2) {
493
494 RS_VectorSolutions ret;
495
496 if (!(e1 && e2)) return ret;
497
498 if(e1->rtti() != RS2::EntityArc && e1->rtti() != RS2::EntityCircle)
499 return ret;
500 if(e2->rtti() != RS2::EntityArc && e2->rtti() != RS2::EntityCircle)
501 return ret;
502
503 RS_Vector c1 = e1->getCenter();
504 RS_Vector c2 = e2->getCenter();
505
506 double r1 = e1->getRadius();
507 double r2 = e2->getRadius();
508
509 RS_Vector u = c2 - c1;
510
511 // concentric
512 if (u.magnitude()<1.0e-6) {
513 return ret;
514 }
515
516 RS_Vector v = RS_Vector(u.y, -u.x);
517
518 double s, t1, t2, term;
519
520 s = 1.0/2.0 * ((r1*r1 - r2*r2)/(RS_Math::pow(u.magnitude(), 2.0)) + 1.0);
521
522 term = (r1*r1)/(RS_Math::pow(u.magnitude(), 2.0)) - s*s;
523
524 // no intersection:
525 if (term<0.0) {
526 ret = RS_VectorSolutions();
527 }
528
529 // one or two intersections:
530 else {
531 t1 = sqrt(term);
532 t2 = -sqrt(term);
533 bool tangent = false;
534
535 RS_Vector sol1 = c1 + u*s + v*t1;
536 RS_Vector sol2 = c1 + u*s + v*t2;
537
538 if (sol1.distanceTo(sol2)<1.0e-4) {
539 sol2 = RS_Vector(false);
540 ret = RS_VectorSolutions({sol1});
541 tangent = true;
542 } else {
543 ret = RS_VectorSolutions({sol1, sol2});
544 }
545
546 ret.setTangent(tangent);
547 }
548
549 return ret;
550 }
551
552 // find intersections between ellipse/arc/circle using quartic equation solver
553 //
554 // @author Dongxu Li <dongxuli2011@gmail.com>
555 //
556
getIntersectionEllipseEllipse(RS_Ellipse const * e1,RS_Ellipse const * e2)557 RS_VectorSolutions RS_Information::getIntersectionEllipseEllipse(
558 RS_Ellipse const* e1, RS_Ellipse const* e2) {
559 RS_VectorSolutions ret;
560
561 if (!(e1 && e2) ) {
562 return ret;
563 }
564 if (
565 (e1->getCenter() - e2 ->getCenter()).squared() < RS_TOLERANCE2 &&
566 (e1->getMajorP() - e2 ->getMajorP()).squared() < RS_TOLERANCE2 &&
567 fabs(e1->getRatio() - e2 ->getRatio()) < RS_TOLERANCE
568 ) { // overlapped ellipses, do not do overlap
569 return ret;
570 }
571 RS_Ellipse ellipse01(nullptr,e1->getData());
572
573 RS_Ellipse *e01= & ellipse01;
574 if( e01->getMajorRadius() < e01->getMinorRadius() ) e01->switchMajorMinor();
575 RS_Ellipse ellipse02(nullptr,e2->getData());
576 RS_Ellipse *e02= &ellipse02;
577 if( e02->getMajorRadius() < e02->getMinorRadius() ) e02->switchMajorMinor();
578 //transform ellipse2 to ellipse1's coordinates
579 RS_Vector shiftc1=- e01->getCenter();
580 double shifta1=-e01->getAngle();
581 e02->move(shiftc1);
582 e02->rotate(shifta1);
583 // RS_Vector majorP2=e02->getMajorP();
584 double a1=e01->getMajorRadius();
585 double b1=e01->getMinorRadius();
586 double x2=e02->getCenter().x,
587 y2=e02->getCenter().y;
588 double a2=e02->getMajorRadius();
589 double b2=e02->getMinorRadius();
590
591 if( e01->getMinorRadius() < RS_TOLERANCE || e01 -> getRatio()< RS_TOLERANCE) {
592 // treat e01 as a line
593 RS_Line line{e1->getParent(), {{-a1,0.}, {a1,0.}}};
594 ret= getIntersectionEllipseLine(&line, e02);
595 ret.rotate(-shifta1);
596 ret.move(-shiftc1);
597 return ret;
598 }
599 if( e02->getMinorRadius() < RS_TOLERANCE || e02 -> getRatio()< RS_TOLERANCE) {
600 // treat e02 as a line
601 RS_Line line{e1->getParent(), {{-a2,0.}, {a2,0.}}};
602 line.rotate({0.,0.}, e02->getAngle());
603 line.move(e02->getCenter());
604 ret = getIntersectionEllipseLine(&line, e01);
605 ret.rotate(-shifta1);
606 ret.move(-shiftc1);
607 return ret;
608 }
609
610 //ellipse01 equation:
611 // x^2/(a1^2) + y^2/(b1^2) - 1 =0
612 double t2= - e02->getAngle();
613 //ellipse2 equation:
614 // ( (x - u) cos(t) - (y - v) sin(t))^2/a^2 + ( (x - u) sin(t) + (y-v) cos(t))^2/b^2 =1
615 // ( cos^2/a^2 + sin^2/b^2) x^2 +
616 // ( sin^2/a^2 + cos^2/b^2) y^2 +
617 // 2 sin cos (1/b^2 - 1/a^2) x y +
618 // ( ( 2 v sin cos - 2 u cos^2)/a^2 - ( 2v sin cos + 2 u sin^2)/b^2) x +
619 // ( ( 2 u sin cos - 2 v sin^2)/a^2 - ( 2u sin cos + 2 v cos^2)/b^2) y +
620 // (u cos - v sin)^2/a^2 + (u sin + v cos)^2/b^2 -1 =0
621 // detect whether any ellipse radius is zero
622 double cs=cos(t2),si=sin(t2);
623 double ucs=x2*cs,usi=x2*si,
624 vcs=y2*cs,vsi=y2*si;
625 double cs2=cs*cs,si2=1-cs2;
626 double tcssi=2.*cs*si;
627 double ia2=1./(a2*a2),ib2=1./(b2*b2);
628 std::vector<double> m(0,0.);
629 m.push_back( 1./(a1*a1)); //ma000
630 m.push_back( 1./(b1*b1)); //ma011
631 m.push_back(cs2*ia2 + si2*ib2); //ma100
632 m.push_back(cs*si*(ib2 - ia2)); //ma101
633 m.push_back(si2*ia2 + cs2*ib2); //ma111
634 m.push_back(( y2*tcssi - 2.*x2*cs2)*ia2 - ( y2*tcssi+2*x2*si2)*ib2); //mb10
635 m.push_back( ( x2*tcssi - 2.*y2*si2)*ia2 - ( x2*tcssi+2*y2*cs2)*ib2); //mb11
636 m.push_back((ucs - vsi)*(ucs-vsi)*ia2+(usi+vcs)*(usi+vcs)*ib2 -1.); //mc1
637 auto vs0=RS_Math::simultaneousQuadraticSolver(m);
638 shifta1 = - shifta1;
639 shiftc1 = - shiftc1;
640 for(RS_Vector vp: vs0){
641 vp.rotate(shifta1);
642 vp.move(shiftc1);
643 ret.push_back(vp);
644 }
645 return ret;
646 }
647
648 //wrapper to do Circle-Ellipse and Arc-Ellipse using Ellipse-Ellipse intersection
getIntersectionCircleEllipse(RS_Circle * c1,RS_Ellipse * e1)649 RS_VectorSolutions RS_Information::getIntersectionCircleEllipse(RS_Circle* c1,
650 RS_Ellipse* e1) {
651 RS_VectorSolutions ret;
652 if (!(c1 && e1)) return ret;
653
654 RS_Ellipse const e2{c1->getParent(),
655 {c1->getCenter(), {c1->getRadius(),0.},
656 1.0,
657 0., 2.*M_PI,
658 false}};
659 return getIntersectionEllipseEllipse(e1, &e2);
660 }
661
getIntersectionArcEllipse(RS_Arc * a1,RS_Ellipse * e1)662 RS_VectorSolutions RS_Information::getIntersectionArcEllipse(RS_Arc * a1,
663 RS_Ellipse* e1) {
664 RS_VectorSolutions ret;
665 if (!(a1 && e1)) {
666 return ret;
667 }
668 RS_Ellipse const e2{a1->getParent(),
669 {a1->getCenter(),
670 {a1->getRadius(), 0.},
671 1.0,
672 a1->getAngle1(), a1->getAngle2(),
673 a1->isReversed()}};
674 return getIntersectionEllipseEllipse(e1, &e2);
675 }
676
677
678
679
680
681 /**
682 * @return One or two intersection points between given entities.
683 */
getIntersectionEllipseLine(RS_Line * line,RS_Ellipse * ellipse)684 RS_VectorSolutions RS_Information::getIntersectionEllipseLine(RS_Line* line,
685 RS_Ellipse* ellipse) {
686
687 RS_VectorSolutions ret;
688
689 if (!(line && ellipse)) return ret;
690
691 // rotate into normal position:
692
693 double rx = ellipse->getMajorRadius();
694 if(rx<RS_TOLERANCE) {
695 //zero radius ellipse
696 RS_Vector vp(line->getNearestPointOnEntity(ellipse->getCenter(), true));
697 if((vp-ellipse->getCenter()).squared() <RS_TOLERANCE2){
698 //center on line
699 ret.push_back(vp);
700 }
701 return ret;
702 }
703 RS_Vector angleVector = ellipse->getMajorP().scale(RS_Vector(1./rx,-1./rx));
704 double ry = rx*ellipse->getRatio();
705 RS_Vector center = ellipse->getCenter();
706 RS_Vector a1 = line->getStartpoint().rotate(center, angleVector);
707 RS_Vector a2 = line->getEndpoint().rotate(center, angleVector);
708 // RS_Vector origin = a1;
709 RS_Vector dir = a2-a1;
710 RS_Vector diff = a1 - center;
711 RS_Vector mDir = RS_Vector(dir.x/(rx*rx), dir.y/(ry*ry));
712 RS_Vector mDiff = RS_Vector(diff.x/(rx*rx), diff.y/(ry*ry));
713
714 double a = RS_Vector::dotP(dir, mDir);
715 double b = RS_Vector::dotP(dir, mDiff);
716 double c = RS_Vector::dotP(diff, mDiff) - 1.0;
717 double d = b*b - a*c;
718
719 // std::cout<<"RS_Information::getIntersectionEllipseLine(): d="<<d<<std::endl;
720 if (d < - 1.e3*RS_TOLERANCE*sqrt(RS_TOLERANCE)) {
721 RS_DEBUG->print("RS_Information::getIntersectionLineEllipse: outside 0");
722 return ret;
723 }
724 if( d < 0. ) d=0.;
725 double root = sqrt(d);
726 double t_a = -b/a;
727 double t_b = root/a;
728 // double t_b = (-b + root) / a;
729
730 ret.push_back(a1.lerp(a2,t_a+t_b));
731 RS_Vector vp(a1.lerp(a2,t_a-t_b));
732 if ( (ret.get(0)-vp).squared()>RS_TOLERANCE2) {
733 ret.push_back(vp);
734 }
735 angleVector.y *= -1.;
736 ret.rotate(center, angleVector);
737 // std::cout<<"found Ellipse-Line intersections: "<<ret.getNumber()<<std::endl;
738 // std::cout<<ret<<std::endl;
739 RS_DEBUG->print("RS_Information::getIntersectionEllipseLine(): done");
740 return ret;
741 }
742
743
744 /**
745 * Checks if the given coordinate is inside the given contour.
746 *
747 * @param point Coordinate to check.
748 * @param contour One or more entities which shape a contour.
749 * If the given contour is not closed, the result is undefined.
750 * The entities don't need to be in a specific order.
751 * @param onContour Will be set to true if the given point it exactly
752 * on the contour.
753 */
isPointInsideContour(const RS_Vector & point,RS_EntityContainer * contour,bool * onContour)754 bool RS_Information::isPointInsideContour(const RS_Vector& point,
755 RS_EntityContainer* contour, bool* onContour) {
756
757 if (!contour) {
758 RS_DEBUG->print(RS_Debug::D_WARNING,
759 "RS_Information::isPointInsideContour: contour is nullptr");
760 return false;
761 }
762
763 if (point.x < contour->getMin().x || point.x > contour->getMax().x ||
764 point.y < contour->getMin().y || point.y > contour->getMax().y) {
765 return false;
766 }
767
768 double width = contour->getSize().x+1.0;
769
770 bool sure;
771 int counter;
772 int tries = 0;
773 double rayAngle = 0.0;
774 do {
775 sure = true;
776
777 // create ray:
778 RS_Vector v = RS_Vector::polar(width*10.0, rayAngle);
779 RS_Line ray{point, point+v};
780 counter = 0;
781 RS_VectorSolutions sol;
782
783 if (onContour) {
784 *onContour = false;
785 }
786
787 for (RS_Entity* e = contour->firstEntity(RS2::ResolveAll);
788 e;
789 e = contour->nextEntity(RS2::ResolveAll)) {
790
791 // intersection(s) from ray with contour entity:
792 sol = RS_Information::getIntersection(&ray, e, true);
793
794 for (int i=0; i<=1; ++i) {
795 RS_Vector p = sol.get(i);
796
797 if (p.valid) {
798 // point is on the contour itself
799 if (p.distanceTo(point)<1.0e-5) {
800 if (onContour) {
801 *onContour = true;
802 }
803 } else {
804 if (e->rtti()==RS2::EntityLine) {
805 RS_Line* line = (RS_Line*)e;
806
807 // ray goes through startpoint of line:
808 if (p.distanceTo(line->getStartpoint())<1.0e-4) {
809 if (RS_Math::correctAngle(line->getAngle1())<M_PI) {
810 sure = false;
811 }
812 }
813
814 // ray goes through endpoint of line:
815 else if (p.distanceTo(line->getEndpoint())<1.0e-4) {
816 if (RS_Math::correctAngle(line->getAngle2())<M_PI) {
817 sure = false;
818 }
819 }
820 // else: ray goes through the line
821
822
823 counter++;
824
825 } else if (e->rtti()==RS2::EntityArc) {
826 RS_Arc* arc = (RS_Arc*)e;
827
828 if (p.distanceTo(arc->getStartpoint())<1.0e-4) {
829 double dir = arc->getDirection1();
830 if ((dir<M_PI && dir>=1.0e-5) ||
831 ((dir>2*M_PI-1.0e-5 || dir<1.0e-5) &&
832 arc->getCenter().y>p.y)) {
833 counter++;
834 sure = false;
835 }
836 }
837 else if (p.distanceTo(arc->getEndpoint())<1.0e-4) {
838 double dir = arc->getDirection2();
839 if ((dir<M_PI && dir>=1.0e-5) ||
840 ((dir>2*M_PI-1.0e-5 || dir<1.0e-5) &&
841 arc->getCenter().y>p.y)) {
842 counter++;
843 sure = false;
844 }
845 } else {
846 counter++;
847 }
848 } else if (e->rtti()==RS2::EntityCircle) {
849 // tangent:
850 if (i==0 && sol.get(1).valid==false) {
851 if (!sol.isTangent()) {
852 counter++;
853 } else {
854 sure = false;
855 }
856 } else if (i==1 || sol.get(1).valid==true) {
857 counter++;
858 }
859 } else if (e->rtti()==RS2::EntityEllipse) {
860 RS_Ellipse* ellipse=static_cast<RS_Ellipse*>(e);
861 if(ellipse->isArc()){
862 if (p.distanceTo(ellipse->getStartpoint())<1.0e-4) {
863 double dir = ellipse->getDirection1();
864 if ((dir<M_PI && dir>=1.0e-5) ||
865 ((dir>2*M_PI-1.0e-5 || dir<1.0e-5) &&
866 ellipse->getCenter().y>p.y)) {
867 counter++;
868 sure = false;
869 }
870 }
871 else if (p.distanceTo(ellipse->getEndpoint())<1.0e-4) {
872 double dir = ellipse->getDirection2();
873 if ((dir<M_PI && dir>=1.0e-5) ||
874 ((dir>2*M_PI-1.0e-5 || dir<1.0e-5) &&
875 ellipse->getCenter().y>p.y)) {
876 counter++;
877 sure = false;
878 }
879 } else {
880 counter++;
881 }
882 }else{
883 // tangent:
884 if (i==0 && sol.get(1).valid==false) {
885 if (!sol.isTangent()) {
886 counter++;
887 } else {
888 sure = false;
889 }
890 } else if (i==1 || sol.get(1).valid==true) {
891 counter++;
892 }
893 }
894 }
895 }
896 }
897 }
898 }
899
900 rayAngle+=0.02;
901 tries++;
902 }
903 while (!sure && rayAngle<2*M_PI && tries<6);
904
905 // remove double intersections:
906 /*
907 QList<RS_Vector> is2;
908 bool done;
909 RS_Vector* av;
910 do {
911 done = true;
912 double minDist = RS_MAXDOUBLE;
913 double dist;
914 av = nullptr;
915 for (RS_Vector* v = is.first(); v; v = is.next()) {
916 dist = point.distanceTo(*v);
917 if (dist<minDist) {
918 minDist = dist;
919 done = false;
920 av = v;
921 }
922 }
923
924 if (!done && av) {
925 is2.append(*av);
926 }
927 } while (!done);
928 */
929
930 return ((counter%2)==1);
931 }
932
933
createQuadrilateral(const RS_EntityContainer & container)934 RS_VectorSolutions RS_Information::createQuadrilateral(const RS_EntityContainer& container)
935 {
936 RS_VectorSolutions ret;
937 if(container.count()!=4) return ret;
938 RS_EntityContainer c(container);
939 std::vector<RS_Line*> lines;
940 for(auto e: c){
941 if(e->rtti()!=RS2::EntityLine) return ret;
942 lines.push_back(static_cast<RS_Line*>(e));
943 }
944 if(lines.size()!=4) return ret;
945
946 //find intersections
947 std::vector<RS_Vector> vertices;
948 for(auto it=lines.begin()+1; it != lines.end(); ++it){
949 for(auto jt=lines.begin(); jt != it; ++jt){
950 RS_VectorSolutions const& sol=RS_Information::getIntersectionLineLine(*it, *jt);
951 if(sol.size()){
952 vertices.push_back(sol.at(0));
953 }
954 }
955 }
956
957 // std::cout<<"vertices.size()="<<vertices.size()<<std::endl;
958
959 switch (vertices.size()){
960 default:
961 return ret;
962 case 4:
963 break;
964 case 5:
965 case 6:
966 for(RS_Line* pl: lines){
967 const double a0=pl->getDirection1();
968 std::vector<std::vector<RS_Vector>::iterator> left;
969 std::vector<std::vector<RS_Vector>::iterator> right;
970 for(auto it=vertices.begin(); it != vertices.end(); ++it){
971 RS_Vector const& dir=*it - pl->getNearestPointOnEntity(*it, false);
972 if(dir.squared()<RS_TOLERANCE15) continue;
973 // std::cout<<"angle="<<remainder(dir.angle() - a0, 2.*M_PI)<<std::endl;
974 if(remainder(dir.angle() - a0, 2.*M_PI) > 0.)
975 left.push_back(it);
976 else
977 right.push_back(it);
978
979 if(left.size()==2 && right.size()==1){
980 vertices.erase(right[0]);
981 break;
982 } else if(left.size()==1 && right.size()==2){
983 vertices.erase(left[0]);
984 break;
985 }
986 }
987 if(vertices.size()==4) break;
988 }
989 break;
990 }
991
992 //order vertices
993 RS_Vector center{0., 0.};
994 for(const RS_Vector& vp: vertices)
995 center += vp;
996 center *= 0.25;
997 std::sort(vertices.begin(), vertices.end(), [¢er](const RS_Vector& a,
998 const RS_Vector&b)->bool{
999 return center.angleTo(a)<center.angleTo(b);
1000 }
1001 );
1002 for(const RS_Vector& vp: vertices){
1003 ret.push_back(vp);
1004 // std::cout<<"vp="<<vp<<std::endl;
1005 }
1006 return ret;
1007 }
1008