src/view/poly_shape_hit_test.cpp

   1 /* Copyright (c) 2010-2014 Samsung Electronics Co., Ltd. All rights reserved.
   2  *
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17
  18 #include "poly_shape_hit_test.h"
  19 #include <climits>
  20 #include <math.h>
  21
  22
  23 //LCOV_EXCL_START
  24 void view::poly_shape_hit_test::add_point(const float x, const float y)
  25 {
  26         __x.push_back(x);
  27         __y.push_back(y);
  28 }
  29
  30 bool view::poly_shape_hit_test::hit_test(const float x, const float y,
  31         const bool polygon, const int w) const
  32 {
  33         if (__x.empty())
  34                 return false;
  35
  36         /* 1. Check if the point in the bounding box of a poly-figure */
  37         if (!hit_test_bounding_box(x, y))
  38                 return false;
  39
  40         /* 2. Check if the point near the polyline */
  41         if (hit_test_polyline(x, y, polygon, w))
  42                 return true;
  43
  44         /* 3. Check if the point near the vertices */
  45         if (hit_test_vertices(x, y))
  46                 return true;
  47
  48         /* 4. Check if the point inside the polygon (for polygon only) */
  49         if (polygon)
  50                 if (pnpoly(x, y))
  51                         return true;
  52
  53         return false;
  54 }
  55
  56 bool view::poly_shape_hit_test::hit_test_bounding_box(const float x, const float y) const
  57 {
  58         float x_min = 1. * FLT_MAX;
  59         float x_max = 1. * FLT_MIN;
  60         float y_min = 1. * FLT_MAX;
  61         float y_max = 1. * FLT_MIN;
  62         for (unsigned int i = 0; i < __x.size(); i ++) {
  63                 if (__x[i] < x_min)
  64                         x_min = __x[i];
  65                 if (__x[i] > x_max)
  66                         x_max = __x[i];
  67                 if (__y[i] < y_min)
  68                         y_min = __y[i];
  69                 if (__y[i] > y_max)
  70                         y_max = __y[i];
  71         }
  72         x_min -= accuracy;
  73         x_max += accuracy;
  74         y_min -= accuracy;
  75         y_max += accuracy;
  76
  77         return ((x >= x_min) && (x <= x_max)
  78                 && (y >= y_min) && (y <= y_max));
  79 }
  80
  81 bool view::poly_shape_hit_test::hit_test_segment(const float x1, const float y1,
  82         const float x2, const float y2, const float x, const float y, const int w) const
  83 {
  84         float a = x2 - x1;
  85         float b = y2 - y1;
  86         float c = sqrt(a * a + b * b);
  87         if (c == 0)
  88                 return false;
  89         float sina = b / c;
  90         float cosa = a / c;
  91
  92         float x_shifted = x - x1;
  93         float y_shifted = y - y1;
  94         float x_rotated = x_shifted * cosa + y_shifted * sina;
  95         float y_rotated = x_shifted * sina - y_shifted * cosa;
  96
  97         if ((x_rotated >= 0) && (x_rotated <= c)
  98            && (y_rotated >= (-1. * (accuracy + w / 2)))
  99            && (y_rotated <=  (accuracy + w / 2)))
 100                 return true;
 101         return false;
 102 }
 103
 104 bool view::poly_shape_hit_test::hit_test_polyline(const float x, const float y,
 105                                         const bool polygon, const int w) const
 106 {
 107         if (__x.size() < 1)
 108                 return false;
 109
 110         for (unsigned int i = 1; i < __x.size(); i ++) {
 111                 if (hit_test_segment(__x[i - 1], __y[i - 1],
 112                                     __x[i], __y[i], x, y, w))
 113                         return true;
 114         }
 115
 116         if (polygon) {
 117                 /* Final section */
 118                 if (hit_test_segment(__x[__x.size() - 1], __y[__x.size() - 1],
 119                                     __x[0], __y[0], x, y))
 120                         return true;
 121         }
 122
 123         return false;
 124 }
 125
 126 bool view::poly_shape_hit_test::hit_test_vertices(const float x, const float y) const
 127 {
 128         for (unsigned int i = 0; i < __x.size(); i ++) {
 129                 float cur_x_min = __x[i] - accuracy;
 130                 float cur_x_max = __x[i] + accuracy;
 131                 float cur_y_min = __y[i] - accuracy;
 132                 float cur_y_max = __y[i] + accuracy;
 133                 if ((x >= cur_x_min) && (x <= cur_x_max)
 134                     && (y >= cur_y_min) && (y <= cur_y_max))
 135                         return true;
 136         }
 137         return false;
 138 }
 139
 140 /*
 141  * PNPOLY
 142  * http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
 143  */
 144 bool view::poly_shape_hit_test::pnpoly(const float x, const float y) const
 145 {
 146         int i, j, c = 0;
 147         const int nvert = int(__x.size());
 148         for (i = 0, j = nvert-1; i < nvert; j = i++) {
 149                 if ( ((__y[i] > y) != (__y[j] > y)) &&
 150                      (x < (__x[j] - __x[i]) * (y - __y[i])
 151                       / (__y[j] - __y[i]) + __x[i]) ) {
 152                         c = !c;
 153                 }
 154         }
 155         return (c != 0);
 156 }
 157 //LCOV_EXCL_STOP