Graphviz 14.0.0~dev.20250918.1035
Loading...
Searching...
No Matches
intersect.c
Go to the documentation of this file.
1/*************************************************************************
2 * Copyright (c) 2011 AT&T Intellectual Property
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * https://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors: Details at https://graphviz.org
9 *************************************************************************/
10
11#include <math.h>
12#include "simple.h"
13#include <stdlib.h>
14#include <util/unreachable.h>
15
16static int sign(double v) {
17 if (v < 0)
18 return -1;
19 if (v > 0)
20 return 1;
21 return 0;
22}
23
24/* find the sign of the area of each of the triangles
25 formed by adding a vertex of m to l
26 also find the sign of their product */
27static void sgnarea(struct vertex *l, struct vertex *m, int i[])
28{
29 const double a = l->pos.x;
30 const double b = l->pos.y;
31 const double c = after(l)->pos.x - a;
32 const double d = after(l)->pos.y - b;
33 const double e = m->pos.x - a;
34 const double f = m->pos.y - b;
35 const double g = after(m)->pos.x - a;
36 const double h = after(m)->pos.y - b;
37 double t = c * f - d * e;
38 i[0] = sign(t);
39 t = c * h - d * g;
40 i[1] = sign(t);
41 i[2] = i[0] * i[1];
42}
43
56static int between(double f, double g, double h) {
57 if (f < g) {
58 if (g < h) {
59 return 1;
60 }
61 if (g > h) {
62 return -1;
63 }
64 return 0;
65 }
66 if (f > g) {
67 if (g > h) {
68 return 1;
69 }
70 if (g < h) {
71 return -1;
72 }
73 return 0;
74 }
75 return 0;
76}
77
78/* determine if vertex i of line m is on line l */
79static int online(struct vertex *l, struct vertex *m, int i)
80{
81 struct position a, b, c;
82 a = l->pos;
83 b = after(l)->pos;
84 c = i == 0 ? m->pos : after(m)->pos;
85 return a.x == b.x ? (a.x == c.x && -1 != between(a.y, c.y, b.y))
86 : between(a.x, c.x, b.x);
87}
88
89/* determine point of detected intersections */
90static int intpoint(struct vertex *l, struct vertex *m, double *x, double *y,
91 int cond) {
92 struct position ls, le, ms, me, pt1, pt2;
93
94 if (cond <= 0)
95 return (0);
96 ls = l->pos;
97 le = after(l)->pos;
98 ms = m->pos;
99 me = after(m)->pos;
100
101 switch (cond) {
102
103 case 3: /* a simple intersection */
104 if (ls.x == le.x) {
105 *x = ls.x;
106 *y = me.y + SLOPE(ms, me) * (*x - me.x);
107 } else if (ms.x == me.x) {
108 *x = ms.x;
109 *y = le.y + SLOPE(ls, le) * (*x - le.x);
110 } else {
111 const double m1 = SLOPE(ms, me);
112 const double m2 = SLOPE(ls, le);
113 const double c1 = ms.y - m1 * ms.x;
114 const double c2 = ls.y - m2 * ls.x;
115 *x = (c2 - c1) / (m1 - m2);
116 *y = (m1 * c2 - c1 * m2) / (m1 - m2);
117 }
118 break;
119
120 case 2: /* the two lines have a common segment */
121 if (online(l, m, 0) == -1) { /* ms between ls and le */
122 pt1 = ms;
123 pt2 = online(m, l, 1) == -1 ? (online(m, l, 0 == -1) ? le : ls) : me;
124 } else if (online(l, m, 1) == -1) { /* me between ls and le */
125 pt1 = me;
126 pt2 = online(l, m, 0) == -1 ? (online(m, l, 0) == -1 ? le : ls) : ms;
127 } else {
128 /* may be degenerate? */
129 if (online(m, l, 0) != -1)
130 return 0;
131 pt1 = ls;
132 pt2 = le;
133 }
134
135 *x = (pt1.x + pt2.x) / 2;
136 *y = (pt1.y + pt2.y) / 2;
137 break;
138
139 case 1: /* a vertex of line m is on line l */
140 if ((ls.x - le.x) * (ms.y - ls.y) == (ls.y - le.y) * (ms.x - ls.x)) {
141 *x = ms.x;
142 *y = ms.y;
143 } else {
144 *x = me.x;
145 *y = me.y;
146 }
147 break;
148
149 default:
150 UNREACHABLE();
151 } /* end switch */
152 return 1;
153}
154
155void find_intersection(struct vertex *l, struct vertex *m,
156 intersections_t *ilist) {
157 double x, y;
158 int i[3];
159 sgnarea(l, m, i);
160
161 if (i[2] > 0)
162 return;
163
164 if (i[2] < 0) {
165 sgnarea(m, l, i);
166 if (i[2] > 0)
167 return;
168 if (!intpoint(l, m, &x, &y, i[2] < 0 ? 3 : online(m, l, abs(i[0]))))
169 return;
170 }
171
172 else if (!intpoint(l, m, &x, &y, i[0] == i[1] ? 2 * MAX(online(l, m, 0),
173 online(l, m, 1)) : online(l, m, abs(i[0]))))
174 return;
175
176 struct intersection inter = {
177 .firstv = l,
178 .secondv = m,
179 .firstp = l->poly,
180 .secondp = m->poly,
181 .x = x,
182 .y = y
183 };
184 LIST_APPEND(ilist, inter);
185}
#define le
Definition edges.h:31
static int between(double f, double g, double h)
Definition intersect.c:56
static void sgnarea(struct vertex *l, struct vertex *m, int i[])
Definition intersect.c:27
static int online(struct vertex *l, struct vertex *m, int i)
Definition intersect.c:79
void find_intersection(struct vertex *l, struct vertex *m, intersections_t *ilist)
detect whether lines l and m intersect
Definition intersect.c:155
static int sign(double v)
Definition intersect.c:16
static int intpoint(struct vertex *l, struct vertex *m, double *x, double *y, int cond)
Definition intersect.c:90
#define after(v)
Definition legal.c:26
#define SLOPE(p, q)
Definition legal.c:22
#define LIST_APPEND(list, item)
Definition list.h:132
struct vertex * firstv
Definition simple.h:36
double y
Definition simple.h:38
double x
Definition simple.h:38
double x
Definition geom.h:29
double y
Definition geom.h:29
double x
Definition simple.h:21
double y
Definition simple.h:21
Definition legal.c:32
pointf pos
Definition legal.c:33
polygon * poly
Definition legal.c:34
#define UNREACHABLE()
Definition unreachable.h:30
#define MAX(a, b)
Definition write.c:32