[Boost-commit] svn:boost r80583 - trunk/boost/polygon/detail

Subject: [Boost-commit] svn:boost r80583 - trunk/boost/polygon/detail
From: sydorchuk.andriy_at_[hidden]
Date: 2012-09-18 15:53:57

Author: asydorchuk
Date: 2012-09-18 15:53:57 EDT (Tue, 18 Sep 2012)
New Revision: 80583
URL: http://svn.boost.org/trac/boost/changeset/80583

Log:
Polygon: acutally adding skeleton predicates header file.

Added:
   trunk/boost/polygon/detail/skeleton_predicates.hpp   (contents, props changed)

Added: trunk/boost/polygon/detail/skeleton_predicates.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/polygon/detail/skeleton_predicates.hpp	2012-09-18 15:53:57 EDT (Tue, 18 Sep 2012)
@@ -0,0 +1,204 @@
+// Boost.Polygon library detail/skeleton_predicates.hpp header file
+
+//          Copyright Andrii Sydorchuk 2012.
+//          Copyright Lucanus Simonson 2012.
+// Distributed under the Boost Software License, Version 1.0.
+//    (See accompanying file LICENSE_1_0.txt or copy at
+//          http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org for updates, documentation, and revision history.
+
+#ifndef BOOST_POLYGON_DETAIL_SKELETON_PREDICATES
+#define BOOST_POLYGON_DETAIL_SKELETON_PREDICATES
+
+#include <boost/cstdint.hpp>
+
+#include <cmath>
+
+#include "voronoi_ctypes.hpp"
+#include "voronoi_robust_fpt.hpp"
+
+namespace boost {
+namespace polygon {
+namespace detail {
+
+template <typename T>
+struct skeleton_ctype_traits;
+
+template <>
+struct skeleton_ctype_traits<int32> {
+  typedef int32 int_type;
+  typedef int64 int_x2_type;
+  typedef extended_int<16> big_int_type;
+  typedef fpt64 fpt_type;
+  typedef type_converter_fpt to_fpt_converter_type;
+};
+
+template <typename T>
+class intersection_event {
+ public:
+  typedef T coordinate_type;
+
+  intersection_event() {}
+
+  coordinate_type x() const { return x_; }
+  void x(const coordinate_type& val) { x_ = val; }
+
+  coordinate_type y() const { return y_; }
+  void y(const coordinate_type& val) { y_ = val; }
+
+  coordinate_type r() const { return r_; }
+  void r(const coordinate_type& val) { r_ = val; }
+
+ private:
+  coordinate_type x_;
+  coordinate_type y_;
+  coordinate_type r_;
+};
+
+template <typename CTYPE_TRAITS>
+class skeleton_predicates {
+ public:
+  typedef typename CTYPE_TRAITS::int_type int_type;
+  typedef typename CTYPE_TRAITS::int_x2_type int_x2_type;
+  typedef typename CTYPE_TRAITS::big_int_type big_int_type;
+  typedef typename CTYPE_TRAITS::fpt_type fpt_type;
+  typedef typename CTYPE_TRAITS::to_fpt_converter_type to_fpt_converter;
+
+  template <typename Segment>
+  class event_existence_predicate {
+   public:
+    typedef Segment segment_type;
+
+    bool operator()(const segment_type& segment1,
+                    const segment_type& segment2,
+                    const segment_type& segment3) {
+      // TODO(asydorchuk): For now don't do any checks and just return true.
+      // Should be enough to solve convex polygon case.
+      return true;
+    }
+  };
+
+  template <typename Segment, typename Event>
+  class mp_event_formation_functor {
+   public:
+    typedef Segment segment_type;
+    typedef Event event_type;
+    typedef robust_sqrt_expr<big_int_type, fpt_type, to_fpt_converter>
+        robust_sqrt_expr_type;
+
+    void operator()(
+        const segment_type& segment1,
+        const segment_type& segment2,
+        const segment_type& segment3,
+        event_type* event,
+        bool recompute_x = true,
+        bool recompute_y = true,
+        bool recompute_r = true) {
+      a[0] = static_cast<int_x2_type>(segment1.high().x()) -
+             static_cast<int_x2_type>(segment1.low().x());
+      a[1] = static_cast<int_x2_type>(segment2.high().x()) -
+             static_cast<int_x2_type>(segment2.low().x());
+      a[2] = static_cast<int_x2_type>(segment3.high().x()) -
+             static_cast<int_x2_type>(segment3.low().x());
+
+      b[0] = static_cast<int_x2_type>(segment1.high().y()) -
+             static_cast<int_x2_type>(segment1.low().y());
+      b[1] = static_cast<int_x2_type>(segment2.high().y()) -
+             static_cast<int_x2_type>(segment2.low().y());
+      b[2] = static_cast<int_x2_type>(segment3.high().y()) -
+             static_cast<int_x2_type>(segment3.low().y());
+
+      c[0] = static_cast<int_x2_type>(segment1.low().x()) *
+             static_cast<int_x2_type>(segment1.high().y()) -
+             static_cast<int_x2_type>(segment1.low().y()) *
+             static_cast<int_x2_type>(segment1.high().x());
+      c[1] = static_cast<int_x2_type>(segment2.low().x()) *
+             static_cast<int_x2_type>(segment2.high().y()) -
+             static_cast<int_x2_type>(segment2.low().y()) *
+             static_cast<int_x2_type>(segment2.high().x());
+      c[2] = static_cast<int_x2_type>(segment3.low().x()) *
+             static_cast<int_x2_type>(segment3.high().y()) -
+             static_cast<int_x2_type>(segment3.low().y()) *
+             static_cast<int_x2_type>(segment3.high().x());
+
+      for (int i = 0; i < 3; ++i) {
+        int j = (i+1) % 3;
+        int k = (i+2) % 3;
+        cA[i] = a[j] * b[k] - a[k] * b[j];
+        cB[i] = a[i] * a[i] + b[i] * b[i];
+      }
+      fpt_type inv_denom = 1.0 / to_fpt(sqrt_expr_.eval3(cA, cB));
+
+      if (recompute_r) {
+        for (int i = 0; i < 3; ++i) {
+          cA[i] = cA[i] * c[i];
+        }
+        fpt_type r = to_fpt(cA[0] + cA[1] + cA[2]);
+        event->r(r * inv_denom);
+        if (is_neg(event->r())) {
+          event->r(-event->r());
+	}
+      }
+
+      if (recompute_x) {
+        for (int i = 0; i < 3; ++i) {
+          int j = (i+1) % 3;
+          int k = (i+2) % 3;
+          cA[i] = a[j] * c[k] - a[k] * c[j];
+        }
+        fpt_type x = to_fpt(sqrt_expr_.eval3(cA, cB));
+        event->x(x * inv_denom);
+      }
+
+      if (recompute_y) {
+        for (int i = 0; i < 3; ++i) {
+          int j = (i+1) % 3;
+          int k = (i+2) % 3;
+          cA[i] = b[j] * c[k] - b[k] * c[j];
+        }
+        fpt_type y = to_fpt(sqrt_expr_.eval3(cA, cB));
+        event->y(y * inv_denom);
+      }
+    }
+
+   private:
+    big_int_type a[3];
+    big_int_type b[3];
+    big_int_type c[3];
+    big_int_type cA[3];
+    big_int_type cB[3];
+    to_fpt_converter to_fpt;
+    robust_sqrt_expr_type sqrt_expr_;
+  };
+
+  template <typename Segment,
+            typename Event,
+            typename EEP = event_existence_predicate<Segment>,
+            typename EFF = mp_event_formation_functor<Segment, Event> >
+  class event_formation_predicate {
+   public:
+    typedef Segment segment_type;
+    typedef Event event_type;
+    typedef EEP event_existence_predicate_type;
+    typedef EFF event_formation_functor_type;
+
+    bool operator()(const segment_type& segment1, const segment_type& segment2,
+                    const segment_type& segment3, event_type* event) {
+      if (!event_existence_predicate_(segment1, segment2, segment3)) {
+        return false;
+      }
+      event_formation_functor_(segment1, segment2, segment3, event);
+      return true;
+    }
+
+   private:
+    event_existence_predicate_type event_existence_predicate_;
+    event_formation_functor_type event_formation_functor_;
+  };
+};
+}  // detail
+}  // polygon
+}  // boost
+
+#endif  // BOOST_POLYGON_DETAIL_SKELETON_PREDICATES