17 #include <boost/math/constants/constants.hpp>
25 :
Polyline(ply), _aabb(ply.getPointsVec(), ply._ply_pnt_ids)
38 for (sub_polygon_it++;
67 WARN(
"Polygon::initialise(): base polyline is not closed.");
76 if (pnt[0] < min_aabb_pnt[0] || max_aabb_pnt[0] < pnt[0] ||
77 pnt[1] < min_aabb_pnt[1] || max_aabb_pnt[1] < pnt[1])
84 std::size_t n_intersections(0);
86 for (std::size_t k(0); k < n_nodes; k++)
88 if (((*(
getPoint(k)))[1] <= pnt[1] &&
89 pnt[1] <= (*(
getPoint(k + 1)))[1]) ||
90 ((*(
getPoint(k + 1)))[1] <= pnt[1] &&
108 if (n_intersections % 2 == 1)
119 if ((*it)->isPntInPolygon(pnt))
131 std::vector<GeoLib::Point> intersections;
133 for (
auto&& seg_it : *
this)
137 intersections.push_back(s);
141 return intersections;
156 const double tol(std::numeric_limits<float>::epsilon());
162 if (sqr_dist_as < tol)
168 if (sqr_dist_bs < tol)
176 std::sort(s.begin(), s.end(),
178 { return MathLib::sqrDist(a, p0) < MathLib::sqrDist(a, p1); });
181 for (std::size_t k(0); k < s.size() - 1;)
185 s.erase(s.begin() + k + 1);
195 0.5 * (a[1] + s[0][1]),
196 0.5 * (a[2] + s[0][2]))))
200 const std::size_t n_sub_segs(s.size() - 1);
201 for (std::size_t k(0); k < n_sub_segs; k++)
204 0.5 * (s[k][1] + s[k + 1][1]),
205 0.5 * (s[k][2] + s[k + 1][2]))))
211 0.5 * (s[0][1] + b[1]),
212 0.5 * (s[0][2] + b[2])));
217 return std::all_of(ply.
begin(), ply.
end(),
218 [
this](
auto const& segment)
219 { return containsSegment(segment); });
226 for (std::size_t k(0); k < ply_size; k++)
234 auto polygon_segment_intersects_line = [&](
auto const& polygon_seg)
237 return std::any_of(ply.
begin(), ply.
end(),
238 [&polygon_seg, &s](
auto const& polyline_seg) {
239 return GeoLib::lineSegmentIntersect(
240 polyline_seg, polygon_seg, s);
244 return any_of(std::cbegin(*
this), std::cend(*
this),
245 polygon_segment_intersects_line);
250 std::size_t& seg_num)
const
254 for (
auto seg_it(
begin() + seg_num); seg_it !=
end(); ++seg_it)
258 seg_num = seg_it.getSegmentNumber();
267 for (
auto seg_it(polygon->begin()); seg_it != polygon->end();
273 seg_num = seg_it.getSegmentNumber();
290 if (v[1] < pnt[1] && pnt[1] <= w[1])
301 if (w[1] < pnt[1] && pnt[1] <= v[1])
322 std::vector<GeoLib::Point*> tmp_polygon_pnts;
323 for (std::size_t k(0); k < n_pnts; k++)
331 for (
auto& tmp_polygon_pnt : tmp_polygon_pnts)
333 (*tmp_polygon_pnt)[2] =
338 std::size_t min_x_max_y_idx(0);
339 for (std::size_t k(0); k < n_pnts; k++)
341 if ((*(tmp_polygon_pnts[k]))[0] <=
342 (*(tmp_polygon_pnts[min_x_max_y_idx]))[0])
344 if ((*(tmp_polygon_pnts[k]))[0] <
345 (*(tmp_polygon_pnts[min_x_max_y_idx]))[0])
349 else if ((*(tmp_polygon_pnts[k]))[1] >
350 (*(tmp_polygon_pnts[min_x_max_y_idx]))[1])
358 if (0 < min_x_max_y_idx && min_x_max_y_idx < n_pnts - 2)
361 *tmp_polygon_pnts[min_x_max_y_idx],
362 *tmp_polygon_pnts[min_x_max_y_idx + 1]);
366 if (0 == min_x_max_y_idx)
369 *tmp_polygon_pnts[0],
370 *tmp_polygon_pnts[1]);
375 *tmp_polygon_pnts[n_pnts - 1],
376 *tmp_polygon_pnts[0]);
383 std::size_t tmp_n_pnts(n_pnts);
386 for (std::size_t k(0); k < tmp_n_pnts / 2; k++)
392 for (std::size_t k(0); k < n_pnts; k++)
394 delete tmp_polygon_pnts[k];
399 const std::list<Polygon*>::const_iterator& polygon_it)
413 std::size_t
const intersection_pnt_id(
_ply_pnts.size());
414 const_cast<std::vector<Point*>&
>(
_ply_pnts).push_back(
420 std::swap(idx0, idx1);
424 for (std::size_t k(0); k <= idx0; k++)
426 polyline0.addPoint((*polygon_it)->getPointID(k));
428 polyline0.addPoint(intersection_pnt_id);
429 for (std::size_t k(idx1 + 1); k < (*polygon_it)->getNumberOfPoints(); k++)
431 polyline0.addPoint((*polygon_it)->getPointID(k));
435 polyline1.addPoint(intersection_pnt_id);
436 for (std::size_t k(idx0 + 1); k <= idx1; k++)
438 polyline1.addPoint((*polygon_it)->getPointID(k));
440 polyline1.addPoint(intersection_pnt_id);
443 if (*polygon_it !=
this)
458 const std::list<GeoLib::Polygon*>::iterator& polygon_it)
460 std::size_t
const n((*polygon_it)->getNumberOfPoints() - 1);
461 std::vector<std::size_t> id_vec(n);
462 std::vector<std::size_t> perm(n);
463 for (std::size_t k(0); k < n; k++)
465 id_vec[k] = (*polygon_it)->getPointID(k);
471 for (std::size_t k(0); k < n - 1; k++)
473 if (id_vec[k] == id_vec[k + 1])
475 std::size_t idx0 = perm[k];
476 std::size_t idx1 = perm[k + 1];
480 std::swap(idx0, idx1);
485 for (std::size_t j(0); j <= idx0; j++)
487 polyline0.
addPoint((*polygon_it)->getPointID(j));
489 for (std::size_t j(idx1 + 1);
490 j < (*polygon_it)->getNumberOfPoints();
493 polyline0.addPoint((*polygon_it)->getPointID(j));
497 for (std::size_t j(idx0); j <= idx1; j++)
499 polyline1.
addPoint((*polygon_it)->getPointID(j));
503 if (*polygon_it !=
this)
511 polygon1_it,
new Polygon(polyline0));
529 const std::size_t start_pnt(lhs.
getPointID(0));
534 for (; k < n - 1 && nfound; k++)
553 for (k = 1; k < n - 1; k++)
567 std::size_t j(k + 2);
568 for (; j < n - 1; j++)
576 for (; j < k + 1; j++)
589 "operator==(Polygon const& lhs, Polygon const& rhs) - not tested case "
590 "(implementation is probably buggy) - please contact "
591 "thomas.fischer@ufz.de mentioning the problem.");
595 std::size_t j(k - 2);
606 for (; j > k - 1; j--)
625 polygon->initialise();
Definition of analytical geometry functions.
void WARN(char const *fmt, Args const &... args)
Definition of the Polygon class.
Eigen::Vector3d const & getMinPoint() const
Eigen::Vector3d const & getMaxPoint() const
GeoLib::Point const & getBeginPoint() const
GeoLib::Point const & getEndPoint() const
std::list< Polygon * > const & computeListOfSimplePolygons()
bool isPolylineInPolygon(const Polyline &ply) const
void splitPolygonAtPoint(const std::list< Polygon * >::iterator &polygon_it)
std::vector< GeoLib::Point > getAllIntersectionPoints(GeoLib::LineSegment const &segment) const
void splitPolygonAtIntersection(const std::list< Polygon * >::const_iterator &polygon_it)
bool isPartOfPolylineInPolygon(const Polyline &ply) const
bool isPntInPolygon(const MathLib::Point3d &pnt) const
bool containsSegment(GeoLib::LineSegment const &segment) const
EdgeType getEdgeType(std::size_t k, MathLib::Point3d const &pnt) const
std::list< Polygon * > _simple_polygon_list
bool getNextIntersectionPointPolygonLine(GeoLib::LineSegment const &seg, GeoLib::Point &intersection_pnt, std::size_t &seg_num) const
void ensureCCWOrientation()
std::size_t getSegmentNumber() const
Class Polyline consists mainly of a reference to a point vector and a vector that stores the indices ...
std::size_t getPointID(std::size_t i) const
std::size_t getNumberOfPoints() const
const Point * getPoint(std::size_t i) const
returns the i-th point contained in the polyline
std::vector< std::size_t > _ply_pnt_ids
SegmentIterator begin() const
virtual bool addPoint(std::size_t pnt_id)
const std::vector< Point * > & _ply_pnts
Location getLocationOfPoint(std::size_t k, MathLib::Point3d const &pnt) const
SegmentIterator end() const
std::vector< Point * > const & getPointsVec() const
@ INESSENTIAL
INESSENTIAL.
void quicksort(It1 first1, It1 last1, It2 first2, Comparator compare)
bool lineSegmentsIntersect(const GeoLib::Polyline *ply, GeoLib::Polyline::SegmentIterator &seg_it0, GeoLib::Polyline::SegmentIterator &seg_it1, GeoLib::Point &intersection_pnt)
Eigen::Matrix3d rotatePointsToXY(InputIterator1 p_pnts_begin, InputIterator1 p_pnts_end, InputIterator2 r_pnts_begin, InputIterator2 r_pnts_end)
bool operator==(LineSegment const &s0, LineSegment const &s1)
bool lineSegmentIntersect(GeoLib::LineSegment const &s0, GeoLib::LineSegment const &s1, GeoLib::Point &s)
Orientation getOrientation(MathLib::Point3d const &p0, MathLib::Point3d const &p1, MathLib::Point3d const &p2)
double sqrDist(MathLib::Point3d const &p0, MathLib::Point3d const &p1)
Definition of the quicksort function.