FreeWRL / FreeX3D 4.3.0
point_in_poly.c
1// http://geomalgorithms.com/a03-_inclusion.html
2// hacked to C, pointer references, and double coords by dug9, freewrl
3typedef struct Point {
4 double x;
5 double y;
6} Point;
7
8// Copyright 2000 softSurfer, 2012 Dan Sunday
9// This code may be freely used and modified for any purpose
10// providing that this copyright notice is included with it.
11// SoftSurfer makes no warranty for this code, and cannot be held
12// liable for any real or imagined damage resulting from its use.
13// Users of this code must verify correctness for their application.
14
15
16// a Point is defined by its coordinates {int x, y;}
17//===================================================================
18
19
20// isLeft(): tests if a point is Left|On|Right of an infinite line.
21// Input: three points P0, P1, and P2
22// Return: >0 for P2 left of the line through P0 and P1
23// =0 for P2 on the line
24// <0 for P2 right of the line
25// See: Algorithm 1 "Area of Triangles and Polygons"
26
27int isLeft( Point *P0, Point *P1, Point *P2 )
28{
29 double ans = ( (P1->x - P0->x) * (P2->y - P0->y)
30 - (P2->x - P0->x) * (P1->y - P0->y) );
31 return ans == 0.0 ? 0 : ans > 0.0 ? 1 : -1;
32}
33//===================================================================
34
35
36// cn_PnPoly(): crossing number test for a point in a polygon
37// Input: P = a point,
38// V[] = vertex points of a polygon V[n+1] with V[n]=V[0]
39// Return: 0 = outside, 1 = inside
40// This code is patterned after [Franklin, 2000]
41int cn_PnPoly( Point P, Point *V, int n )
42{
43 int cn = 0; // the crossing number counter
44
45 // loop through all edges of the polygon
46 for (int i=0; i<n; i++) { // edge from V[i] to V[i+1]
47 if (((V[i].y <= P.y) && (V[i+1].y > P.y)) // an upward crossing
48 || ((V[i].y > P.y) && (V[i+1].y <= P.y))) { // a downward crossing
49 // compute the actual edge-ray intersect x-coordinate
50 double vt = (float)(P.y - V[i].y) / (V[i+1].y - V[i].y);
51 if (P.x < V[i].x + vt * (V[i+1].x - V[i].x)) // P.x < intersect
52 ++cn; // a valid crossing of y=P.y right of P.x
53 }
54 }
55 return (cn & 1); // 0 if even (out), and 1 if odd (in)
56
57}
58//===================================================================
59
60
61// wn_PnPoly(): winding number test for a point in a polygon
62// Input: P = a point,
63// V[] = vertex points of a polygon V[n+1] with V[n]=V[0]
64// Return: wn = the winding number (=0 only when P is outside)
65int wn_PnPoly( Point *P, Point **V, int n )
66{
67 int wn = 0; // the winding number counter
68
69 // loop through all edges of the polygon
70 for (int i=0; i<n; i++) { // edge from V[i] to V[i+1]
71 if (V[i]->y <= P->y) { // start y <= P.y
72 if (V[i+1]->y > P->y) // an upward crossing
73 if (isLeft( V[i], V[i+1], P) > 0) // P left of edge
74 ++wn; // have a valid up intersect
75 }
76 else { // start y > P.y (no test needed)
77 if (V[i+1]->y <= P->y) // a downward crossing
78 if (isLeft( V[i], V[i+1], P) < 0) // P right of edge
79 --wn; // have a valid down intersect
80 }
81 }
82 return wn;
83}
84//===================================================================
Definition DIS.h:642
float x
x
Definition DIS.h:644
float y
y
Definition DIS.h:646