4 #include <grass/Vect.h>
9 #define LENGTH(DX, DY) (sqrt((DX*DX)+(DY*DY)))
11 #define MIN(X,Y) ((X<Y)?X:Y)
14 #define MAX(X,Y) ((X>Y)?X:Y)
61 for (i = 0; i < segments_count; i++) {
74 for (i = 0; i < si->
ilcount; i++)
105 void add_ipoint(
struct line_pnts *Points,
int first_seg,
int second_seg,
128 LENGTH((Points->x[first_seg] - x),
129 (Points->y[first_seg] - y)), ip);
132 LENGTH((Points->x[second_seg] - x),
133 (Points->y[second_seg] - y)), ip);
142 G_debug(4,
"sort_intersection_list()");
146 for (i = 0; i < n - 1; i++) {
148 for (j = i + 1; j <
n; j++) {
155 il->
a[i] = il->
a[
min];
163 static int compare(
const void *a,
const void *
b)
172 else if (aa->
x > bb->
x)
175 return (aa->
y < bb->
y) ? -1 : ((aa->
y > bb->
y) ? 1 : 0);
187 np = Points->n_points;
191 min =
MAX(fabs(x[1] - x[0]), fabs(y[1] - y[0]));
192 for (i = 1; i <= np - 2; i++) {
193 t =
MAX(fabs(x[i + 1] - x[i]), fabs(y[i + 1] - y[i]));
194 if ((t > 0) && (t < min)) {
200 return min * 0.000001;
216 double x1, y1, x2, y2;
228 G_debug(3,
"find_all_intersections()");
230 np = Points->n_points;
236 looped = ((x[0] == x[np - 1]) && (y[0] == y[np - 1]));
237 G_debug(3,
" looped=%d", looped);
239 G_debug(3,
" finding intersections...");
240 for (i = 0; i < np - 1; i++) {
241 for (j = i + 1; j < np - 1; j++) {
242 G_debug(4,
" checking %d-%d %d-%d", i, i + 1, j, j + 1);
246 y[j], x[j + 1], y[j + 1], &x1, &y1,
254 G_debug(4,
" intersection type = %d", res);
258 else if ((res >= 2) && (res <= 5)) {
266 add_ipoint(Points, 0, -1, Points->x[0], Points->y[0], si);
267 add_ipoint(Points, np - 2, -1, Points->x[np - 1], Points->y[np - 1],
270 G_debug(3,
" finding intersections...done");
272 G_debug(3,
" postprocessing...");
279 for (i = 0; i < si->
ilcount; i++) {
296 for (i = 0; i < si->
ipcount; i++)
297 sorted[i] = &(si->
ip[i]);
303 for (i = 0; i < si->
ipcount; i++) {
306 for (j = i - 1; j >= 0; j--) {
307 if (!
FEQUAL(sorted[j]->x, sorted[i]->x, EPSILON))
310 if (
FEQUAL(sorted[j]->y, sorted[i]->y, EPSILON)) {
312 t = sorted[j]->
group;
316 G_debug(4,
" group=%d, ip=%d", t,
317 (
int)(sorted[i] - &(si->
ip[0])));
318 sorted[i]->
group = t;
324 G_debug(3,
" postprocessing...done");
327 for (i = 0; i < si->
ilcount; i++) {
328 G_debug(4,
"%d-%d :", i, i + 1);
329 for (j = 0; j < si->
il[i].
count; j++) {
333 G_debug(4,
" x=%.18f, y=%.18f",
349 pg->
v = G_malloc(n *
sizeof(
struct pg_vertex));
350 memset(pg->
v, 0, n *
sizeof(
struct pg_vertex));
354 pg->
e = G_malloc(e *
sizeof(
struct pg_edge));
363 for (i = 0; i < pg->
vcount; i++) {
387 for (i = 0; i < ecount; i++) {
389 if (((e->
v1 == v1) && (e->
v2 ==
v2)) ||
390 ((e->
v1 ==
v2) && (e->
v2 == v1)))
413 G_debug(4,
"pg_addedge(), v1=%d, v2=%d", v1, v2);
415 if ((v1 == v2) || (v1 < 0) || (v1 >= pg->
vcount) || (v2 < 0) ||
426 (
"Trying to add more edges to the planar_graph than the initial allocation size allows");
462 for (i = 0; i < si->
ipcount; i++) {
470 for (i = 0; i < si->
ilcount; i++) {
472 for (j = 1; j < si->
il[i].
count; j++) {
482 for (i = 0; i < pg->
vcount; i++) {
484 vert->
angles = G_malloc((vert->
ecount) *
sizeof(
double));
485 for (j = 0; j < vert->
ecount; j++) {
486 edge = vert->
edges[j];
487 t = (edge->
v1 != i) ? (edge->
v1) : (edge->
v2);
489 atan2(pg->
v[t].
y - vert->
y, pg->
v[t].
x - vert->
x);
514 for (i = 0; i < pg->
vcount; i++) {
515 G_debug(4,
" vertex %d (%g, %g)", i, pg->
v[i].
x, pg->
v[i].
y);
516 for (j = 0; j < pg->
v[i].
ecount; j++) {
struct planar_graph * pg_create(struct line_pnts *Points)
void pg_addedge(struct planar_graph *pg, int v1, int v2)
void sort_intersection_list(struct seg_intersection_list *il)
void G_free(void *buf)
Free allocated memory.
void pg_destroy_struct(struct planar_graph *pg)
void pg_addedge1(struct pg_vertex *v, struct pg_edge *e)
struct intersection_point * ip
struct seg_intersection_list * il
#define FEQUAL(X, Y, TOL)
struct seg_intersection * a
struct planar_graph * pg_create_struct(int n, int e)
void add_ipoint(struct line_pnts *Points, int first_seg, int second_seg, double x, double y, struct seg_intersections *si)
int pg_existsedge(struct planar_graph *pg, int v1, int v2)
int segment_intersection_2d(double ax1, double ay1, double ax2, double ay2, double bx1, double by1, double bx2, double by2, double *x1, double *y1, double *x2, double *y2)
struct seg_intersections * find_all_intersections(struct line_pnts *Points)
int G_debug(int level, const char *msg,...)
Print debugging message.
struct seg_intersections * create_si_struct(int segments_count)
void destroy_si_struct(struct seg_intersections *si)
double get_epsilon(struct line_pnts *Points)
int G_fatal_error(const char *msg,...)
Print a fatal error message to stderr.
void add_ipoint1(struct seg_intersection_list *il, int with, double dist, int ip)