Root/poly2d/poly2d.h

1/*
2 * poly2d.h - The public face of the 2D Polygon library
3 *
4 * Written 2012, 2013, 2015 by Werner Almesberger
5 * Copyright 2012, 2013, 2015 Werner Almesberger
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
11 */
12
13
14#ifndef POLY2D_H
15#define POLY2D_H
16
17#include <stdbool.h>
18#include <stdio.h>
19
20
21struct v2d {
22    double x, y;
23    struct v2d *next; /* may end in NULL or may be cyclic */
24};
25
26
27struct p2d {
28    struct v2d *v; /* vertices */
29    struct v2d *last; /* last vertex or vertex preceding first */
30    struct p2d *next;
31};
32
33struct f2d {
34    double x[3]; /* vertices forming the face */
35    double y[3];
36    bool side[3]; /* side[i] if v[i] and v[(i+1) mod 3] are on polygon */
37    struct f2d *next;
38};
39
40
41/*
42 * forall_v2d* need -std=gnu99
43 */
44
45#define forall_v2d_once(var, first) \
46    for (const struct v2d *__fv2do_0 = (var = (first)); \
47        var; \
48        var = var->next == __fv2do_0 ? NULL : var->next)
49
50#define forall_v2d(var, first) \
51    for (const struct v2d *__fv2d_0 = (var = (first)); \
52        var; \
53        ({ \
54        var = __fv2d_0 ? var->next : NULL; \
55        if (var == __fv2d_0) \
56            __fv2d_0 = NULL; \
57        }))
58
59#define forall_edges(a, b, first) \
60    for (const struct v2d *__fe_0 = \
61       (a = (first), b = a ? a->next : a, a); \
62        a && b; \
63        ({ \
64        a = b; \
65        b = b == __fe_0 ? NULL : b->next; \
66        }))
67
68
69/*
70 * Polygon creation
71 */
72
73struct p2d *p2d_new(void);
74struct v2d *v2d_new(double x, double y);
75void p2d_append(struct p2d *p, struct v2d *v);
76void p2d_prepend(struct p2d *p, struct v2d *v);
77void p2d_close(struct p2d *p);
78
79/*
80 * Intersect line from A0 to A1 with line from B0 to B1.
81 *
82 * Returns:
83 * 0 if the lines are parallel,
84 * 1 if the lines intersect between A0-A1 and B0-B1,
85 * -1 if the lines intersect outside A0-A1 or B0-B1.
86 *
87 * If v2d_intersect returns non-zero, the intersection P is at
88 *
89 * P = A0+(A1-A0)*na = B0+(B1-B0)*nb
90 */
91
92int v2d_intersect(const struct v2d *a0, const struct v2d *a1,
93    const struct v2d *b0, const struct v2d *b1,
94    double *na, double *nb);
95
96/*
97 * Calculate the distance between point P and the line from A to B.
98 * The result is negative if P is on the "right" side of A->B.
99 */
100
101double v2d_line_distance(const struct v2d *a, const struct v2d *b,
102    const struct v2d *p);
103
104/*
105 * Duplicate a polygon
106 */
107
108struct p2d *p2d_copy(const struct p2d *p);
109struct p2d *p2d_copy_all(const struct p2d *p);
110
111/*
112 * Change a polygon from clockwise to counter-clockwise and vice versa.
113 */
114
115struct p2d *p2d_reverse(const struct p2d *p);
116
117/*
118 * p2d_is_cw determine whether a polygon is clockwise.
119 * p2d_is_closed determines whether a polygon is closed.
120 * p2d_no_intersect determines whether a polygon does't self-intersect.
121 * p2d_vertices counts the number of vertices in a polygon.
122 */
123
124bool p2d_is_cw(const struct p2d *p);
125bool p2d_is_closed(const struct p2d *p);
126bool p2d_no_intersect(const struct p2d *p);
127unsigned p2d_vertices(const struct p2d *p);
128
129/*
130 * Convert a possibly self-intersecting polygon into one or more simple
131 * polygons. [1]
132 *
133 * http://en.wikipedia.org/wiki/Simple_polygon
134 */
135
136struct p2d *p2d_simplify(const struct p2d *p);
137
138/*
139 * p2d_free deallocates a single polygon and its vertices.
140 * p2d_free_all deallocates all polygons in a list.
141 */
142
143void p2d_free(struct p2d *p);
144void p2d_free_all(struct p2d *p);
145
146/*
147 * Returns non-zero if the point is inside or on the simple polygon.
148 */
149
150bool p2d_contains_point(const struct p2d *p, const struct v2d *v);
151
152/*
153 * Returns:
154 * 0 if polygon "b" is outside of polygon "a"
155 * 1 if polygon "b" is inside of polygon "a"
156 * -1 if the two polygons intersect
157 */
158
159int p2d_contains_poly(const struct p2d *a, const struct p2d *b);
160
161struct p2d *p2d_offset_holes(const struct p2d *p, const struct p2d *holes,
162    double off);
163struct p2d *p2d_offset(const struct p2d *p, double off);
164
165void p2d_area_holes_append(const struct p2d *p,
166    const struct p2d *holes, double first, double next,
167    struct p2d ***last);
168struct p2d *p2d_area_holes(const struct p2d *p, const struct p2d *holes,
169    double first, double next);
170struct p2d *p2d_area(const struct p2d *p, double first, double next);
171
172void f2d_tri_holes_append(const struct p2d *p, const struct p2d *holes,
173    struct f2d ***last);
174struct f2d *f2d_tri_holes(const struct p2d *p, const struct p2d *holes);
175struct f2d *f2d_tri(const struct p2d *p);
176void f2d_free_all(struct f2d *f);
177
178struct p2d *p2d_read_gnuplot(FILE *file);
179bool p2d_write_gnuplot(FILE *file, const struct p2d *p);
180bool p2d_write_gnuplot_all(FILE *file, const struct p2d *p);
181
182#endif /* !POLY2D_H */
183

Archive Download this file

Branches:
master



interactive