9 #ifndef _LIMBO_GEOMETRY_POLYGON2RECTANGLEVEC_H
10 #define _LIMBO_GEOMETRY_POLYGON2RECTANGLEVEC_H
23 struct point_compare_type;
24 template <
typename PointSet,
26 class Polygon2Rectangle;
32 template <
typename PointType,
33 typename RectangleType>
43 typedef typename container_traits<point_set_type>::value_type
point_type;
48 typedef typename container_traits<rectangle_set_type>::value_type
rectangle_type;
65 :
m_mPoint((slicing_orient != HORIZONTAL_SLICING && slicing_orient != VERTICAL_SLICING)? 2 : 1)
66 , m_vOrient2Id(2, std::numeric_limits<unsigned char>::
max())
80 template <
typename InputIterator>
82 :
m_mPoint((slicing_orient != HORIZONTAL_SLICING && slicing_orient != VERTICAL_SLICING)? 2 : 1)
83 , m_vOrient2Id(2, std::numeric_limits<unsigned char>::
max())
96 template <
typename InputIterator>
97 void initialize(InputIterator input_begin, InputIterator input_end)
99 assert(input_begin != input_end);
104 std::vector<point_type> vTmpPoint;
105 InputIterator input_last = input_begin;
106 std::size_t dist = std::distance(input_begin, input_end);
107 std::advance(input_last, dist-1);
108 if (is_equal_type()(*input_begin, *input_last))
113 vTmpPoint.reserve(dist);
115 for (InputIterator itPrev = input_begin; itPrev != input_end; ++itPrev)
117 InputIterator itCur = itPrev;
119 if (itCur == input_end)
121 InputIterator itNext = itCur;
123 if (itNext == input_end)
124 itNext = input_begin;
127 if (is_equal_type()(*itCur, *itNext))
131 if (this->
get(*itPrev, HORIZONTAL) == this->
get(*itCur, HORIZONTAL)
132 && this->
get(*itCur, HORIZONTAL) == this->
get(*itNext, HORIZONTAL))
135 assert(
std::min(this->
get(*itPrev, VERTICAL), this->
get(*itNext, VERTICAL)) <= this->
get(*itCur, VERTICAL)
136 &&
std::max(this->
get(*itPrev, VERTICAL), this->
get(*itNext, VERTICAL)) >= this->
get(*itCur, VERTICAL));
140 else if (this->
get(*itPrev, VERTICAL) == this->
get(*itCur, VERTICAL)
141 && this->
get(*itCur, VERTICAL) == this->
get(*itNext, VERTICAL))
144 assert(
std::min(this->
get(*itPrev, HORIZONTAL), this->
get(*itNext, HORIZONTAL)) <= this->
get(*itCur, HORIZONTAL)
145 &&
std::max(this->
get(*itPrev, HORIZONTAL), this->
get(*itNext, HORIZONTAL)) >= this->
get(*itCur, HORIZONTAL));
154 this->
get(*itCur, HORIZONTAL),
155 this->
get(*itCur, VERTICAL)
160 assert(vTmpPoint.size() % 2 == 0);
165 point_set_type& vPointFront =
m_mPoint.front().second;
168 vPointFront.reserve(vTmpPoint.size());
169 for (
typename std::vector<point_type>::iterator itCur = vTmpPoint.begin(), itCure = vTmpPoint.end(); itCur != itCure; ++itCur)
171 typename std::vector<point_type>::iterator itNext = itCur;
173 if (itNext == itCure)
174 itNext = vTmpPoint.begin();
175 if (!is_equal_type()(*itCur, *itNext))
176 vPointFront.push_back(*itCur);
180 if (itCur == itCure)
break;
185 for (std::size_t i = 1, ie =
m_mPoint.size(); i < ie; ++i)
187 point_set_type
const& vPointPrev =
m_mPoint[i-1].second;
189 point_set_type& vPoint =
m_mPoint[i].second;
192 vPoint.swap(vTmpPoint);
194 vPoint.assign(vPointPrev.begin(), vPointPrev.end());
206 std::vector<rectangle_type> vRect (
m_mPoint.size());
208 while (!
m_mPoint.front().second.empty())
212 for (
typename std::vector<std::pair<orientation_2d, point_set_type> >::const_iterator it =
m_mPoint.begin();
217 point_set_type
const& vPoint = it->second;
218 assert(vPoint.empty() || !vPoint.empty());
221 point_type Pk, Pl, Pm;
226 rectangle_type& rect = vRect[i];
232 this->
get(Pk, HORIZONTAL),
233 this->
get(Pk, VERTICAL),
234 std::max(this->
get(Pl, HORIZONTAL), this->
get(Pm, HORIZONTAL)),
235 std::max(this->
get(Pl, VERTICAL), this->
get(Pm, VERTICAL)));
244 typename std::vector<rectangle_type>::iterator itRect = vRect.begin();
245 for (
typename std::vector<rectangle_type>::iterator it = ++vRect.begin(); it != vRect.end(); ++it)
249 coordinate_distance w = this->
get(*it, RIGHT)-this->
get(*it, LEFT);
250 coordinate_distance h = this->
get(*it, TOP)-this->
get(*it, BOTTOM);
251 coordinate_distance wref = this->
get(*itRect, RIGHT)-this->
get(*itRect, LEFT);
252 coordinate_distance href = this->
get(*itRect, TOP)-this->
get(*itRect, BOTTOM);
272 coordinate_distance minDelta = w;
273 coordinate_distance maxDelta = h;
274 coordinate_distance minDeltaRef = wref;
275 coordinate_distance maxDeltaRef = href;
276 if (minDelta > maxDelta)
277 std::swap(minDelta, maxDelta);
278 if (minDeltaRef > maxDeltaRef)
279 std::swap(minDeltaRef, maxDeltaRef);
281 if (maxDelta*minDeltaRef < minDelta*maxDeltaRef)
290 for (
typename std::vector<std::pair<orientation_2d, point_set_type> >::iterator it =
m_mPoint.begin();
295 point_set_type
const& vPoint = it->second;
296 assert(vPoint.empty() || !vPoint.empty());
323 bool read(
string const& filename)
325 ifstream in (filename.c_str());
328 cout <<
"failed to open " << filename << endl;
336 std::vector<point_type> vPoint;
341 if (tag ==
"polygon" && status == 0)
345 else if (tag ==
"from" || tag ==
"to")
348 coordinate_type value[2] = {0, 0};
351 while (!in.eof() && i < 2)
354 boost::trim_if(value_str, boost::is_any_of(
", \t\\"));
357 value[i] = boost::lexical_cast<coordinate_type>(value_str);
363 if (i != 2)
return false;
366 this->
set(vPoint.back(), HORIZONTAL, value[0]);
367 this->
set(vPoint.back(), VERTICAL, value[1]);
369 else if (status == 1)
376 this->
initialize(vPoint.begin(), vPoint.end());
384 void print(
string const& filename)
const
386 ofstream out (filename.c_str());
389 cout <<
"failed to open " << filename << endl;
393 point_set_type
const& vPoint =
m_mPoint.begin()->second;
395 if (vPoint.size() > 0)
397 out <<
"set obj " << i++ <<
" ";
398 out <<
"polygon \\" << endl;
399 for (
typename point_set_type::const_iterator it = vPoint.begin(), ite = vPoint.end(); it != ite; ++it)
401 if (it == vPoint.begin())
402 out <<
"from " << this->
get(*it, HORIZONTAL) <<
", " << this->
get(*it, VERTICAL) <<
" \\" << endl;
404 out <<
"to " << this->
get(*it, HORIZONTAL) <<
", " << this->
get(*it, VERTICAL) <<
" \\" << endl;
410 for (
typename rectangle_set_type::const_iterator it =
m_vRect.begin(); it !=
m_vRect.end(); ++it)
413 out <<
"set obj " << i <<
" rectangle ";
414 out <<
"from " << this->
get(*it, LEFT) <<
", " << this->
get(*it, BOTTOM) <<
" "
415 <<
"to " << this->
get(*it, RIGHT) <<
", " << this->
get(*it, TOP) <<
" ";
416 out <<
"fc rgb \"dark-grey\" fs transparent pattern 4 bo"<< endl;
418 out <<
"set label \'" << i <<
"\' at "
419 << (this->
get(*it, LEFT)+this->
get(*it, RIGHT))/2.0 <<
", " << (this->
get(*it, BOTTOM)+this->
get(*it, TOP))/2.0 <<
" "
420 <<
"front center tc rgb \"black\"" << endl;
466 inline bool operator() (point_type
const& p1, point_type
const& p2)
const
479 switch (slicing_orient)
482 case HORIZONTAL_SLICING:
484 m_vOrient2Id[VERTICAL] = 0;
486 case VERTICAL_SLICING:
488 m_vOrient2Id[HORIZONTAL] = 0;
494 m_vOrient2Id[HORIZONTAL] = 0;
496 m_vOrient2Id[VERTICAL] = 1;
499 std::cout <<
"unknown slicing orientation" << std::endl;
514 point_set_type
const& vPoint =
m_mPoint.at(m_vOrient2Id[orient.
to_int()]).second;
515 if (vPoint.size() < 4)
520 this->
set(Pk, HORIZONTAL, this->
get(*vPoint.begin(), HORIZONTAL));
521 this->
set(Pk, VERTICAL, this->
get(*vPoint.begin(), VERTICAL));
523 this->
set(Pl, HORIZONTAL, this->
get(*(++(vPoint.begin())), HORIZONTAL));
524 this->
set(Pl, VERTICAL, this->
get(*(++(vPoint.begin())), VERTICAL));
528 for (
typename point_set_type::const_iterator it = vPoint.begin(), ite = vPoint.end(); it != ite; ++it)
530 if (this->
get(Pk, orient) == this->
get(*it, orient))
535 assert(this->
get(*it, orient) > this->
get(Pk, orient));
536 this->
set(Pm, HORIZONTAL, this->
get(*it, HORIZONTAL));
537 this->
set(Pm, VERTICAL, this->
get(*it, VERTICAL));
555 point_set_type& vPoint =
m_mPoint.at(m_vOrient2Id[orient.
to_int()]).second;
558 typename point_set_type::iterator itr = std::lower_bound(vPoint.begin(), vPoint.end(), point,
point_compare_type(orient));
560 if (itr == vPoint.end() || !is_equal_type()(*itr, point))
569 std::vector<std::pair<orientation_2d, point_set_type> >
m_mPoint;
570 std::vector<unsigned char> m_vOrient2Id;
static rectangle_type construct(coordinate_type const &xl, coordinate_type const &yl, coordinate_type const &xh, coordinate_type const &yh)
construct rectangle from coordinates
static coordinate_type get(const point_type &point, orientation_2d const &orient)
get coordinate from point
int to_int() const
convert orientation to integer
Polygon2Rectangle(rectangle_set_type &vRect, InputIterator input_begin, InputIterator input_end, slicing_orientation_2d slicing_orient)
constructor
std::vector< std::pair< orientation_2d, point_set_type > > m_mPoint
static void set(rectangle_type &rectangle, direction_2d const &direct, coordinate_type const &v)
set coordinate for rectangle
rectangle_set_type & m_vRect
save all rectangles from conversion
map< orientation_2d, point_set_type > m_mPoint
static void set(point_type &point, orientation_2d const &orient, coordinate_type const &value)
set coordinate for point
std::vector< PointType > point_set_type
internal point set type
void F(point_type const &point, orientation_2d const &orient)
F function in the original paper remove point if found, otherwise insert.
container_traits< rectangle_set_type >::value_type rectangle_type
internal rectangle type
direction_2d
direction type for rectangles
horizontal/vertical slicing and choose rectangle with smaller area every time
sort helper if orient == HORIZONTAL, sort by left lower if orient == VERTICAL, sort by lower left ...
slicing_orientation_2d m_slicing_orient
slicing orient
slicing_orientation_2d m_slicing_orient
slicing orient
bool operator()()
top api for limbo::geometry::Polygon2Rectangle
void initialize(slicing_orientation_2d slicing_orient)
initialize with slicing orientation it must be called before initializing other data ...
bool find_Pk_Pl_Pm(point_type &Pk, point_type &Pl, point_type &Pm, orientation_2d const &orient)
find Pk, Pl, Pm, please refer to the paper for definition Given points, find Pk, Pl and Pm ...
void initialize(InputIterator input_begin, InputIterator input_end)
initialize polygon points
slicing_orientation_2d
orientation type for slicing
void set(point_type &p, orientation_2d o, coordinate_type v) const
set coordinate of point
type traits for containers such as vector, list, multiset
bool find_Pk_Pl_Pm(point_type &Pk, point_type &Pl, point_type &Pm, orientation_2d const &orient)
find Pk, Pl, Pm, please refer to the paper for definition Given points, find Pk, Pl and Pm ...
a class implement conversion from manhattan polygon to rectangle
point_traits< point_type >::coordinate_type coordinate_type
point set type for polygon
bool is_number(string const &s)
check whether string represents a number, either integer or floating point number ...
std::vector< RectangleType > rectangle_set_type
internal rectangle set type
static coordinate_type get(rectangle_type const &rectangle, direction_2d const &direct)
get coordinate from rectangle
horizontal/vertical slicing and choose rectangle with better aspect ratio every time ...
orientation_2d get_perpendicular() const
get perpendicular orientation
container_traits< point_set_type >::value_type point_type
internal point type
void set(rectangle_type &r, direction_2d d, coordinate_type v) const
set coordinate of rectangle
container_traits< point_set_type >::value_type point_type
internal point type
std::iterator_traits< Iterator >::value_type max(Iterator first, Iterator last)
get max of an array
type traits for coordinates
static void insert(container_type &container, value_type const &v)
insert value to container
void print(string const &filename) const
print polygon to file in gnuplot format
void F(point_type const &point, orientation_2d const &orient)
F function in the original paper remove point if found, otherwise insert.
horizontal/vertical slicing and choose rectangle with larger area every time
rectangle_set_type & m_vRect
save all rectangles from conversion
static void erase(container_type &container, value_type const &v)
erase value from iterator
coordinate_traits< coordinate_type >::coordinate_distance coordinate_distance
coordinate distance type
bool operator()(point_type const &p1, point_type const &p2) const
is equal helper
std::iterator_traits< Iterator >::value_type min(Iterator first, Iterator last)
get min of an array
coordinate_traits< coordinate_type >::manhattan_area_type manhattan_area_type
manhattan area type
bool read(string const &filename)
read polygon from file try to be compatible to gnuplot format
#define assert_msg(condition, message)
assertion with message
rectangle_set_type const & get_rectangles() const
get rectangles
a class denoting orientation of lines
void initialize(InputIterator input_begin, InputIterator input_end)
initialize polygon points
void set(point_type &p, orientation_2d o, coordinate_type v) const
set coordinate of point
Polygon2Rectangle(rectangle_set_type &vRect, slicing_orientation_2d slicing_orient=HORIZONTAL_SLICING)
constructor