140 lines
3.2 KiB
C++
140 lines
3.2 KiB
C++
/*
|
||
* © Copyright 2014 – Urheberrechtshinweis
|
||
* Alle Rechte vorbehalten / All Rights Reserved
|
||
*
|
||
* Programmcode ist urheberrechtlich geschuetzt.
|
||
* Das Urheberrecht liegt, soweit nicht ausdruecklich anders gekennzeichnet, bei Frank Ebner.
|
||
* Keine Verwendung ohne explizite Genehmigung.
|
||
* (vgl. § 106 ff UrhG / § 97 UrhG)
|
||
*/
|
||
|
||
#ifndef POLYGON2_H
|
||
#define POLYGON2_H
|
||
|
||
#include "Point2.h"
|
||
#include <vector>
|
||
#include "Line2.h"
|
||
#include "BBox2.h"
|
||
|
||
static bool polygonContainsPoint(const std::vector<Point2>& poly, const Point2 p);
|
||
|
||
class Polygon2 {
|
||
|
||
std::vector<Point2> pts;
|
||
|
||
public:
|
||
|
||
void add(const Point2 p) {
|
||
pts.push_back(p);
|
||
}
|
||
|
||
void add(std::initializer_list<Point2> lst) {
|
||
for (const Point2 p : lst) {add(p);}
|
||
}
|
||
|
||
std::vector<Point2>::iterator begin() {return pts.begin();}
|
||
std::vector<Point2>::iterator end() {return pts.end();}
|
||
|
||
std::vector<Point2>::const_iterator begin() const {return pts.begin();}
|
||
std::vector<Point2>::const_iterator end() const {return pts.end();}
|
||
|
||
std::vector<Point2>& getVector() {return pts;}
|
||
|
||
Point2& operator [] (const size_t idx) {
|
||
return pts[idx];
|
||
}
|
||
|
||
|
||
|
||
/** get polygon as list of lines */
|
||
std::vector<Line2> getLines() const {
|
||
std::vector<Line2> res;
|
||
for (size_t i = 0; i < pts.size(); ++i) {
|
||
const Point2 p1 = pts[(i+0)];
|
||
const Point2 p2 = pts[(i+1)%pts.size()];
|
||
res.push_back(Line2(p1, p2));
|
||
}
|
||
return res;
|
||
}
|
||
|
||
struct CutRes {
|
||
Point2 p;
|
||
size_t i1,i2; // line, given by two points, within this poly
|
||
size_t j1,j2; // line, given by two points, within other, given poly
|
||
CutRes(Point2 p, size_t i1, size_t i2, size_t j1, size_t j2) : p(p), i1(i1), i2(i2), j1(j1), j2(j2) {;}
|
||
};
|
||
|
||
|
||
BBox2 getBBox() const {
|
||
BBox2 bb;
|
||
for (const Point2 p : pts) {bb.add(p);}
|
||
return bb;
|
||
}
|
||
|
||
|
||
bool contains(const Point2 p) const {
|
||
return polygonContainsPoint(pts, p);
|
||
}
|
||
|
||
std::vector<CutRes> getIntersections(const Polygon2& o, bool limit = true) const {
|
||
|
||
std::vector<CutRes> res;
|
||
for (size_t i = 0; i < pts.size(); ++i) {
|
||
const size_t i1 = (i+0);
|
||
const size_t i2 = (i+1) % pts.size();
|
||
const Line2 l1(pts[i1], pts[i2]);
|
||
|
||
for (size_t j = 0; j < o.pts.size(); ++j) {
|
||
const size_t j1 = (j+0);
|
||
const size_t j2 = (j+1) % o.pts.size();
|
||
const Line2 l2(o.pts[j1], o.pts[j2]);
|
||
|
||
Point2 p;
|
||
//if (l1.getSegmentIntersection(l2, p)) {
|
||
if (intersects(l1, l2, limit, p)) {
|
||
res.push_back(CutRes(p, i1,i2, j1,j2));
|
||
}
|
||
}
|
||
}
|
||
|
||
return res;
|
||
|
||
}
|
||
|
||
};
|
||
|
||
/** does the given polygon (list of points) contain the given point? */
|
||
static bool polygonContainsPoint(const std::vector<Point2>& poly, const Point2 p) {
|
||
|
||
// https://en.wikipedia.org/wiki/Winding_number
|
||
// http://geomalgorithms.com/a03-_inclusion.html
|
||
|
||
// BBox2 bb
|
||
// bb.grow(Point2(0.001, 0.001));
|
||
// if (!bb.contains(p)) {return false;}
|
||
|
||
double sum = 0;
|
||
for (size_t i = 0; i < poly.size(); ++i) {
|
||
|
||
const Point2 p1 = poly[i];
|
||
const Point2 p2 = poly[(i+1)%poly.size()];
|
||
|
||
const Point2 d1 = (p1-p).normalized();
|
||
const Point2 d2 = (p2-p).normalized();
|
||
|
||
sum += std::acos(dot(d1, d2));
|
||
|
||
}
|
||
|
||
// normalize (x = number of windings)
|
||
const double x = sum / M_PI / 2;
|
||
|
||
// only look at the fractional part
|
||
//const double y = x - std::floor(x);
|
||
|
||
return std::abs(x) >= 0.995;// && (std::abs(y) >= 0.9 || std::abs(y) < 0.1);
|
||
|
||
}
|
||
|
||
#endif // POLYGON2_H
|