13 #ifndef _LIMBO_GEOMETRY_POLYGON2RECTANGLE
14 #define _LIMBO_GEOMETRY_POLYGON2RECTANGLE
22 #include <boost/lexical_cast.hpp>
23 #include <boost/algorithm/string/trim.hpp>
24 #include <boost/algorithm/string/classification.hpp>
71 template <
typename Po
intType>
72 inline bool operator()(PointType
const& p1, PointType
const& p2)
const
74 assert(m_orient.
valid());
88 template <
typename PointSet,
98 typedef typename container_traits<point_set_type>::value_type
point_type;
102 typedef typename container_traits<rectangle_set_type>::value_type
rectangle_type;
133 template <
typename InputIterator>
148 template <
typename InputIterator>
149 void initialize(InputIterator input_begin, InputIterator input_end)
155 std::vector<point_type> vTmpPoint;
158 InputIterator input_last = input_end;
159 for (InputIterator itCur = input_begin; itCur != input_end; ++itCur)
161 InputIterator itNext = itCur;
163 if (itNext == input_end)
169 assert_msg(input_last != input_end,
"failed to find input_last, maybe too few points");
170 if (
is_equal_type()(*input_begin, *input_last)) ++input_begin;
172 for (InputIterator itPrev = input_begin; itPrev != input_end; ++itPrev)
174 InputIterator itCur = itPrev;
176 if (itCur == input_end)
178 InputIterator itNext = itCur;
180 if (itNext == input_end)
181 itNext = input_begin;
188 if (this->
get(*itPrev, HORIZONTAL) == this->
get(*itCur, HORIZONTAL)
189 && this->
get(*itCur, HORIZONTAL) == this->
get(*itNext, HORIZONTAL))
192 assert(
std::min(this->
get(*itPrev, VERTICAL), this->
get(*itNext, VERTICAL)) <= this->
get(*itCur, VERTICAL)
193 &&
std::max(this->
get(*itPrev, VERTICAL), this->
get(*itNext, VERTICAL)) >= this->
get(*itCur, VERTICAL));
197 else if (this->
get(*itPrev, VERTICAL) == this->
get(*itCur, VERTICAL)
198 && this->
get(*itCur, VERTICAL) == this->
get(*itNext, VERTICAL))
201 assert(
std::min(this->
get(*itPrev, HORIZONTAL), this->
get(*itNext, HORIZONTAL)) <= this->
get(*itCur, HORIZONTAL)
202 &&
std::max(this->
get(*itPrev, HORIZONTAL), this->
get(*itNext, HORIZONTAL)) >= this->
get(*itCur, HORIZONTAL));
211 this->
get(*itCur, HORIZONTAL),
212 this->
get(*itCur, VERTICAL)
217 assert(vTmpPoint.size() % 2 == 0);
221 for (
typename map<orientation_2d, point_set_type>::iterator it =
m_mPoint.begin();
225 point_set_type& vPoint = it->second;
232 for (
typename vector<point_type>::iterator itCur = vTmpPoint.begin(); itCur != vTmpPoint.end(); ++itCur)
234 typename vector<point_type>::iterator itNext = itCur;
236 if (itNext == vTmpPoint.end())
237 itNext = vTmpPoint.begin();
243 if (itCur == vTmpPoint.end())
break;
248 cout <<
"reduce from " << vTmpPoint.size() <<
" to " <<
m_mPoint.begin()->second.size() << endl;
259 std::cout <<
"debug| PTR::Polygon2Rectangle(), m_vPoint = " << std::endl;
263 vector<rectangle_type> vRect (
m_mPoint.size());
265 while (
m_mPoint.begin()->second.size() > 0)
269 for (
typename map<orientation_2d, point_set_type>::iterator it =
m_mPoint.begin();
274 point_set_type
const& vPoint = it->second;
275 assert(vPoint.empty() || !vPoint.empty());
278 point_type Pk, Pl, Pm;
283 rectangle_type& rect = vRect[i];
289 this->
get(Pk, HORIZONTAL),
290 this->
get(Pk, VERTICAL),
291 std::max(this->
get(Pl, HORIZONTAL), this->
get(Pm, HORIZONTAL)),
292 std::max(this->
get(Pl, VERTICAL), this->
get(Pm, VERTICAL)));
301 typename vector<rectangle_type>::iterator itRect = vRect.begin();
302 for (
typename vector<rectangle_type>::iterator it = ++vRect.begin(); it != vRect.end(); ++it)
306 coordinate_distance w = this->
get(*it, RIGHT)-this->
get(*it, LEFT);
307 coordinate_distance h = this->
get(*it, TOP)-this->
get(*it, BOTTOM);
308 coordinate_distance wref = this->
get(*itRect, RIGHT)-this->
get(*itRect, LEFT);
309 coordinate_distance href = this->
get(*itRect, TOP)-this->
get(*itRect, BOTTOM);
329 coordinate_distance minDelta = w;
330 coordinate_distance maxDelta = h;
331 coordinate_distance minDeltaRef = wref;
332 coordinate_distance maxDeltaRef = href;
333 if (minDelta > maxDelta)
334 std::swap(minDelta, maxDelta);
335 if (minDeltaRef > maxDeltaRef)
336 std::swap(minDeltaRef, maxDeltaRef);
338 if (maxDelta*minDeltaRef < minDelta*maxDeltaRef)
347 for (
typename map<orientation_2d, point_set_type>::iterator it =
m_mPoint.begin();
352 point_set_type
const& vPoint = it->second;
353 assert(vPoint.empty() || !vPoint.empty());
380 bool read(
string const& filename)
382 ifstream in (filename.c_str());
385 cout <<
"failed to open " << filename << endl;
393 std::vector<point_type> vPoint;
398 if (tag ==
"polygon" && status == 0)
402 else if (tag ==
"from" || tag ==
"to")
405 coordinate_type value[2] = {0, 0};
408 while (!in.eof() && i < 2)
411 boost::trim_if(value_str, boost::is_any_of(
", \t\\"));
414 value[i] = boost::lexical_cast<coordinate_type>(value_str);
420 if (i != 2)
return false;
423 this->
set(vPoint.back(), HORIZONTAL, value[0]);
424 this->
set(vPoint.back(), VERTICAL, value[1]);
426 else if (status == 1)
433 this->
initialize(vPoint.begin(), vPoint.end());
441 void print(
string const& filename)
const
443 ofstream out (filename.c_str());
446 cout <<
"failed to open " << filename << endl;
450 point_set_type
const& vPoint =
m_mPoint.begin()->second;
452 if (vPoint.size() > 0)
454 out <<
"set obj " << i++ <<
" ";
455 out <<
"polygon \\" << endl;
456 for (
typename point_set_type::const_iterator it = vPoint.begin(); it != vPoint.end(); ++it)
458 if (it == vPoint.begin())
459 out <<
"from " << this->
get(*it, HORIZONTAL) <<
", " << this->
get(*it, VERTICAL) <<
" \\" << endl;
461 out <<
"to " << this->
get(*it, HORIZONTAL) <<
", " << this->
get(*it, VERTICAL) <<
" \\" << endl;
467 for (
typename rectangle_set_type::const_iterator it =
m_vRect.begin(); it !=
m_vRect.end(); ++it)
470 out <<
"set obj " << i <<
" rectangle ";
471 out <<
"from " << this->
get(*it, LEFT) <<
", " << this->
get(*it, BOTTOM) <<
" "
472 <<
"to " << this->
get(*it, RIGHT) <<
", " << this->
get(*it, TOP) <<
" ";
473 out <<
"fc rgb \"dark-grey\" fs transparent pattern 4 bo"<< endl;
475 out <<
"set label \'" << i <<
"\' at "
476 << (this->
get(*it, LEFT)+this->
get(*it, RIGHT))/2.0 <<
", " << (this->
get(*it, BOTTOM)+this->
get(*it, TOP))/2.0 <<
" "
477 <<
"front center tc rgb \"black\"" << endl;
523 inline bool operator() (point_type
const& p1, point_type
const& p2)
const
536 switch (slicing_orient)
538 case HORIZONTAL_SLICING:
544 case VERTICAL_SLICING:
563 cout <<
"unknown slicing orientation" << endl;
578 point_set_type
const& vPoint =
m_mPoint[orient];
579 if (vPoint.size() < 4)
584 this->
set(Pk, HORIZONTAL, this->
get(*vPoint.begin(), HORIZONTAL));
585 this->
set(Pk, VERTICAL, this->
get(*vPoint.begin(), VERTICAL));
587 this->
set(Pl, HORIZONTAL, this->
get(*(++(vPoint.begin())), HORIZONTAL));
588 this->
set(Pl, VERTICAL, this->
get(*(++(vPoint.begin())), VERTICAL));
592 for (
typename point_set_type::const_iterator it = vPoint.begin(); it != vPoint.end(); ++it)
594 if (this->
get(Pk, orient) == this->
get(*it, orient))
599 assert(this->
get(*it, orient) > this->
get(Pk, orient));
600 this->
set(Pm, HORIZONTAL, this->
get(*it, HORIZONTAL));
601 this->
set(Pm, VERTICAL, this->
get(*it, VERTICAL));
619 point_set_type& vPoint =
m_mPoint[orient];
622 typename point_set_type::iterator itr = std::lower_bound(vPoint.begin(), vPoint.end(), point,
point_compare_type(orient));
634 coordinate_type getHorRangeNext(coordinate_type
const& x1, coordinate_type
const& x2, coordinate_type
const& min_y)
const
639 for (
typename point_set_type::const_iterator it = m_vPoint.begin(); it != m_vPoint.end(); ++it)
641 coordinate_type x = this->
get(*it, HORIZONTAL), y = this->
get(*it, VERTICAL);
642 if (x<x1 || x>x2)
continue;
643 if (y <= min_y)
continue;
644 if (y >= next_y)
continue;
652 coordinate_type getVerRangeNext(coordinate_type
const& y1, coordinate_type
const& y2, coordinate_type
const& min_x)
const
656 for (
typename point_set_type::const_iterator it = m_vPoint.begin(); it != m_vPoint.end(); ++it)
658 coordinate_type x = this->
get(*it, HORIZONTAL), y = this->
get(*it, VERTICAL);
659 if (y<y1 || y>y2)
continue;
660 if (x <= min_x)
continue;
661 if (x >= next_x)
continue;
697 template <
typename InputIterator,
typename Po
intSet,
typename RectSet>
702 if (!p2r())
return false;
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
static void set(rectangle_type &rectangle, direction_2d const &direct, coordinate_type const &v)
set coordinate for rectangle
bool valid() const
check whether the orientation is valid
void set(rectangle_type &r, direction_2d d, coordinate_type v) const
set coordinate of rectangle
rectangle_set_type const & get_rectangles() const
get rectangles
map< orientation_2d, point_set_type > m_mPoint
void initialize(slicing_orientation_2d slicing_orient)
initialize with slicing orientation it must be called before initializing other data ...
static void set(point_type &point, orientation_2d const &orient, coordinate_type const &value)
set coordinate for point
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
Contains utilities for geometric types, such as type traits, area calculator. I'm trying to make thes...
PointSet point_set_type
internal point set type
slicing_orientation_2d
orientation type for slicing
bool read(string const &filename)
read polygon from file try to be compatible to gnuplot format
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
coordinate_traits< coordinate_type >::coordinate_distance coordinate_distance
coordinate distance type
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
bool is_number(string const &s)
check whether string represents a number, either integer or floating point number ...
Polygon2Rectangle(rectangle_set_type &vRect, slicing_orientation_2d slicing_orient=HORIZONTAL_SLICING)
constructor
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 ...
coordinate_traits< coordinate_type >::manhattan_area_type manhattan_area_type
manhattan area type
RectSet rectangle_set_type
internal rectangle set type
bool polygon2rectangle(InputIterator input_begin, InputIterator input_end, PointSet const &, RectSet &r, slicing_orientation_2d slicing_orient=HORIZONTAL_SLICING)
standby function for polygon-to-rectangle conversion
orientation_2d get_perpendicular() const
get perpendicular orientation
container_traits< point_set_type >::value_type point_type
internal point type
point_traits< point_type >::coordinate_type coordinate_type
point set type for polygon
orientation_2d m_orient
orientation, HORIZONTAL or VERTICAL
std::iterator_traits< Iterator >::value_type max(Iterator first, Iterator last)
get max of an array
point_compare_type(orientation_2d const &ori)
void print(string const &filename) const
print polygon to file in gnuplot format
type traits for coordinates
bool operator()()
top api for limbo::geometry::Polygon2Rectangle
static void insert(container_type &container, value_type const &v)
insert value to container
void F(point_type const &point, orientation_2d const &orient)
F function in the original paper remove point if found, otherwise insert.
Check string is integer, floating point, number... Convert string to upper/lower cases.
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
Polygon2Rectangle(rectangle_set_type &vRect, InputIterator input_begin, InputIterator input_end, slicing_orientation_2d slicing_orient)
constructor
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
container_traits< rectangle_set_type >::value_type rectangle_type
internal rectangle type
#define assert_msg(condition, message)
assertion with message
a class denoting orientation of lines
void initialize(InputIterator input_begin, InputIterator input_end)
initialize polygon points
a template specialization for std::vector. It is more efficient than generic version ...
bool operator()(PointType const &p1, PointType const &p2) const
compare two points at specific orientation