Mercurial > hg > orthanc-stone
comparison UnitTestsSources/ComputationalGeometryTests.cpp @ 1875:b896f20d24ca
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 } |