lint.c

//
//  lint.c
//  Algorithms - Two line segments intersect
//
//  Created by YourtionGuo on 25/05/2017.
//  Copyright © 2017 Yourtion. All rights reserved.
//

#include "geometry.h"

#pragma mark - Public


int lint(Point p1, Point p2, Point p3, Point p4)
{
  double    z1, z2, z3, z4;
  int       s1, s2, s3, s4;

  /// 执行快速剔除检测
  if (!(MAX(p1.x, p2.x) >= MIN(p3.x, p4.x)
        && MAX(p3.x, p4.x) >= MIN(p1.x, p2.x)
        && MAX(p1.y, p2.y) >= MIN(p3.y, p4.y)
        && MAX(p3.y, p4.y) >= MIN(p1.y, p2.y))) {

    return 0;
  }

  /*****************************************************************************
   *                                                                            *
   *  Determine whether the line segments straddle each other.                  *
   *                                                                            *
   *****************************************************************************/

  if ((z1 = ((p3.x - p1.x)*(p2.y - p1.y)) - ((p3.y - p1.y)*(p2.x - p1.x))) < 0) {
    s1 = -1;
  } else if (z1 > 0) {
    s1 = 1;
  } else {
    s1 = 0;
  }

  if ((z2 = ((p4.x - p1.x)*(p2.y - p1.y)) - ((p4.y - p1.y)*(p2.x - p1.x))) < 0) {
    s2 = -1;
  } else if (z2 > 0) {
    s2 = 1;
  } else {
    s2 = 0;
  }

  if ((z3 = ((p1.x - p3.x)*(p4.y - p3.y)) - ((p1.y - p3.y)*(p4.x - p3.x))) < 0) {
    s3 = -1;
  } else if (z3 > 0) {
    s3 = 1;
  } else {
    s3 = 0;
  }

  if ((z4 = ((p2.x - p3.x)*(p4.y - p3.y)) - ((p2.y - p3.y)*(p4.x - p3.x))) < 0) {
    s4 = -1;
  } else if (z4 > 0) {
    s4 = 1;
  } else {
    s4 = 0;
  }

  if ((s1 * s2 <= 0) && (s3 * s4 <= 0)) return 1;

  /// 如果线段没有相交返回 0
  return 0;
}