geometry.c

Go to the documentation of this file.

/*************************************************************************
 * 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 "config.h"
 
#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;
}