1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
/*************************************************************************
* Copyright (c) 2011 AT&T Intellectual Property
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License v1.0
* which accompanies this distribution, and is available at
* https://www.eclipse.org/legal/epl-v10.html
*
* Contributors: Details at https://graphviz.org
*************************************************************************/
#include <neatogen/geometry.h>
#include <math.h>
#include <stddef.h>
double xmin, xmax, ymin, ymax; /* min and max x and y values of sites */
double deltax; // xmax - xmin
size_t nsites;
int sqrt_nsites;
void geominit(void)
{
double sn;
sn = nsites + 4;
sqrt_nsites = (int) sqrt(sn);
}
double dist_2(Point pp, Point qp) {
const double dx = pp.x - qp.x;
const double dy = pp.y - qp.y;
return (dx * dx + dy * dy);
}
void subpt(Point * a, Point b, Point c)
{
a->x = b.x - c.x;
a->y = b.y - c.y;
}
void addpt(Point * c, Point a, Point b)
{
c->x = a.x + b.x;
c->y = a.y + b.y;
}
double area_2(Point a, Point b, Point c)
{
return ((a.y - b.y) * (c.x - b.x) - (c.y - b.y) * (a.x - b.x));
}
int leftOf(Point a, Point b, Point c)
{
return (area_2(a, b, c) > 0);
}
int intersection(Point a, Point b, Point c, Point d, Point * p)
{
double s, t; /* The two parameters of the parametric eqns. */
double denom; /* Denominator of solutions. */
denom =
a.x * (d.y - c.y) +
b.x * (c.y - d.y) + d.x * (b.y - a.y) + c.x * (a.y - b.y);
/* If denom is zero, then the line segments are parallel. */
/* In this case, return false even though the segments might overlap. */
if (denom == 0.0)
return 0;
s = (a.x * (d.y - c.y) + c.x * (a.y - d.y) + d.x * (c.y - a.y)
) / denom;
t = -(a.x * (c.y - b.y) + b.x * (a.y - c.y) + c.x * (b.y - a.y)
) / denom;
p->x = a.x + s * (b.x - a.x);
p->y = a.y + s * (b.y - a.y);
if ((0.0 <= s) && (s <= 1.0) && (0.0 <= t) && (t <= 1.0))
return 1;
else
return 0;
}
|
