2017年7月23日

[C++] boost::geometry::overlaps 的檢查與預期不符

目前的程式因為需要大量的多邊形操作,所以現在是直接用 boost::geometry 來做相關的運算,其中很常用的是要檢查 2 個多邊形是否重疊到,在 boost::geometry 中有提供 2 種操作:intersects & overlaps,兩者差異如下:
  • intersects:2 個多邊形只要有 "一個點" 重疊到就算有相交
  • overlaps:2 個多邊形必須要有重疊到 "一塊面" 才算
所以如果今天要檢查 2 個多邊形是否只有重疊到 "一條邊" 就必須自己想辦法兜出來,但這不是這次的重點,這次的重點在 overlaps 有另一個隱藏的細節:
其中一個多邊形不能完全包含住另一個多邊形
這種情形下,overlaps 的回傳值是 false,然後我 TMD 踩到這狀況結果問題找超久阿阿阿阿
舉個例子,下面這隻程式的 p1 被包在 p2 裡,但是這情況 overlaps 的回傳值是 false (也就是沒有重疊):

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>
typedef boost::geometry::model::point<int, 2, boost::geometry::cs::cartesian> point_t;
typedef boost::geometry::model::box<point_t> box_t;
// point should be in clockwise order
typedef boost::geometry::model::polygon<point_t> polygon_t;

int main()
{
    const polygon_t p1 {{{0, 0}, {0, 2}, {2, 2}, {2, 0}, {0, 0}}};
    const polygon_t p2 {{{0, 0}, {0, 3}, {3, 3}, {3, 0}, {0, 0}}};
    printf("is overlap? %d\n", boost::geometry::overlaps(p2, p1));
    return 0;
}

boost geometry 的實作從 document 來看應該是有遵照一定的規範在處理,不過我到現在還沒仔細看過,搞不好那規範裡面有一些跟一般預期不同的結果...Orz

沒有留言:

張貼留言