graphiq/library/geometric/polygon.cpp

   1
   2
   3
   4 /*****************************************************************************\
   5 *                                                                             *
   6 *  Name   : polygon                                                           *
   7 *  Author : Chris Koeritz                                                     *
   8 *                                                                             *
   9 *******************************************************************************
  10 * Copyright (c) 1992-$now By Author.  This program is free software; you can  *
  11 * redistribute it and/or modify it under the terms of the GNU General Public  *
  12 * License as published by the Free Software Foundation; either version 2 of   *
  13 * the License or (at your option) any later version.  This is online at:      *
  14 *     http://www.fsf.org/copyleft/gpl.html                                    *
  15 * Please send any updates to: fred@gruntose.com                               *
  16 \*****************************************************************************/
  17
  18 #include "polygon.h"
  19
  20 #include <basis/array.h>
  21
  22 using namespace basis;
  23
  24 namespace geometric {
  25
  26 bool polygon::inside(const cartesian_point &to_check)
  27 {
  28   int right_intersect_count = 0;
  29   for (int i = 0; i < length(); i++) {
  30     cartesian_point vert_1 = get(i);
  31     cartesian_point vert_2 = get( (i + 1) % length() );
  32     if ( (to_check.y() < minimum(vert_1.y(), vert_2.y()))
  33         || (to_check.y() > maximum(vert_1.y(), vert_2.y())) ) continue;
  34     double x_intersect;
  35     if (vert_2.x() == vert_1.x()) {
  36       x_intersect = vert_2.x();
  37     } else {
  38       double m = (vert_2.y() - vert_1.y()) / (vert_2.x() - vert_1.x());
  39       x_intersect = 1.0 / m * (to_check.y() - vert_1.y() + m * vert_1.x());
  40     }
  41     if (x_intersect > to_check.x()) right_intersect_count++;
  42   }
  43   return !!(right_intersect_count % 2);
  44 }
  45
  46 }
  47
  48
  49
  50