Please explain find_feasible.hpp

[voidBunny]

find_feasible.hpp

//discard immediately intersecting translations
std::vector<TranslationVector> vectors;
for (const auto& v : potentialVectors) {
    bool discarded = false;
    for (const auto& sp : touchEdges) {
            ……
        }
}

May I ask what happened in the second loop? I don't understand. Sometimes the program discards the correct potential vectors. I am trying to figure out the logical flow of this code and fix it. Please!!

[kallaballa]

basically it checks if a translation would lead to an immediate (and unwanted) intersection of the two polygons. do you have a concrete test-case?

[voidBunny]

……
    double angle_double = (double)angle * 3.14 / 180;
    libnfporb::polygon_t new_polygons;
    auto& points = individual.GetPolygonsOuter();
    for (int idx = 0; idx < points.size(); idx++) {
        libnfporb::coord_t x = points[idx].x_;
        libnfporb::coord_t y = points[idx].y_;
        libnfporb::coord_t new_x = x * (libnfporb::coord_t)cos(angle) - y * (libnfporb::coord_t)sin(angle);
        libnfporb::coord_t new_y = x * (libnfporb::coord_t)sin(angle) + y * (libnfporb::coord_t)cos(angle);
        bg::append(new_polygons.outer(), libnfporb::point_t::point_t(new_x, new_y));
    }
……

I rotated the numbers in your data/generated like this code. I can't upload wkt files. (Github don't support that file type.) So I copy them here.

rotated_0.wkt : POLYGON ((640 128, 882 0, 1152 388, 1152 736, 1152 1084, 882 1472, 640 1472, 399 1472, 128 1084, 128 736, 128 388, 399 0, 640 0, 479 128, 320 430, 320 736, 320 1042, 479 1344, 640 1344, 801 1344, 960 1042, 960 736, 960 430, 801 128, 640 128))

rotated_1.wkt : POLYGON ((320 0, 1024 0, 1024 128, 768 128, 768 1472, 627 1472, 256 1216, 256 1061, 576 1281, 576 128, 320 128, 320 0))

rotated_d.wkt : POLYGON ((1088 128, 896 310, 748 128, 608 128, 466 128, 320 339, 320 544, 320 751, 466 960, 608 960, 748 960, 896 767, 896 585, 896 484, 1088 1536, 704 1536, 704 1408, 896 1408, 896 884, 843 989, 681 1088, 561 1088, 369 1088, 128 787, 128 544, 128 302, 370 0, 561 0, 681 0, 843 90, 896 185, 896 0, 1280 0, 1280 128, 1088 128))

Please test them. thx!

[kallaballa]

I don't understand your test-case. usually there are two polygons (A and B) and they result in a third polygon (the NFP). I tried to generate the NFP with the data of rotated_0 and rotated_1 and it works. Could you maybe post the exact test-case that fails and how you invoke it?

[voidBunny]

Sorry...I misplaced these files.

rotated_0.wkt : POLYGON ((-401.19868726354025 514.80444183982331, -395.20092942592805 788.50505729569204, -863.05151125782049 856.03159340972456, -1174.1623501908145 700.10197499677338, -1485.2731891238086 544.17235658382219, -1711.1640182459491 128.94069435355357, -1602.7302031426900 -87.406498237781420, -1494.7444616555599 -302.85969416551592, -1026.4458062075385 -371.28022694314905, -715.33496727454428 -215.35060853019783, -404.22412834155023 -59.420990117246618, -178.78137283553889 356.70466877662255, -286.76711432266887 572.15786470435705, -329.05883506674388 370.87097900013339, -527.80212250957436 93.407277416635367, -801.36510157134501 -43.703249118890710, -1074.9280806331158 -180.81377565441676, -1416.1587780050222 -173.98653821293743, -1488.2986302018187 -30.053075373247566, -1560.4384823986152 113.88038746644224, -1361.6951949557847 391.34408904994029, -1088.1322158940138 528.45461558546640, -814.56923683224318 665.56514212099239, -473.33853946033673 658.73790467951312, -401.19868726354025 514.80444183982331))

rotated_1.wkt : POLYGON ((-143.38355716133444 286.07893235217853, -458.82738291627021 915.45258352697124, -573.25895585714159 858.09916066243750, -458.55211012807410 629.23601478069463, -1660.0836260072238 27.025074703089899, -1596.9052461330107 -99.028454864588753, -1201.8067886673459 -315.99437133132807, -1063.2373058092594 -246.54296083130669, -1403.3001289627166 -59.040224027545605, -372.52197583127338 457.58865536938748, -257.81513010220584 228.72550948764476, -143.38355716133444 286.07893235217853))

I tried to generate the NFP with the data of rotated_0 and rotated_1 . rotated_0 is A polygon, rotated_1 is B polygon. When the program runs to find_feasible.hpp (can't printf next19.svg) , the vectors returned are empty.

[voidBunny]

Please leave ‘rotated_d.wkt’ alone, now don't care it...

[voidBunny]

[kallaballa]

Thanks for spotting this bug! It was caused by a regression that had to do with negative coordinates (see https://github.com/kallaballa/libnfporb/issues/20). Fixed c056f479dedaa516fc7672c1fc81be116ed61e10

[voidBunny]

Thank you!!