cogl/cogl-point-in-poly.c

   1 /*
   2  * Point Inclusion in Polygon Test
   3  *
   4  * Copyright (c) 1970-2003, Wm. Randolph Franklin
   5  * Copyright (C) 2011 Intel Corporation.
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining
   8  * a copy of this software and associated documentation files (the
   9  * "Software"), to deal in the Software without restriction, including
  10  * without limitation the rights to use, copy, modify, merge, publish,
  11  * distribute, sublicense, and/or sell copies of the Software, and to
  12  * permit persons to whom the Software is furnished to do so, subject to
  13  * the following conditions:
  14  *
  15  * 1. Redistributions of source code must retain the above copyright
  16  *    notice, this list of conditions and the following disclaimers.
  17  *    2. Redistributions in binary form must reproduce the above
  18  *    copyright notice in the documentation and/or other materials
  19  *    provided with the distribution.
  20  * 3. The name of W. Randolph Franklin may not be used to endorse or
  21  *    promote products derived from this Software without specific
  22  *    prior written permission.
  23  *
  24  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  25  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  26  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  27  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  28  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  29  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  30  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  31  *
  32  * Note:
  33  * The algorithm for this point_in_poly() function was learnt from:
  34  * http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
  35  */
  36
  37 #ifdef HAVE_CONFIG_H
  38 #include "config.h"
  39 #endif
  40
  41 #include "cogl-util.h"
  42 #include "cogl-point-in-poly-private.h"
  43
  44 #include <glib.h>
  45
  46 /* We've made a notable change to the original algorithm referenced
  47  * above to make sure we have reliable results for screen aligned
  48  * rectangles even though there may be some numerical in-precision in
  49  * how the vertices of the polygon were calculated.
  50  *
  51  * We've avoided introducing an epsilon factor to the comparisons
  52  * since we feel there's a risk of changing some semantics in ways that
  53  * might not be desirable. One of those is that if you transform two
  54  * polygons which share an edge and test a point close to that edge
  55  * then this algorithm will currently give a positive result for only
  56  * one polygon.
  57  *
  58  * Another concern is the way this algorithm resolves the corner case
  59  * where the horizontal ray being cast to count edge crossings may
  60  * cross directly through a vertex. The solution is based on the "idea
  61  * of Simulation of Simplicity" and "pretends to shift the ray
  62  * infinitesimally down so that it either clearly intersects, or
  63  * clearly doesn't touch". I'm not familiar with the idea myself so I
  64  * expect a misplaced epsilon is likely to break that aspect of the
  65  * algorithm.
  66  *
  67  * The simple solution we've gone for is to pixel align the polygon
  68  * vertices which should eradicate most noise due to in-precision.
  69  */
  70 int
  71 _cogl_util_point_in_screen_poly (float point_x,
  72                                  float point_y,
  73                                  void *vertices,
  74                                  size_t stride,
  75                                  int n_vertices)
  76 {
  77   int i, j, c = 0;
  78
  79   for (i = 0, j = n_vertices - 1; i < n_vertices; j = i++)
  80     {
  81       float vert_xi = *(float *)((guint8 *)vertices + i * stride);
  82       float vert_xj = *(float *)((guint8 *)vertices + j * stride);
  83       float vert_yi = *(float *)((guint8 *)vertices + i * stride +
  84                                  sizeof (float));
  85       float vert_yj = *(float *)((guint8 *)vertices + j * stride +
  86                                  sizeof (float));
  87
  88       vert_xi = COGL_UTIL_NEARBYINT (vert_xi);
  89       vert_xj = COGL_UTIL_NEARBYINT (vert_xj);
  90       vert_yi = COGL_UTIL_NEARBYINT (vert_yi);
  91       vert_yj = COGL_UTIL_NEARBYINT (vert_yj);
  92
  93       if (((vert_yi > point_y) != (vert_yj > point_y)) &&
  94            (point_x < (vert_xj - vert_xi) * (point_y - vert_yi) /
  95             (vert_yj - vert_yi) + vert_xi) )
  96          c = !c;
  97     }
  98
  99   return c;
 100 }
 101