1 #ifndef __JGEOMETRY2DTOOLKIT__
2 #define __JGEOMETRY2DTOOLKIT__
19 namespace JGEOMETRY2D {}
20 namespace JPP {
using namespace JGEOMETRY2D; }
22 namespace JGEOMETRY2D {
40 const double A = a.getX() - b.getX();
41 const double B = a.getY() - b.getY();
42 const double C = c.getX() - b.getX();
43 const double D = c.getY() - b.getY();
45 return (A*D - B*C) <= 0.0;
104 if (__begin != __end) {
106 for (T i = __begin; i != __end; ++i) {
110 div(std::distance(__begin, __end));
129 template<
class T,
class JCompare_t>
136 if (__begin != __end) {
138 sort(__begin, __end, compare);
148 for (T j, k; i != __end; ++i) {
150 for (j = k = l; j != __begin &&
getCCW(*i, *j, *--k); --j) {}
180 inline bool operator()(
const T& first,
const T& second)
const
182 if (first.getX() == second.getX())
183 return second.getY() > first.getY();
185 return first.getX() > second.getX();
202 inline bool operator()(
const T& first,
const T& second)
const
204 if (first.getX() == second.getX())
205 return second.getY() < first.getY();
207 return first.getX() < second.getX();
238 if (__p == __begin || __p == __end) {
239 return make_pair(__p, __p);
244 reverse(__begin, __p);
253 reverse(__begin, __q);
255 const int n = distance(__p, __q);
261 return make_pair(__p, __q);
284 if (distance(__begin,__end) >= 3) {
292 for (++j, ++(++k); k != __end; ++i, ++j, ++k) {
293 A += j->getX() * (k->getY() - i->getY());
298 A += j->getX() * (k->getY() - i->getY());
304 A += j->getX() * (k->getY() - i->getY());
306 return 0.5 * fabs(A);
328 if (distance(__begin,__end) >= 2) {
330 T i = __begin, j = __begin;
332 for (++j; j != __end; ++i, ++j) {
334 if (!
getCCW(*i, *j, pos)) {
341 return getCCW(*i, *j, pos);
364 if (distance(__begin,__end2) >= 3) {
366 if (pos.
getX() < __begin->getX()) {
378 if (!
getCCW(*i, *j, pos)) {
389 return getCCW(*i, *j, pos);
418 static double getDmin(T __begin, T __end,
const double delta)
424 sort(__begin, __end, compareY);
426 for (T i = __begin; i != __end; ++i) {
427 for (T j = i; ++j != __end && (j->getY() - i->getY()) < Dmin; ) {
437 sort(__begin, __end, compareX);
455 const int N = distance(__begin, __end);
459 double Dmin = numeric_limits<double>::max();
461 for (T i = __begin; i != __end; ++i) {
462 for (T j = i; ++j != __end; ) {
480 const double dl = getDmin(__begin, i);
481 const double dr = getDmin(i, __end);
483 const double Dmin = min(dl, dr);
488 while (--il != __begin && i ->getX() - il->getX() < Dmin) {}
489 while (++ir != __end && ir->getX() - i ->getX() < Dmin) {}
491 return min(Dmin, getDmin(++il, ir, Dmin));
508 inline bool operator()(
const T& first,
const T& second)
const
510 return first.getX() < second.getX();
527 inline bool operator()(
const T& first,
const T& second)
const
529 return first.getY() < second.getY();
559 sort(__begin, __end, compareX);
561 return getDmin(__begin, __end);
575 double operator()(T __begin, T __end,
const double delta)
const
581 sort(__begin, __end, compareX);
583 for (T i = __begin; i != __end; ) {
587 for ( ; ++j != __end && (j->getX() - i->getX()) < Dmin; ) {}
589 const double d = getDmin(i, j);
616 sort(__begin, __end, compareX);
618 for (T i = __begin; i != __end; ++i) {
622 while (++j != __end && (j->getX() - i->getX()) <= Dmax) {}
624 if (distance(i,j) != 1) {
626 if (distance(i,j) == 2) {
629 return make_pair(i,j);
634 sort(i, j, compareY);
636 for (T __i = i; __i != j; ++__i) {
637 for (T __j = __i; ++__j != j && (__j->getY() - __i->getY()) <= Dmax; ) {
642 return make_pair(__i,__j);
647 sort(i, j, compareX);
652 return make_pair(__end,__end);
Data structure for vector in two dimensions.
bool operator()(const T &first, const T &second) const
Compare y-positions of given points.
static std::pair< T, T > getPair(T __begin, T __end, const double Dmax)
Get pairs with smaller or equal given maximal distance.
static T getConvexHull2D(T __begin, T __end, JCompare_t compare)
Partition half Hull.
static double getDmin(T __begin, T __end, const double delta)
Get distance beween the closest points within a strip around the median in x.
double operator()(T __begin, T __end, const double delta) const
Get distance beween the closest points within a strip around the median in z.
Auxiliary class for sorting elements.
static const JCompareX compareX
Function object for sorting elements.
static const JSmallestDistance2D getSmallestDistance2D
Function object for smallest distance determination.
Auxiliary class for convex hull determination in X-Y plane.
Auxiliary class for sorting elements.
static const JLowerHull sortLowerHull
Function object for sorting elements.
bool operator()(const T &first, const T &second) const
Compare x-positions of given points.
bool getCCW(const T &a, const T &b, const T &c)
Check sequence of three points in X-Y plane.
double getDistance(const JFirst_t &first, const JSecond_t &second)
Get distance between objects.
bool operator()(const T &first, const T &second) const
Sort criterion for upper hull.
JCenter2D(const JVector2D &p0, const JVector2D &p1, const JVector2D &p2)
Constructor.
bool inside2D(T __begin, T __end, const JVector2D &pos)
Check if given point is inside a convex polygon.
JSmallestDistance2D()
Default constructor.
Auxiliary class for sorting elements.
static const JUpperHull sortUpperHull
Function object for sorting elements.
double getX() const
Get x position.
static const JCompareY compareY
Function object for sorting elements.
JVector2D & div(const double factor)
Scale vector.
counter_type advance(counter_type &counter, const counter_type value, const counter_type limit=std::numeric_limits< counter_type >::max())
Advance counter.
Auxiliary class for sorting elements.
JVector2D & add(const JVector2D &vector)
Add vector.
Auxiliary class for determination of smallest distance between pair of 2D points. ...
double getArea2D(T __begin, T __end)
Get area of a convex polygon.
double operator()(T __begin, T __end) const
Get smallest distance between two points.
static double getDmin(T __begin, T __end)
Recursive method to find the smallest distance.
JConvexHull2D()
Default constructor.
std::pair< T, T > operator()(T __begin, T __end) const
Get convex Hull.
bool operator()(const T &first, const T &second) const
Sort criterion for lower hull.
JCenter2D(const JVector2D &p0, const JVector2D &p1)
Constructor.
JCenter2D(T __begin, T __end)
Constructor.