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 void view::poly_shape_hit_test::add_point(const float x, const float y)
  24 {
  25         __x.push_back(x);
  26         __y.push_back(y);
  27 }
  28
  29 bool view::poly_shape_hit_test::hit_test(const float x, const float y,
  30         const bool polygon, const int w) const
  31 {
  32         if (__x.empty())
  33                 return false;
  34
  35         /* 1. Check if the point in the bounding box of a poly-figure */
  36         if (!hit_test_bounding_box(x, y))
  37                 return false;
  38
  39         /* 2. Check if the point near the polyline */
  40         if (hit_test_polyline(x, y, polygon, w))
  41                 return true;
  42
  43         /* 3. Check if the point near the vertices */
  44         if (hit_test_vertices(x, y))
  45                 return true;
  46
  47         /* 4. Check if the point inside the polygon (for polygon only) */
  48         if (polygon)
  49                 if (pnpoly(x, y))
  50                         return true;
  51
  52         return false;
  53 }
  54
  55 bool view::poly_shape_hit_test::hit_test_bounding_box(const float x, const float y) const
  56 {
  57         float x_min = 1. * FLT_MAX;
  58         float x_max = 1. * FLT_MIN;
  59         float y_min = 1. * FLT_MAX;
  60         float y_max = 1. * FLT_MIN;
  61         for (unsigned int i = 0; i < __x.size(); i ++) {
  62                 if (__x[i] < x_min)
  63                         x_min = __x[i];
  64                 if (__x[i] > x_max)
  65                         x_max = __x[i];
  66                 if (__y[i] < y_min)
  67                         y_min = __y[i];
  68                 if (__y[i] > y_max)
  69                         y_max = __y[i];
  70         }
  71         x_min -= accuracy;
  72         x_max += accuracy;
  73         y_min -= accuracy;
  74         y_max += accuracy;
  75
  76         return ((x >= x_min) && (x <= x_max)
  77                 && (y >= y_min) && (y <= y_max));
  78 }
  79
  80 bool view::poly_shape_hit_test::hit_test_segment(const float x1, const float y1,
  81         const float x2, const float y2, const float x, const float y, const int w) const
  82 {
  83         float a = x2 - x1;
  84         float b = y2 - y1;
  85         float c = sqrt(a * a + b * b);
  86         if (c == 0)
  87                 return false;
  88         float sina = b / c;
  89         float cosa = a / c;
  90
  91         float x_shifted = x - x1;
  92         float y_shifted = y - y1;
  93         float x_rotated = x_shifted * cosa + y_shifted * sina;
  94         float y_rotated = x_shifted * sina - y_shifted * cosa;
  95
  96         if ((x_rotated >= 0) && (x_rotated <= c)
  97            && (y_rotated >= (-1. * (accuracy + w / 2)))
  98            && (y_rotated <=  (accuracy + w / 2)))
  99                 return true;
 100         return false;
 101 }
 102
 103 bool view::poly_shape_hit_test::hit_test_polyline(const float x, const float y,
 104                                         const bool polygon, const int w) const
 105 {
 106         if (__x.size() < 1)
 107                 return false;
 108
 109         for (unsigned int i = 1; i < __x.size(); i ++) {
 110                 if (hit_test_segment(__x[i - 1], __y[i - 1],
 111                                     __x[i], __y[i], x, y, w))
 112                         return true;
 113         }
 114
 115         if (polygon) {
 116                 /* Final section */
 117                 if (hit_test_segment(__x[__x.size() - 1], __y[__x.size() - 1],
 118                                     __x[0], __y[0], x, y))
 119                         return true;
 120         }
 121
 122         return false;
 123 }
 124
 125 bool view::poly_shape_hit_test::hit_test_vertices(const float x, const float y) const
 126 {
 127         for (unsigned int i = 0; i < __x.size(); i ++) {
 128                 float cur_x_min = __x[i] - accuracy;
 129                 float cur_x_max = __x[i] + accuracy;
 130                 float cur_y_min = __y[i] - accuracy;
 131                 float cur_y_max = __y[i] + accuracy;
 132                 if ((x >= cur_x_min) && (x <= cur_x_max)
 133                     && (y >= cur_y_min) && (y <= cur_y_max))
 134                         return true;
 135         }
 136         return false;
 137 }
 138
 139 /*
 140  * PNPOLY
 141  * http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
 142  */
 143 bool view::poly_shape_hit_test::pnpoly(const float x, const float y) const
 144 {
 145         int i, j, c = 0;
 146         const int nvert = int(__x.size());
 147         for (i = 0, j = nvert-1; i < nvert; j = i++) {
 148                 if ( ((__y[i] > y) != (__y[j] > y)) &&
 149                      (x < (__x[j] - __x[i]) * (y - __y[i])
 150                       / (__y[j] - __y[i]) + __x[i]) ) {
 151                         c = !c;
 152                 }
 153         }
 154         return (c != 0);
 155 }