1/* $Id$ $Revision$ */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14/*
15 * in_poly
16 *
17 * Test if a point is inside a polygon.
18 * The polygon must be convex with vertices in CW order.
19 */
20
21#include <stdlib.h>
22#include "vispath.h"
23#include "pathutil.h"
24
25#ifdef DMALLOC
26#include "dmalloc.h"
27#endif
28
29int in_poly(Ppoly_t poly, Ppoint_t q)
30{
31 int i, i1; /* point index; i1 = i-1 mod n */
32 int n;
33 Ppoint_t *P;
34
35 P = poly.ps;
36 n = poly.pn;
37 for (i = 0; i < n; i++) {
38 i1 = (i + n - 1) % n;
39 if (wind(P[i1],P[i],q) == 1) return FALSE;
40 }
41 return TRUE;
42}
43