ここで見つけることができる Boost セグメント utils の intersect_segments メソッドを使用したいと思います。
また、Point および Segment 構造体を Boost.Polygon の概念にマップするコードに従って実装しました: http://www.boost.org/doc/libs/1_59_0/libs/polygon/doc/voronoi_basic_tutorial.htm
ただし、含める<boost/polygon/segment_utils.hpp>と、コンパイル中に多くのエラーが発生します。
In file included from /usr/include/boost/polygon/segment_utils.hpp:16:0,
from test.cpp:17:
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:17:49: error: expected template-name before '<' token
class line_intersection : public scanline_base<Unit> {
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:17:49: error: expected '{' before '<' token
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:17:49: error: expected unqualified-id before '<' token
In file included from /usr/include/boost/polygon/segment_utils.hpp:16:0,
from test.cpp:17:
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:947:40: error: expected template-name before '<' token
class scanline : public scanline_base<Unit> {
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:947:40: error: expected '{' before '<' token
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:947:40: error: expected unqualified-id before '<' token
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:1472:22: error: expected nested-name-specifier before 'scanline_base'
typedef typename scanline_base<Unit>::half_edge half_edge;
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:1472:22: error: expected ';' at end of member declaration
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:1472:35: error: expected unqualified-id before '<' token
typedef typename scanline_base<Unit>::half_edge half_edge;
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:1475:48: error: 'half_edge' does not name a type
void operator()(result_type& result, const half_edge& edge, const key_type& left, const key_type& right) {
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp: In member function 'void boost::polygon::merge_output_functor<Unit>::operator()(result_type&, const int&, const key_type&, const key_type&)':
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:1476:26: error: 'half_edge' was not declared in this scope
typename std::pair<half_edge, int> elem;
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:1476:40: error: template argument 1 is invalid
typename std::pair<half_edge, int> elem;
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:1476:42: error: 'elem' in namespace 'std' does not name a type
typename std::pair<half_edge, int> elem;
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:1477:7: error: 'elem' was not declared in this scope
elem.first = edge;
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:1479:15: error: request for member 'second' in 'edge', which is of non-class type 'const int'
if(edge.second < edge.first) elem.second *= -1;
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:1479:29: error: request for member 'first' in 'edge', which is of non-class type 'const int'
if(edge.second < edge.first) elem.second *= -1;
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:1480:10: error: 'boost::polygon::merge_output_functor<Unit>::scanline_base {aka int}' is not a template
if(scanline_base<Unit>::is_vertical(edge)) elem.second *= -1;
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:1480:10: error: 'scanline_base' is not a class, namespace, or enumeration
/usr/include/boost/polygon/detail/scan_arbitrary.hpp: At global scope:
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:1491:46: error: expected template-name before '<' token
class property_merge : public scanline_base<Unit> {
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:1491:46: error: expected '{' before '<' token
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:1491:46: error: expected unqualified-id before '<' token
In file included from /usr/include/boost/polygon/segment_utils.hpp:16:0,
from test.cpp:17:
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:2490:52: error: expected template-name before '<' token
class arbitrary_boolean_op : public scanline_base<Unit> {
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:2490:52: error: expected '{' before '<' token
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:2490:52: error: expected unqualified-id before '<' token
/usr/include/boost/polygon/detail/scan_arbitrary.hpp: In function 'bool boost::polygon::test_arbitrary_boolean_op(stream_type&)':
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:2653:5: error: 'polygon_set_data' was not declared in this scope
polygon_set_data<Unit> psd;
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:2653:26: error: expected primary-expression before '>' token
polygon_set_data<Unit> psd;
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:2653:28: error: 'psd' was not declared in this scope
polygon_set_data<Unit> psd;
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:2657:26: error: expected primary-expression before '>' token
polygon_set_data<Unit> psd2;
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:2657:28: error: 'psd2' was not declared in this scope
polygon_set_data<Unit> psd2;
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:2660:17: error: 'polygon_data' was not declared in this scope
std::vector<polygon_data<Unit> > pv;
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:2660:34: error: template argument 1 is invalid
std::vector<polygon_data<Unit> > pv;
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:2660:34: error: template argument 2 is invalid
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:2660:36: error: expected unqualified-id before '>' token
std::vector<polygon_data<Unit> > pv;
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:2661:5: error: 'pv' was not declared in this scope
pv.clear();
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:2663:26: error: expected primary-expression before '>' token
polygon_set_data<Unit> psd3;
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:2663:28: error: 'psd3' was not declared in this scope
polygon_set_data<Unit> psd3;
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp: At global scope:
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:2710:65: error: expected template-name before '<' token
class arbitrary_connectivity_extraction : public scanline_base<Unit> {
^
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:2710:65: error: expected '{' before '<' token
/usr/include/boost/polygon/detail/scan_arbitrary.hpp:2710:65: error: expected unqualified-id before '<' token
In file included from test.cpp:17:0:
/usr/include/boost/polygon/segment_utils.hpp: In function 'typename boost::enable_if<typename boost::polygon::gtl_and<typename boost::polygon::gtl_if<typename boost::polygon::is_segment_concept<typename boost::polygon::geometry_concept<typename std::iterator_traits<_Iterator1>::value_type>::type>::type>::type, typename boost::polygon::gtl_if<typename boost::polygon::is_segment_concept<typename boost::polygon::geometry_concept<GeometryType>::type>::type>::type>::type, void>::type boost::polygon::intersect_segments(std::vector<std::pair<long unsigned int, Segment> >&, SegmentIterator, SegmentIterator)':
/usr/include/boost/polygon/segment_utils.hpp:46:20: error: expected nested-name-specifier before 'scanline_base'
typedef typename scanline_base<Unit>::Point Point;
^
/usr/include/boost/polygon/segment_utils.hpp:46:33: error: expected initializer before '<' token
typedef typename scanline_base<Unit>::Point Point;
^
/usr/include/boost/polygon/segment_utils.hpp:47:20: error: expected nested-name-specifier before 'scanline_base'
typedef typename scanline_base<Unit>::half_edge half_edge;
^
/usr/include/boost/polygon/segment_utils.hpp:47:33: error: expected initializer before '<' token
typedef typename scanline_base<Unit>::half_edge half_edge;
^
/usr/include/boost/polygon/segment_utils.hpp:49:25: error: 'half_edge' was not declared in this scope
std::vector<std::pair<half_edge, segment_id> > half_edges;
^
/usr/include/boost/polygon/segment_utils.hpp:49:46: error: template argument 1 is invalid
std::vector<std::pair<half_edge, segment_id> > half_edges;
^
/usr/include/boost/polygon/segment_utils.hpp:49:48: error: template argument 1 is invalid
std::vector<std::pair<half_edge, segment_id> > half_edges;
^
/usr/include/boost/polygon/segment_utils.hpp:49:48: error: template argument 2 is invalid
/usr/include/boost/polygon/segment_utils.hpp:50:25: error: the value of 'half_edge' is not usable in a constant expression
std::vector<std::pair<half_edge, segment_id> > half_edges_out;
^
/usr/include/boost/polygon/segment_utils.hpp:49:25: note: 'half_edge' was not declared 'constexpr'
std::vector<std::pair<half_edge, segment_id> > half_edges;
^
/usr/include/boost/polygon/segment_utils.hpp:50:46: error: type/value mismatch at argument 1 in template parameter list for 'template<class _T1, class _T2> struct std::pair'
std::vector<std::pair<half_edge, segment_id> > half_edges_out;
^
/usr/include/boost/polygon/segment_utils.hpp:50:46: note: expected a type, got 'half_edge'
/usr/include/boost/polygon/segment_utils.hpp:50:48: error: template argument 1 is invalid
std::vector<std::pair<half_edge, segment_id> > half_edges_out;
^
/usr/include/boost/polygon/segment_utils.hpp:50:48: error: template argument 2 is invalid
/usr/include/boost/polygon/segment_utils.hpp:52:14: error: request for member 'reserve' in 'half_edges', which is of non-class type 'int'
half_edges.reserve(std::distance(first, last));
^
/usr/include/boost/polygon/segment_utils.hpp:57:16: error: request for member 'push_back' in 'half_edges', which is of non-class type 'int'
half_edges.push_back(std::make_pair(half_edge(l, h), id_in++));
^
/usr/include/boost/polygon/segment_utils.hpp:59:18: error: request for member 'reserve' in 'half_edges_out', which is of non-class type 'int'
half_edges_out.reserve(half_edges.size());
^
/usr/include/boost/polygon/segment_utils.hpp:59:37: error: request for member 'size' in 'half_edges', which is of non-class type 'int'
half_edges_out.reserve(half_edges.size());
^
/usr/include/boost/polygon/segment_utils.hpp:61:18: error: request for member 'size' in 'half_edges', which is of non-class type 'int'
if (half_edges.size() != 0) {
^
/usr/include/boost/polygon/segment_utils.hpp:63:36: error: request for member 'begin' in 'half_edges', which is of non-class type 'int'
half_edges_out, half_edges.begin(), half_edges.end());
^
/usr/include/boost/polygon/segment_utils.hpp:63:56: error: request for member 'end' in 'half_edges', which is of non-class type 'int'
half_edges_out, half_edges.begin(), half_edges.end());
^
/usr/include/boost/polygon/segment_utils.hpp:66:49: error: request for member 'size' in 'half_edges_out', which is of non-class type 'int'
result.reserve(result.size() + half_edges_out.size());
^
/usr/include/boost/polygon/segment_utils.hpp:67:46: error: request for member 'size' in 'half_edges_out', which is of non-class type 'int'
for (std::size_t i = 0; i < half_edges_out.size(); ++i) {
^
/usr/include/boost/polygon/segment_utils.hpp:68:52: error: invalid types 'int[std::size_t {aka long unsigned int}]' for array subscript
std::size_t id = (std::size_t)(half_edges_out[i].second);
^
/usr/include/boost/polygon/segment_utils.hpp:69:31: error: invalid types 'int[std::size_t {aka long unsigned int}]' for array subscript
Point l = half_edges_out[i].first.first;
^
/usr/include/boost/polygon/segment_utils.hpp:70:31: error: invalid types 'int[std::size_t {aka long unsigned int}]' for array subscript
Point h = half_edges_out[i].first.second;
^
/usr/include/boost/polygon/segment_utils.hpp: In function 'typename boost::enable_if<typename boost::polygon::gtl_and<typename boost::polygon::gtl_if<typename boost::polygon::is_segment_concept<typename boost::polygon::geometry_concept<typename std::iterator_traits<_Iterator1>::value_type>::type>::type>::type, typename boost::polygon::gtl_if<typename boost::polygon::is_segment_concept<typename boost::polygon::geometry_concept<typename SegmentContainer::value_type>::type>::type>::type>::type, void>::type boost::polygon::intersect_segments(SegmentContainer&, SegmentIterator, SegmentIterator)':
/usr/include/boost/polygon/segment_utils.hpp:101:20: error: expected nested-name-specifier before 'scanline_base'
typedef typename scanline_base<Unit>::Point Point;
^
/usr/include/boost/polygon/segment_utils.hpp:101:33: error: expected initializer before '<' token
typedef typename scanline_base<Unit>::Point Point;
^
/usr/include/boost/polygon/segment_utils.hpp:102:20: error: expected nested-name-specifier before 'scanline_base'
typedef typename scanline_base<Unit>::half_edge half_edge;
^
/usr/include/boost/polygon/segment_utils.hpp:102:33: error: expected initializer before '<' token
typedef typename scanline_base<Unit>::half_edge half_edge;
^
/usr/include/boost/polygon/segment_utils.hpp:104:25: error: 'half_edge' was not declared in this scope
std::vector<std::pair<half_edge, segment_id> > half_edges;
^
/usr/include/boost/polygon/segment_utils.hpp:104:46: error: template argument 1 is invalid
std::vector<std::pair<half_edge, segment_id> > half_edges;
^
/usr/include/boost/polygon/segment_utils.hpp:104:48: error: template argument 1 is invalid
std::vector<std::pair<half_edge, segment_id> > half_edges;
^
/usr/include/boost/polygon/segment_utils.hpp:104:48: error: template argument 2 is invalid
/usr/include/boost/polygon/segment_utils.hpp:105:25: error: the value of 'half_edge' is not usable in a constant expression
std::vector<std::pair<half_edge, segment_id> > half_edges_out;
^
/usr/include/boost/polygon/segment_utils.hpp:104:25: note: 'half_edge' was not declared 'constexpr'
std::vector<std::pair<half_edge, segment_id> > half_edges;
^
/usr/include/boost/polygon/segment_utils.hpp:105:46: error: type/value mismatch at argument 1 in template parameter list for 'template<class _T1, class _T2> struct std::pair'
std::vector<std::pair<half_edge, segment_id> > half_edges_out;
^
/usr/include/boost/polygon/segment_utils.hpp:105:46: note: expected a type, got 'half_edge'
/usr/include/boost/polygon/segment_utils.hpp:105:48: error: template argument 1 is invalid
std::vector<std::pair<half_edge, segment_id> > half_edges_out;
^
/usr/include/boost/polygon/segment_utils.hpp:105:48: error: template argument 2 is invalid
/usr/include/boost/polygon/segment_utils.hpp:107:14: error: request for member 'reserve' in 'half_edges', which is of non-class type 'int'
half_edges.reserve(std::distance(first, last));
^
/usr/include/boost/polygon/segment_utils.hpp:112:16: error: request for member 'push_back' in 'half_edges', which is of non-class type 'int'
half_edges.push_back(std::make_pair(half_edge(l, h), id_in++));
^
/usr/include/boost/polygon/segment_utils.hpp:114:18: error: request for member 'reserve' in 'half_edges_out', which is of non-class type 'int'
half_edges_out.reserve(half_edges.size());
^
/usr/include/boost/polygon/segment_utils.hpp:114:37: error: request for member 'size' in 'half_edges', which is of non-class type 'int'
half_edges_out.reserve(half_edges.size());
^
/usr/include/boost/polygon/segment_utils.hpp:116:18: error: request for member 'size' in 'half_edges', which is of non-class type 'int'
if (half_edges.size() != 0) {
^
/usr/include/boost/polygon/segment_utils.hpp:118:36: error: request for member 'begin' in 'half_edges', which is of non-class type 'int'
half_edges_out, half_edges.begin(), half_edges.end());
^
/usr/include/boost/polygon/segment_utils.hpp:118:56: error: request for member 'end' in 'half_edges', which is of non-class type 'int'
half_edges_out, half_edges.begin(), half_edges.end());
^
/usr/include/boost/polygon/segment_utils.hpp:121:49: error: request for member 'size' in 'half_edges_out', which is of non-class type 'int'
result.reserve(result.size() + half_edges_out.size());
^
/usr/include/boost/polygon/segment_utils.hpp:122:46: error: request for member 'size' in 'half_edges_out', which is of non-class type 'int'
for (std::size_t i = 0; i < half_edges_out.size(); ++i) {
^
/usr/include/boost/polygon/segment_utils.hpp:123:31: error: invalid types 'int[std::size_t {aka long unsigned int}]' for array subscript
Point l = half_edges_out[i].first.first;
^
/usr/include/boost/polygon/segment_utils.hpp:124:31: error: invalid types 'int[std::size_t {aka long unsigned int}]' for array subscript
Point h = half_edges_out[i].first.second;
これは、ユニットの概念も実装する必要があるということでしょうか? もしそうなら、それはどのように行われますか？
編集: 私のコードはこのコードと同じです: http://www.boost.org/doc/libs/1_61_0/libs/polygon/example/voronoi_basic_tutorial.cppが#include <boost/polygon/segment_utils.hpp>追加されています。