Mercurial > hg > orthanc-stone

comparison UnitTestsSources/ComputationalGeometryTests.cpp @ 1875:b896f20d24ca

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
added UnionOfRectangles algorithm
author Sebastien Jodogne <s.jodogne@gmail.com>
date Tue, 11 Jan 2022 19:59:40 +0100
parents 08f2476e8f5e
children b1f510e601d2
comparison
equal deleted inserted replaced
1874:08f2476e8f5e 1875:b896f20d24ca
23 #include <gtest/gtest.h> 23 #include <gtest/gtest.h>
24 24
25 #include "../OrthancStone/Sources/Toolbox/Internals/OrientedIntegerLine2D.h" 25 #include "../OrthancStone/Sources/Toolbox/Internals/OrientedIntegerLine2D.h"
26 #include "../OrthancStone/Sources/Toolbox/Internals/RectanglesIntegerProjection.h" 26 #include "../OrthancStone/Sources/Toolbox/Internals/RectanglesIntegerProjection.h"
27 #include "../OrthancStone/Sources/Toolbox/SegmentTree.h" 27 #include "../OrthancStone/Sources/Toolbox/SegmentTree.h"
28 #include "../OrthancStone/Sources/Toolbox/UnionOfRectangles.h"
28 29
29 #include <Logging.h> 30 #include <Logging.h>
30 #include <OrthancException.h> 31 #include <OrthancException.h>
31 32
32 33
477 ASSERT_EQ(20u, v[2]); 478 ASSERT_EQ(20u, v[2]);
478 ASSERT_EQ(20u, v[3]); 479 ASSERT_EQ(20u, v[3]);
479 ASSERT_EQ(5u, v[4]); 480 ASSERT_EQ(5u, v[4]);
480 ASSERT_EQ(5u, v[5]); 481 ASSERT_EQ(5u, v[5]);
481 } 482 }
483
484
485 TEST(UnionOfRectangles, Textbook)
486 {
487 // This is Figure 8.12 from textbook
488
489 std::list<OrthancStone::Extent2D> rectangles;
490 rectangles.push_back(OrthancStone::Extent2D(1, 3, 13, 5));
491 rectangles.push_back(OrthancStone::Extent2D(3, 1, 7, 12));
492 rectangles.push_back(OrthancStone::Extent2D(5, 7, 11, 10));
493 rectangles.push_back(OrthancStone::Extent2D(10, 2, 14, 8));
494 rectangles.push_back(OrthancStone::Extent2D(3, 3, 4, 3)); // empty rectangle
495
496 for (unsigned int fillHole = 0; fillHole < 2; fillHole++)
497 {
498 if (fillHole)
499 {
500 rectangles.push_back(OrthancStone::Extent2D(6.5, 4.5, 10.5, 7.5));
501 }
502
503 std::list< std::vector<OrthancStone::ScenePoint2D> > contours;
504 OrthancStone::UnionOfRectangles::Apply(contours, rectangles);
505
506 ASSERT_EQ(fillHole ? 1u : 2u, contours.size());
507 ASSERT_EQ(17u, contours.front().size());
508 ASSERT_TRUE(contours.front()[0].IsEqual(OrthancStone::ScenePoint2D(3, 12)));
509 ASSERT_TRUE(contours.front()[1].IsEqual(OrthancStone::ScenePoint2D(7, 12)));
510 ASSERT_TRUE(contours.front()[2].IsEqual(OrthancStone::ScenePoint2D(7, 10)));
511 ASSERT_TRUE(contours.front()[3].IsEqual(OrthancStone::ScenePoint2D(11, 10)));
512 ASSERT_TRUE(contours.front()[4].IsEqual(OrthancStone::ScenePoint2D(11, 8)));
513 ASSERT_TRUE(contours.front()[5].IsEqual(OrthancStone::ScenePoint2D(14, 8)));
514 ASSERT_TRUE(contours.front()[6].IsEqual(OrthancStone::ScenePoint2D(14, 2)));
515 ASSERT_TRUE(contours.front()[7].IsEqual(OrthancStone::ScenePoint2D(10, 2)));
516 ASSERT_TRUE(contours.front()[8].IsEqual(OrthancStone::ScenePoint2D(10, 3)));
517 ASSERT_TRUE(contours.front()[9].IsEqual(OrthancStone::ScenePoint2D(7, 3)));
518 ASSERT_TRUE(contours.front()[10].IsEqual(OrthancStone::ScenePoint2D(7, 1)));
519 ASSERT_TRUE(contours.front()[11].IsEqual(OrthancStone::ScenePoint2D(3, 1)));
520 ASSERT_TRUE(contours.front()[12].IsEqual(OrthancStone::ScenePoint2D(3, 3)));
521 ASSERT_TRUE(contours.front()[13].IsEqual(OrthancStone::ScenePoint2D(1, 3)));
522 ASSERT_TRUE(contours.front()[14].IsEqual(OrthancStone::ScenePoint2D(1, 5)));
523 ASSERT_TRUE(contours.front()[15].IsEqual(OrthancStone::ScenePoint2D(3, 5)));
524 ASSERT_TRUE(contours.front()[16].IsEqual(OrthancStone::ScenePoint2D(3, 12)));
525
526 if (!fillHole)
527 {
528 ASSERT_EQ(5u, contours.back().size());
529 ASSERT_TRUE(contours.back()[0].IsEqual(OrthancStone::ScenePoint2D(10, 7)));
530 ASSERT_TRUE(contours.back()[1].IsEqual(OrthancStone::ScenePoint2D(7, 7)));
531 ASSERT_TRUE(contours.back()[2].IsEqual(OrthancStone::ScenePoint2D(7, 5)));
532 ASSERT_TRUE(contours.back()[3].IsEqual(OrthancStone::ScenePoint2D(10, 5)));
533 ASSERT_TRUE(contours.back()[4].IsEqual(OrthancStone::ScenePoint2D(10, 7)));
534 }
535 }
536 }
537
538
539 #if 0
540 static void SaveSvg(const std::list< std::vector<OrthancStone::ScenePoint2D> >& contours)
541 {
542 float ww = 15;
543 float hh = 13;
544
545 FILE* fp = fopen("test.svg", "w");
546 fprintf(fp, "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n");
547 fprintf(fp, "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\" \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n");
548 fprintf(fp, "<svg width=\"%f\" height=\"%f\" viewBox=\"0 0 %f %f\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", 100.0f*ww, 100.0f*hh, ww, hh);
549
550 // http://thenewcode.com/1068/Making-Arrows-in-SVG
551 fprintf(fp, "<defs>\n");
552 fprintf(fp, "<marker id=\"arrowhead\" markerWidth=\"2\" markerHeight=\"3\" \n");
553 fprintf(fp, "refX=\"2\" refY=\"1.5\" orient=\"auto\">\n");
554 fprintf(fp, "<polygon points=\"0 0, 2 1.5, 0 3\" />\n");
555 fprintf(fp, "</marker>\n");
556 fprintf(fp, "</defs>\n");
557
558 fprintf(fp, "<rect fill=\"#fff\" stroke=\"#000\" x=\"0\" y=\"0\" width=\"%f\" height=\"%f\"/>\n", ww, hh);
559
560 for (std::list< std::vector<OrthancStone::ScenePoint2D> >::const_iterator
561 it = contours.begin(); it != contours.end(); ++it)
562 {
563 for (size_t i = 0; i + 1 < it->size(); i++)
564 {
565 float x1 = (*it)[i].GetX();
566 float x2 = (*it)[i + 1].GetX();
567 float y1 = (*it)[i].GetY();
568 float y2 = (*it)[i + 1].GetY();
569
570 fprintf(fp, "<line x1=\"%f\" y1=\"%f\" x2=\"%f\" y2=\"%f\" stroke=\"blue\" stroke-width=\"0.05\" marker-end=\"url(#arrowhead)\"/>\n", x1, y1, x2, y2);
571 }
572 }
573 fprintf(fp, "</svg>\n");
574
575 fclose(fp);
576 }
577 #endif
578
579
580 TEST(UnionOfRectangles, Complex)
581 {
582 {
583 std::list<OrthancStone::Extent2D> rectangles;
584 rectangles.push_back(OrthancStone::Extent2D(1, 4, 4, 6));
585 rectangles.push_back(OrthancStone::Extent2D(4, 6, 7, 8));
586 rectangles.push_back(OrthancStone::Extent2D(4, 2, 7, 4));
587 rectangles.push_back(OrthancStone::Extent2D(7, 4, 10, 6));
588
589 std::list< std::vector<OrthancStone::ScenePoint2D> > contours;
590 OrthancStone::UnionOfRectangles::Apply(contours, rectangles);
591
592 ASSERT_EQ(1u, contours.size());
593 ASSERT_EQ(17u, contours.front().size());
594 ASSERT_TRUE(contours.front()[0].IsEqual(OrthancStone::ScenePoint2D(4, 8)));
595 ASSERT_TRUE(contours.front()[1].IsEqual(OrthancStone::ScenePoint2D(7, 8)));
596 ASSERT_TRUE(contours.front()[2].IsEqual(OrthancStone::ScenePoint2D(7, 6)));
597 ASSERT_TRUE(contours.front()[3].IsEqual(OrthancStone::ScenePoint2D(10, 6)));
598 ASSERT_TRUE(contours.front()[4].IsEqual(OrthancStone::ScenePoint2D(10, 4)));
599 ASSERT_TRUE(contours.front()[5].IsEqual(OrthancStone::ScenePoint2D(7, 4)));
600 ASSERT_TRUE(contours.front()[6].IsEqual(OrthancStone::ScenePoint2D(7, 2)));
601 ASSERT_TRUE(contours.front()[7].IsEqual(OrthancStone::ScenePoint2D(4, 2)));
602 ASSERT_TRUE(contours.front()[8].IsEqual(OrthancStone::ScenePoint2D(4, 4)));
603 ASSERT_TRUE(contours.front()[9].IsEqual(OrthancStone::ScenePoint2D(7, 4)));
604 ASSERT_TRUE(contours.front()[10].IsEqual(OrthancStone::ScenePoint2D(7, 6)));
605 ASSERT_TRUE(contours.front()[11].IsEqual(OrthancStone::ScenePoint2D(4, 6)));
606 ASSERT_TRUE(contours.front()[12].IsEqual(OrthancStone::ScenePoint2D(4, 4)));
607 ASSERT_TRUE(contours.front()[13].IsEqual(OrthancStone::ScenePoint2D(1, 4)));
608 ASSERT_TRUE(contours.front()[14].IsEqual(OrthancStone::ScenePoint2D(1, 6)));
609 ASSERT_TRUE(contours.front()[15].IsEqual(OrthancStone::ScenePoint2D(4, 6)));
610 ASSERT_TRUE(contours.front()[16].IsEqual(OrthancStone::ScenePoint2D(4, 8)));
611 }
612
613 {
614 std::list<OrthancStone::Extent2D> rectangles;
615 rectangles.push_back(OrthancStone::Extent2D(1, 4, 4, 6));
616 rectangles.push_back(OrthancStone::Extent2D(4, 4, 7, 6));
617
618 std::list< std::vector<OrthancStone::ScenePoint2D> > contours;
619 OrthancStone::UnionOfRectangles::Apply(contours, rectangles);
620
621 ASSERT_EQ(1u, contours.size());
622 ASSERT_EQ(5u, contours.front().size());
623 ASSERT_TRUE(contours.front()[0].IsEqual(OrthancStone::ScenePoint2D(1, 6)));
624 ASSERT_TRUE(contours.front()[1].IsEqual(OrthancStone::ScenePoint2D(7, 6)));
625 ASSERT_TRUE(contours.front()[2].IsEqual(OrthancStone::ScenePoint2D(7, 4)));
626 ASSERT_TRUE(contours.front()[3].IsEqual(OrthancStone::ScenePoint2D(1, 4)));
627 ASSERT_TRUE(contours.front()[4].IsEqual(OrthancStone::ScenePoint2D(1, 6)));
628 }
629
630 {
631 std::list<OrthancStone::Extent2D> rectangles;
632 rectangles.push_back(OrthancStone::Extent2D(1, 4, 4, 6));
633 rectangles.push_back(OrthancStone::Extent2D(1, 6, 4, 8));
634
635 std::list< std::vector<OrthancStone::ScenePoint2D> > contours;
636 OrthancStone::UnionOfRectangles::Apply(contours, rectangles);
637
638 ASSERT_EQ(1u, contours.size());
639 ASSERT_EQ(5u, contours.front().size());
640 ASSERT_TRUE(contours.front()[0].IsEqual(OrthancStone::ScenePoint2D(1, 8)));
641 ASSERT_TRUE(contours.front()[1].IsEqual(OrthancStone::ScenePoint2D(4, 8)));
642 ASSERT_TRUE(contours.front()[2].IsEqual(OrthancStone::ScenePoint2D(4, 4)));
643 ASSERT_TRUE(contours.front()[3].IsEqual(OrthancStone::ScenePoint2D(1, 4)));
644 ASSERT_TRUE(contours.front()[4].IsEqual(OrthancStone::ScenePoint2D(1, 8)));
645 }
646
647 {
648 std::list<OrthancStone::Extent2D> rectangles;
649 rectangles.push_back(OrthancStone::Extent2D(1, 1, 2, 2));
650 rectangles.push_back(OrthancStone::Extent2D(4, 4, 7, 6));
651 rectangles.push_back(OrthancStone::Extent2D(4, 6, 7, 8));
652
653 std::list< std::vector<OrthancStone::ScenePoint2D> > contours;
654 OrthancStone::UnionOfRectangles::Apply(contours, rectangles);
655
656 ASSERT_EQ(2u, contours.size());
657
658 ASSERT_EQ(5u, contours.front().size());
659 ASSERT_TRUE(contours.front()[0].IsEqual(OrthancStone::ScenePoint2D(4, 8)));
660 ASSERT_TRUE(contours.front()[1].IsEqual(OrthancStone::ScenePoint2D(7, 8)));
661 ASSERT_TRUE(contours.front()[2].IsEqual(OrthancStone::ScenePoint2D(7, 4)));
662 ASSERT_TRUE(contours.front()[3].IsEqual(OrthancStone::ScenePoint2D(4, 4)));
663 ASSERT_TRUE(contours.front()[4].IsEqual(OrthancStone::ScenePoint2D(4, 8)));
664
665 ASSERT_EQ(5u, contours.back().size());
666 ASSERT_TRUE(contours.back()[0].IsEqual(OrthancStone::ScenePoint2D(1, 2)));
667 ASSERT_TRUE(contours.back()[1].IsEqual(OrthancStone::ScenePoint2D(2, 2)));
668 ASSERT_TRUE(contours.back()[2].IsEqual(OrthancStone::ScenePoint2D(2, 1)));
669 ASSERT_TRUE(contours.back()[3].IsEqual(OrthancStone::ScenePoint2D(1, 1)));
670 ASSERT_TRUE(contours.back()[4].IsEqual(OrthancStone::ScenePoint2D(1, 2)));
671 }
672
673 #if 0
674 {
675 std::list<OrthancStone::Extent2D> rectangles;
676 rectangles.push_back(OrthancStone::Extent2D(1, 4, 4, 6));
677 rectangles.push_back(OrthancStone::Extent2D(6, 4, 9, 6));
678 rectangles.push_back(OrthancStone::Extent2D(4, 6, 7, 8));
679 rectangles.push_back(OrthancStone::Extent2D(4, 2, 7, 6));
680
681 std::list< std::vector<OrthancStone::ScenePoint2D> > contours;
682 OrthancStone::UnionOfRectangles::Apply(contours, rectangles);
683
684 SaveSvg(contours);
685
686 ASSERT_EQ(1u, contours.size());
687 ASSERT_EQ(13u, contours.front().size());
688 ASSERT_TRUE(contours.front()[0].IsEqual(OrthancStone::ScenePoint2D(4, 8)));
689 ASSERT_TRUE(contours.front()[1].IsEqual(OrthancStone::ScenePoint2D(7, 8)));
690 ASSERT_TRUE(contours.front()[2].IsEqual(OrthancStone::ScenePoint2D(7, 6)));
691 ASSERT_TRUE(contours.front()[3].IsEqual(OrthancStone::ScenePoint2D(9, 6)));
692 ASSERT_TRUE(contours.front()[4].IsEqual(OrthancStone::ScenePoint2D(7, 6)));
693 ASSERT_TRUE(contours.front()[5].IsEqual(OrthancStone::ScenePoint2D(4, 4)));
694 ASSERT_TRUE(contours.front()[6].IsEqual(OrthancStone::ScenePoint2D(1, 4)));
695 ASSERT_TRUE(contours.front()[7].IsEqual(OrthancStone::ScenePoint2D()));
696 ASSERT_TRUE(contours.front()[8].IsEqual(OrthancStone::ScenePoint2D()));
697 ASSERT_TRUE(contours.front()[9].IsEqual(OrthancStone::ScenePoint2D()));
698 ASSERT_TRUE(contours.front()[10].IsEqual(OrthancStone::ScenePoint2D()));
699 ASSERT_TRUE(contours.front()[11].IsEqual(OrthancStone::ScenePoint2D()));
700 ASSERT_TRUE(contours.front()[12].IsEqual(OrthancStone::ScenePoint2D()));
701 }
702 #endif
703 }