intersect.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 <math.h>
#include "simple.h"
#include <stdlib.h>
#include <util/unreachable.h>
 
static int sign(double v) {
  if (v < 0)
    return -1;
  if (v > 0)
    return 1;
  return 0;
}
 
/* find the sign of the area of each of the triangles
  formed by adding a vertex of m to l 
  also find the sign of their product  */
static void sgnarea(struct vertex *l, struct vertex *m, int i[])
{
    const double a = l->pos.x;
    const double b = l->pos.y;
    const double c = after(l)->pos.x - a;
    const double d = after(l)->pos.y - b;
    const double e = m->pos.x - a;
    const double f = m->pos.y - b;
    const double g = after(m)->pos.x - a;
    const double h = after(m)->pos.y - b;
    double t = c * f - d * e;
    i[0] = sign(t);
    t = c * h - d * g;
    i[1] = sign(t);
    i[2] = i[0] * i[1];
}
 
static int between(double f, double g, double h) {
  if (f < g) {
    if (g < h) {
      return 1;
    }
    if (g > h) {
      return -1;
    }
    return 0;
  }
  if (f > g) {
    if (g > h) {
      return 1;
    }
    if (g < h) {
      return -1;
    }
    return 0;
  }
  return 0;
}
 
/* determine if vertex i of line m is on line l     */
static int online(struct vertex *l, struct vertex *m, int i)
{
    struct position a, b, c;
    a = l->pos;
    b = after(l)->pos;
    c = i == 0 ? m->pos : after(m)->pos;
    return a.x == b.x ? (a.x == c.x && -1 != between(a.y, c.y, b.y))
                      : between(a.x, c.x, b.x);
}
 
/* determine point of detected intersections  */
static int intpoint(struct vertex *l, struct vertex *m, double *x, double *y,
                    int cond) {
    struct position ls, le, ms, me, pt1, pt2;
 
    if (cond <= 0)
        return (0);
    ls = l->pos;
    le = after(l)->pos;
    ms = m->pos;
    me = after(m)->pos;
 
    switch (cond) {
 
    case 3:                     /* a simple intersection        */
        if (ls.x == le.x) {
            *x = ls.x;
            *y = me.y + SLOPE(ms, me) * (*x - me.x);
        } else if (ms.x == me.x) {
            *x = ms.x;
            *y = le.y + SLOPE(ls, le) * (*x - le.x);
        } else {
            const double m1 = SLOPE(ms, me);
            const double m2 = SLOPE(ls, le);
            const double c1 = ms.y - m1 * ms.x;
            const double c2 = ls.y - m2 * ls.x;
            *x = (c2 - c1) / (m1 - m2);
            *y = (m1 * c2 - c1 * m2) / (m1 - m2);
        }
        break;
 
    case 2:                     /*     the two lines  have a common segment  */
        if (online(l, m, 0) == -1) {    /* ms between ls and le */
            pt1 = ms;
            pt2 = online(m, l, 1) == -1 ? (online(m, l, 0 == -1) ? le : ls) : me;
        } else if (online(l, m, 1) == -1) {     /* me between ls and le */
            pt1 = me;
            pt2 = online(l, m, 0) == -1 ? (online(m, l, 0) == -1 ? le : ls) : ms;
        } else {
            /* may be degenerate? */
            if (online(m, l, 0) != -1)
                return 0;
            pt1 = ls;
            pt2 = le;
        }
 
        *x = (pt1.x + pt2.x) / 2;
        *y = (pt1.y + pt2.y) / 2;
        break;
 
    case 1:                     /* a vertex of line m is on line l */
        if ((ls.x - le.x) * (ms.y - ls.y) == (ls.y - le.y) * (ms.x - ls.x)) {
            *x = ms.x;
            *y = ms.y;
        } else {
            *x = me.x;
            *y = me.y;
        }
        break;
 
    default:
        UNREACHABLE();
    }                           /* end switch  */
    return 1;
}
 
void find_intersection(struct vertex *l, struct vertex *m,
                       intersections_t *ilist) {
    double x, y;
    int i[3];
    sgnarea(l, m, i);
 
    if (i[2] > 0)
        return;
 
    if (i[2] < 0) {
        sgnarea(m, l, i);
        if (i[2] > 0)
            return;
        if (!intpoint(l, m, &x, &y, i[2] < 0 ? 3 : online(m, l, abs(i[0]))))
            return;
    }
 
    else if (!intpoint(l, m, &x, &y, i[0] == i[1] ? 2 * MAX(online(l, m, 0),
                               online(l, m, 1)) : online(l, m, abs(i[0]))))
        return;
 
    struct intersection inter = {
      .firstv = l,
      .secondv = m,
      .firstp = l->poly,
      .secondp = m->poly,
      .x = x,
      .y = y
    };
    LIST_APPEND(ilist, inter);
}