25 #define LENGTH(DX, DY) (sqrt((DX*DX)+(DY*DY))) 28 struct intersection_point
35 struct seg_intersection
42 struct seg_intersection_list
46 struct seg_intersection *a;
49 struct seg_intersections
53 struct intersection_point *ip;
55 struct seg_intersection_list *il;
61 struct seg_intersections *si;
65 si =
G_malloc(
sizeof(
struct seg_intersections));
67 si->ipallocated = segments_count + 16;
68 si->ip =
G_malloc((si->ipallocated) *
sizeof(
struct intersection_point));
69 si->ilcount = segments_count;
70 si->il =
G_malloc(segments_count *
sizeof(
struct seg_intersection_list));
71 for (i = 0; i < segments_count; i++) {
73 si->il[i].allocated = 0;
84 for (i = 0; i < si->ilcount; i++)
94 void add_ipoint1(
struct seg_intersection_list *il,
int with,
double dist,
97 struct seg_intersection *s;
99 if (il->count == il->allocated) {
103 (il->allocated) *
sizeof(
struct seg_intersection));
105 s = &(il->a[il->count]);
116 double x,
double y,
struct seg_intersections *si)
118 struct intersection_point *
t;
124 if (si->ipcount == si->ipallocated) {
125 si->ipallocated += 16;
128 (si->ipallocated) *
sizeof(
struct intersection_point));
138 LENGTH((Points->
x[first_seg] - x),
139 (Points->
y[first_seg] - y)), ip);
142 LENGTH((Points->
x[second_seg] - x),
143 (Points->
y[second_seg] - y)), ip);
149 struct seg_intersection t;
151 G_debug(4,
"sort_intersection_list()");
155 for (i = 0; i < n - 1; i++) {
157 for (j = i + 1; j < n; j++) {
158 if (il->a[j].dist < il->a[min].dist) {
164 il->a[i] = il->a[
min];
174 struct intersection_point *aa, *bb;
176 aa = *((
struct intersection_point **)a);
177 bb = *((
struct intersection_point **)b);
181 else if (aa->x > bb->x)
184 return (aa->y < bb->y) ? -1 : ((aa->y > bb->y) ? 1 : 0);
200 min =
MAX(fabs(x[1] - x[0]), fabs(y[1] - y[0]));
201 for (i = 1; i <= np - 2; i++) {
202 t =
MAX(fabs(x[i + 1] - x[i]), fabs(y[i + 1] - y[i]));
203 if ((t > 0) && (t < min)) {
209 return min * 0.000001;
221 double x1, y1, x2, y2;
226 struct seg_intersections *si;
227 struct seg_intersection_list *il;
228 struct intersection_point **sorted;
230 G_debug(3,
"find_all_intersections()");
238 looped = ((x[0] == x[np - 1]) && (y[0] == y[np - 1]));
239 G_debug(3,
" looped=%d", looped);
241 G_debug(3,
" finding intersections...");
242 for (i = 0; i < np - 1; i++) {
243 for (j = i + 1; j < np - 1; j++) {
244 G_debug(4,
" checking %d-%d %d-%d", i, i + 1, j, j + 1);
248 y[j], x[j + 1], y[j + 1], &x1, &y1,
257 G_debug(4,
" intersection type = %d", res);
261 else if ((res >= 2) && (res <= 5)) {
269 add_ipoint(Points, 0, -1, Points->
x[0], Points->
y[0], si);
270 add_ipoint(Points, np - 2, -1, Points->
x[np - 1], Points->
y[np - 1],
273 G_debug(3,
" finding intersections...done");
275 G_debug(3,
" postprocessing...");
276 if (si->ipallocated > si->ipcount) {
277 si->ipallocated = si->ipcount;
280 (si->ipcount) *
sizeof(
struct intersection_point));
282 for (i = 0; i < si->ilcount; i++) {
284 if (il->allocated > il->count) {
285 il->allocated = il->count;
288 (il->count) *
sizeof(
struct seg_intersection));
298 sorted =
G_malloc((si->ipcount) *
sizeof(
struct intersection_point *));
299 for (i = 0; i < si->ipcount; i++)
300 sorted[i] = &(si->ip[i]);
302 qsort(sorted, si->ipcount,
sizeof(
struct intersection_point *),
compare);
306 for (i = 0; i < si->ipcount; i++) {
309 for (j = i - 1; j >= 0; j--) {
310 if (!
FEQUAL(sorted[j]->x, sorted[i]->x, EPSILON))
313 if (
FEQUAL(sorted[j]->y, sorted[i]->y, EPSILON)) {
315 t = sorted[j]->group;
319 G_debug(4,
" group=%d, ip=%d", t,
320 (
int)(sorted[i] - &(si->ip[0])));
321 sorted[i]->group =
t;
325 si->group_count = group;
327 G_debug(3,
" postprocessing...done");
330 for (i = 0; i < si->ilcount; i++) {
331 G_debug(4,
"%d-%d :", i, i + 1);
332 for (j = 0; j < si->il[i].count; j++) {
333 G_debug(4,
" %d-%d, group=%d", si->il[i].a[j].with,
334 si->il[i].a[j].with + 1, si->ip[si->il[i].a[j].ip].group);
335 G_debug(4,
" dist=%.18f", si->il[i].a[j].dist);
336 G_debug(4,
" x=%.18f, y=%.18f",
337 si->ip[si->il[i].a[j].ip].x, si->ip[si->il[i].a[j].ip].y);
354 memset(pg->
v, 0, n *
sizeof(
struct pg_vertex));
367 for (i = 0; i < pg->
vcount; i++) {
389 for (i = 0; i < ecount; i++) {
391 if (((e->
v1 == v1) && (e->
v2 ==
v2)) ||
392 ((e->
v1 ==
v2) && (e->
v2 == v1)))
415 G_debug(4,
"pg_addedge(), v1=%d, v2=%d", v1, v2);
417 if ((v1 == v2) || (v1 < 0) || (v1 >= pg->
vcount) || (v2 < 0) ||
428 "than the initial allocation size allows"));
446 struct seg_intersections *si;
448 struct intersection_point *ip;
460 for (i = 0; i < si->ipcount; i++) {
468 for (i = 0; i < si->ilcount; i++) {
469 v = si->ip[si->il[i].a[0].ip].group;
470 for (j = 1; j < si->il[i].count; j++) {
471 t = si->ip[si->il[i].a[j].ip].group;
480 for (i = 0; i < pg->
vcount; i++) {
483 for (j = 0; j < vert->
ecount; j++) {
484 edge = vert->
edges[j];
485 t = (edge->
v1 != i) ? (edge->
v1) : (edge->
v2);
487 atan2(pg->
v[t].
y - vert->
y, pg->
v[t].
x - vert->
x);
512 for (i = 0; i < pg->
vcount; i++) {
513 G_debug(4,
" vertex %d (%g, %g)", i, pg->
v[i].
x, pg->
v[i].
y);
514 for (j = 0; j < pg->
v[i].
ecount; j++) {
void pg_addedge(struct planar_graph *pg, int v1, int v2)
void void void void G_fatal_error(const char *,...) __attribute__((format(printf
void sort_intersection_list(struct seg_intersection_list *il)
void pg_destroy_struct(struct planar_graph *pg)
void add_ipoint(const struct line_pnts *Points, int first_seg, int second_seg, double x, double y, struct seg_intersections *si)
void pg_addedge1(struct pg_vertex *v, struct pg_edge *e)
int n_points
Number of points.
#define FEQUAL(X, Y, TOL)
struct planar_graph * pg_create_struct(int n, int e)
void G_free(void *)
Free allocated memory.
int pg_existsedge(struct planar_graph *pg, int v1, int v2)
double * x
Array of X coordinates.
Feature geometry info - coordinates.
struct planar_graph * pg_create(const struct line_pnts *Points)
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)
double * y
Array of Y coordinates.
int compare(const void *a, const void *b)
struct seg_intersections * create_si_struct(int segments_count)
void destroy_si_struct(struct seg_intersections *si)
double get_epsilon(struct line_pnts *Points)
struct seg_intersections * find_all_intersections(const struct line_pnts *Points)
void add_ipoint1(struct seg_intersection_list *il, int with, double dist, int ip)
int G_debug(int, const char *,...) __attribute__((format(printf