Calculate the intersection of two lines.

@param lineA a line
@param lineB another line
@return the point where the two lines intersect (or null)
514074
public static Point2D lineLineIntersect(final Line2D lineA, final Line2D lineB) {
        return lineLineIntersect(lineA.getX1(), lineA.getY1(), lineA.getX2(), lineA.getY2(), lineB.getX1(),
                lineB.getY1(), lineB.getX2(), lineB.getY2());

    }
1118152
public static Double azimuth(Geometry pointA, Geometry pointB){
        if(pointA == null||pointB == null){
            return null;
        }
        if ((pointA instanceof Point) && (pointB instanceof Point)) {
            Double angle ;
            double x0 = ((Point) pointA).getX();
            double y0 = ((Point) pointA).getY();
            double x1 = ((Point) pointB).getX();
            double y1 = ((Point) pointB).getY();

            if (x0 == x1) {
                if (y0 < y1) {
                    angle = 0.0;
                } else if (y0 > y1) {
                    angle = Math.PI;
                } else {
                    angle = null;
                }
            } else

            if (y0 == y1) {
                if (x0 < x1) {
                    angle = Math.PI / 2;
                } else if (x0 > x1) {
                    angle = Math.PI + (Math.PI / 2);
                } else {
                    angle = null;
                }
            } else

            if (x0 < x1) {
                if (y0 < y1) {
                    angle = Math.atan(Math.abs(x0 - x1) / Math.abs(y0 - y1));
                } else { /* ( y0 > y1 ) - equality case handled above */
                    angle = Math.atan(Math.abs(y0 - y1) / Math.abs(x0 - x1)) + (Math.PI / 2);
                }
            }

            else { /* ( x0 > x1 ) - equality case handled above */
                if (y0 > y1) {
                    angle = Math.atan(Math.abs(x0 - x1) / Math.abs(y0 - y1)) + Math.PI;
                } else { /* ( y0 < y1 ) - equality case handled above */
                    angle = Math.atan(Math.abs(y0 - y1) / Math.abs(x0 - x1)) + (Math.PI + (Math.PI / 2));
                }
            }
            return angle;
        }
        return null;
    }
83334
public CompactSketch intersect(final Sketch a, final Sketch b) {
    return intersect(a, b, true, null);
  }
190869
public void process(PairLineNorm line, AssociatedPair point) {

		// t0 = (F*x) cross l'
		GeometryMath_F64.mult(F,point.p1,Fx);
		GeometryMath_F64.cross(Fx,line.getL2(),t0);
		// t1 = x' cross ((f*x) cross l')
		GeometryMath_F64.cross(point.p2, t0, t1);
		// t0 = x' cross e'
		GeometryMath_F64.cross(point.p2,e2,t0);

		double top = GeometryMath_F64.dot(t0,t1);
		double bottom = t0.normSq()*(line.l1.x*point.p1.x + line.l1.y*point.p1.y + line.l1.z);

		// e' * l^T
		GeometryMath_F64.outerProd(e2, line.l1, el);
		// cross(l')*F
		GeometryMath_F64.multCrossA(line.l2, F, lf);

		CommonOps_DDRM.add(lf,top/bottom,el,H);

		// pick a good scale and sign for H
		adjust.adjust(H, point);
	}
781898
public Vertex get(int line, int length)
    {
        for (Vertex vertex : vertexes[line])
        {
            if (vertex.realWord.length() == length)
            {
                return vertex;
            }
        }

        return null;
    }
1175763
public boolean intersects(Geometry geometry) {
		if (geometry == null || isEmpty() || geometry.isEmpty()) {
			return false;
		}

		if (geometry.getNumGeometries() > 1) {
			for (int n = 0; n < geometry.getNumGeometries(); n++) {
				if (intersects(geometry.getGeometryN(n))) {
					return true;
				}
			}
		} else {
			final Coordinate[] coords = geometry.getCoordinates();
			if (coords.length > 1 && coordinates.length > 1) {
				for (int i = 0; i < coordinates.length - 1; i++) {
					for (int j = 0; j < coords.length - 1; j++) {
						if (Mathlib.lineIntersects(coordinates[i], coordinates[i + 1], coords[j], coords[j + 1])) {
							return true;
						}
					}
					if (Mathlib.touches(geometry, coordinates[i])) {
						return true;
					}
				}
			} else {
				// TODO implement me
			}
		}

		return false;
	}
672119
private static boolean polylineContainsPoint_(Polyline polyline_a,
			Point point_b, double tolerance, ProgressTracker progress_tracker) {
		// Quick rasterize test to see whether the the geometries are disjoint.
		if (tryRasterizedContainsOrDisjoint_(polyline_a, point_b, tolerance,
				false) == Relation.disjoint)
			return false;

		Point2D pt_b = point_b.getXY();
		return linearPathContainsPoint_(polyline_a, pt_b, tolerance);
	}
960463
public static function intersection(
        ImagickRendererLine $l1,
        ImagickRendererLine $l2
    ) {
        $rs = $l1->rx * $l2->ry - $l1->ry * $l2->rx;

        if ($rs == 0) {
            return null;
        }
        
        $u = (($l2->Px - $l1->Px) * $l1->ry - ($l2->Py - $l1->Py) * $l1->rx) / $rs;

        return new Point(
            $l2->Px + $u * $l2->rx,
            $l2->Py + $u * $l2->ry
        );
    }
125772
public final Bounds intersect(Bounds b) {
		final long _min = Math.max(this.min, b.min);
		final long _max = Math.min(this.max, b.max);
		if(_min <= _max) return new Bounds(_min, _max);
		return null;
	}
995807
public boolean intersects(LineSegment lineSegment) {
		double x1 = this.x1();
		double y1 = this.y1();
		double x2 = this.x2();
		double y2 = this.y2();
		double x3 = lineSegment.x1();
		double y3 = lineSegment.y1();
		double x4 = lineSegment.x2();
		double y4 = lineSegment.y2();

		double denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
		if (denom == 0) {
			return false;
		}
		double u1 = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denom;
		double u2 = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denom;
		return (u1 > 0 && u1 < 1 && u2 > 0 && u2 < 1);
	}
339923
public boolean intersects(Geometry geometry) {
		if (geometry == null) {
			return false;
		}
		Coordinate[] arr1 = getCoordinates();
		Coordinate[] arr2 = geometry.getCoordinates();
		for (int i = 0; i < arr1.length - 1; i++) {
			for (int j = 0; j < arr2.length - 1; j++) {
				if (Mathlib.lineIntersects(arr1[i], arr1[i + 1], arr2[j], arr2[j + 1])) {
					return true;
				}
			}
		}
		return false;
	}
1169254
def intersect (self, line):
     
     eps   = 1e-8
     d     = (line.q - line.p)
     dn    = d.dot(self.n)
     point = None

     if abs(dn) >= eps:
       mu = self.n.dot(self.p - line.p) / dn
       if mu >= 0 and mu <= 1:
         point = line.p + mu * d

     return point
1354032
def split(line, lines):
    
    out = empty((len(lines) + 1, 4))

    p1 = line[:2]
    for n, l2 in enumerate(lines):
        p2 = intersection(line, l2)
        out[n][:2] = p1
        out[n][2:] = p2
        p1 = p2
    out[n + 1][:2] = p2
    out[n + 1][2:] = line[2:]
    return out
649149
static Edge selectClosest( NodeInfo a , NodeInfo b , boolean checkSide ) {

		double bestScore = Double.MAX_VALUE;
		Edge bestEdgeA = null;

		Edge edgeAB = a.findEdge(b);
		double distAB = a.distance(b);

		if( edgeAB == null ) {
			return null;// TODO BUG! FIX!
		}

		for (int i = 0; i < a.edges.size; i++) {
			Edge edgeA = a.edges.get(i);
			NodeInfo aa = a.edges.get(i).target;
			if( aa.marked ) continue;

			for (int j = 0; j < b.edges.size; j++) {
				Edge edgeB = b.edges.get(j);
				NodeInfo bb = b.edges.get(j).target;
				if( bb.marked ) continue;

				if( aa == bb ) {
//					System.out.println("center "+aa.ellipse.center);
					if( checkSide && UtilAngle.distanceCW(edgeAB.angle,edgeA.angle) > Math.PI*0.75 )
						continue;

					double angle = UtilAngle.dist(edgeA.angle,edgeB.angle);

					if( angle < 0.3 )
						continue;

					double da = EllipsesIntoClusters.axisAdjustedDistanceSq(a.ellipse,aa.ellipse);
					double db = EllipsesIntoClusters.axisAdjustedDistanceSq(b.ellipse,aa.ellipse);

					da = Math.sqrt(da);
					db = Math.sqrt(db);

					// see if they are approximately the same distance
					double diffRatio = Math.abs(da-db)/Math.max(da,db);
					if( diffRatio > 0.3 )
						continue;

					// TODO reject if too far
					double d = (da+db)/distAB + 0.1*angle;

					if( d < bestScore ) {
						bestScore = d;
						bestEdgeA = a.edges.get(i);
					}
					break;
				}
			}
		}

		return bestEdgeA;
	}
515614
public boolean intersects(Shape shape) {
        /*
         * Intersection formula used:
         *      (x4 - x3)(y1 - y3) - (y4 - y3)(x1 - x3)
         * UA = ---------------------------------------
         *      (y4 - y3)(x2 - x1) - (x4 - x3)(y2 - y1)
         *      
         *      (x2 - x1)(y1 - y3) - (y2 - y1)(x1 - x3)
         * UB = ---------------------------------------
         *      (y4 - y3)(x2 - x1) - (x4 - x3)(y2 - y1)
         *      
         * if UA and UB are both between 0 and 1 then the lines intersect.
         * 
         * Source: http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
         */
        checkPoints();

        boolean result = false;
        float points[] = getPoints();           // (x3, y3)  and (x4, y4)
        float thatPoints[] = shape.getPoints(); // (x1, y1)  and (x2, y2)
        int length = points.length;
        int thatLength = thatPoints.length;
        double unknownA;
        double unknownB;
        
        if (!closed()) {
        	length -= 2;
        }
        if (!shape.closed()) {
        	thatLength -= 2;
        }
        
        // x1 = thatPoints[j]
        // x2 = thatPoints[j + 2]
        // y1 = thatPoints[j + 1]
        // y2 = thatPoints[j + 3]
        // x3 = points[i]
        // x4 = points[i + 2]
        // y3 = points[i + 1]
        // y4 = points[i + 3]
        for(int i=0;i<length;i+=2) {        	
        	int iNext = i+2;
	    	if (iNext >= points.length) {
	    		iNext = 0;
	    	}
	    	
            for(int j=0;j<thatLength;j+=2) {
            	int jNext = j+2;
            	if (jNext >= thatPoints.length) {
            		jNext = 0;
            	}

                unknownA = (((points[iNext] - points[i]) * (double) (thatPoints[j + 1] - points[i + 1])) - 
                        ((points[iNext+1] - points[i + 1]) * (thatPoints[j] - points[i]))) / 
                        (((points[iNext+1] - points[i + 1]) * (thatPoints[jNext] - thatPoints[j])) - 
                                ((points[iNext] - points[i]) * (thatPoints[jNext+1] - thatPoints[j + 1])));
                unknownB = (((thatPoints[jNext] - thatPoints[j]) * (double) (thatPoints[j + 1] - points[i + 1])) - 
                        ((thatPoints[jNext+1] - thatPoints[j + 1]) * (thatPoints[j] - points[i]))) / 
                        (((points[iNext+1] - points[i + 1]) * (thatPoints[jNext] - thatPoints[j])) - 
                                ((points[iNext] - points[i]) * (thatPoints[jNext+1] - thatPoints[j + 1])));
                
                if(unknownA >= 0 && unknownA <= 1 && unknownB >= 0 && unknownB <= 1) {
                    result = true;
                    break;
                }
            }
            if(result) {
                break;
            }
        }

        return result;
    }
1335040
private static boolean intersectsPoint(Geometry point, Geometry geometry) {
		if (geometry.getGeometries() != null) {
			for (Geometry child : geometry.getGeometries()) {
				if (intersectsPoint(point, child)) {
					return true;
				}
			}
		}
		if (geometry.getCoordinates() != null) {
			Coordinate coordinate = point.getCoordinates()[0];
			if (geometry.getCoordinates().length == 1) {
				return coordinate.equals(geometry.getCoordinates()[0]);
			} else {
				for (int i = 0; i < geometry.getCoordinates().length - 1; i++) {
					double distance = MathService.distance(geometry.getCoordinates()[i],
							geometry.getCoordinates()[i + 1], coordinate);
					if (distance < DEFAULT_DOUBLE_DELTA) {
						return true;
					}
				}
			}
		}
		return false;
	}
283929
public static int intersectShape (IShape s, float x, float y, float w, float h) {
        if (!s.bounds().intersects(x, y, w, h)) {
            return 0;
        }
        return intersectPath(s.pathIterator(null), x, y, w, h);
    }