Java-多邊形和線的交點

Question

是否有任何函數會給我一個Polygon和Line2D的交點？

我有一個多邊形和一個線段，我知道相交我想交點的實際值不是布爾答案。

Answer 1

有java.awt.geom.Area.intersect(Area)使用構造函數Area(Shape)與您的Polygon和傳遞您的Line2D作爲面積相交將給你相交的區域。

Answer 2

你需要記住它可能會在多個地方相交。

我們稱之爲多邊形P的線段和實線段L.

我們發現每條線的斜率（斜率爲m）

ml = (ly1-ly2)/(lx1-lx2); 
mp = (ply-pl2)/(px1-px2); 

查找每一行的y軸截距 // y = mx + b其中b是y截距 bl = ly1 - （ml * lx1）; bp = py1 - （pl * px1）;

可以解決與x值：

x = (bp - bl)/(ml - mp) 

然後就是X插入公式的一個獲得在Y

y = ml * x + bl 

這裏是算法的實現版本

class pointtest { 

    static float[] intersect(float lx1, float ly1, float lx2, float ly2, 
          float px1, float py1, float px2, float py2) { 
     // calc slope 
     float ml = (ly1-ly2)/(lx1-lx2); 
     float mp = (py1-py2)/(px1-px2);  

     // calc intercept   
     float bl = ly1 - (ml*lx1); 
     float bp = py1 - (mp*px1); 

     float x = (bp - bl)/(ml - mp); 
     float y = ml * x + bl; 

     return new float[]{x,y}; 
    } 

    public static void main(String[] args) { 

     float[] coords = intersect(1,1,5,5,1,4,5,3); 
     System.out.println(coords[0] + " " + coords[1]); 

    } 
} 

和結果：

C:\Documents and Settings\glow\My Documents>java pointtest 
3.4 3.4 

C:\Documents and Settings\glow\My Documents> 

Answer 3

給你。有趣的方法是getIntersections和getIntersection。前者解析所有多邊形線段並檢查交點，後者進行實際計算。請記住，計算可以嚴格優化，不會檢查除數爲0.這也只適用於多邊形。如果引入三次和二次曲線的計算，它可以適用於其他形狀。假定使用Line2D.Double而不是Line2D.Float。一套用於避免重複的點（可能發生在多邊形角落交叉點）。

請不要在沒有廣泛測試的情況下使用此功能，因爲我剛剛將它快速入侵併且不確定它是否完全正常。

package quickpolygontest; 

import java.awt.Polygon; 
import java.awt.geom.Line2D; 
import java.awt.geom.PathIterator; 
import java.awt.geom.Point2D; 
import java.util.HashSet; 
import java.util.Iterator; 
import java.util.Set; 

public class Main { 

    public static void main(String[] args) throws Exception { 

     final Polygon poly = new Polygon(new int[]{1,2,2,1}, new int[]{1,1,2,2}, 4); 
     final Line2D.Double line = new Line2D.Double(2.5, 1.3, 1.3, 2.5); 
     final Set<Point2D> intersections = getIntersections(poly, line); 
     for(Iterator<Point2D> it = intersections.iterator(); it.hasNext();) { 
      final Point2D point = it.next(); 
      System.out.println("Intersection: " + point.toString()); 
     } 

    } 

    public static Set<Point2D> getIntersections(final Polygon poly, final Line2D.Double line) throws Exception { 

     final PathIterator polyIt = poly.getPathIterator(null); //Getting an iterator along the polygon path 
     final double[] coords = new double[6]; //Double array with length 6 needed by iterator 
     final double[] firstCoords = new double[2]; //First point (needed for closing polygon path) 
     final double[] lastCoords = new double[2]; //Previously visited point 
     final Set<Point2D> intersections = new HashSet<Point2D>(); //List to hold found intersections 
     polyIt.currentSegment(firstCoords); //Getting the first coordinate pair 
     lastCoords[0] = firstCoords[0]; //Priming the previous coordinate pair 
     lastCoords[1] = firstCoords[1]; 
     polyIt.next(); 
     while(!polyIt.isDone()) { 
      final int type = polyIt.currentSegment(coords); 
      switch(type) { 
       case PathIterator.SEG_LINETO : { 
        final Line2D.Double currentLine = new Line2D.Double(lastCoords[0], lastCoords[1], coords[0], coords[1]); 
        if(currentLine.intersectsLine(line)) 
         intersections.add(getIntersection(currentLine, line)); 
        lastCoords[0] = coords[0]; 
        lastCoords[1] = coords[1]; 
        break; 
       } 
       case PathIterator.SEG_CLOSE : { 
        final Line2D.Double currentLine = new Line2D.Double(coords[0], coords[1], firstCoords[0], firstCoords[1]); 
        if(currentLine.intersectsLine(line)) 
         intersections.add(getIntersection(currentLine, line)); 
        break; 
       } 
       default : { 
        throw new Exception("Unsupported PathIterator segment type."); 
       } 
      } 
      polyIt.next(); 
     } 
     return intersections; 

    } 

    public static Point2D getIntersection(final Line2D.Double line1, final Line2D.Double line2) { 

     final double x1,y1, x2,y2, x3,y3, x4,y4; 
     x1 = line1.x1; y1 = line1.y1; x2 = line1.x2; y2 = line1.y2; 
     x3 = line2.x1; y3 = line2.y1; x4 = line2.x2; y4 = line2.y2; 
     final double x = (
       (x2 - x1)*(x3*y4 - x4*y3) - (x4 - x3)*(x1*y2 - x2*y1) 
       )/
       (
       (x1 - x2)*(y3 - y4) - (y1 - y2)*(x3 - x4) 
       ); 
     final double y = (
       (y3 - y4)*(x1*y2 - x2*y1) - (y1 - y2)*(x3*y4 - x4*y3) 
       )/
       (
       (x1 - x2)*(y3 - y4) - (y1 - y2)*(x3 - x4) 
       ); 

     return new Point2D.Double(x, y); 

    } 

} 

Answer 4

取得了巨大成功，我用這個方法：

Area a = new Area(shape1); 
Area b = new Area(shape2); 
b.intersect(a); 
if (!b.isEmpty()) { 
    //Shapes have non-empty intersection, so do you actions. 
    //In case of need, actual intersection is in Area b. (its destructive operation) 
} 

Answer 5

如果你並不侷限於使用多邊形和的Line2D對象，我會建議使用JTS。

• 創建LinearRing幾何（您的多邊形）。
• 創建LineString幾何。
• 使用intersection方法創建交叉點。

簡單的代碼示例：

// create ring: P1(0,0) - P2(0,10) - P3(10,10) - P4(0,10) 
LinearRing lr = new GeometryFactory().createLinearRing(new Coordinate[]{new Coordinate(0,0), new Coordinate(0,10), new Coordinate(10,10), new Coordinate(10,0), new Coordinate(0,0)}); 
// create line: P5(5, -1) - P6(5, 11) -> crossing the ring vertically in the middle 
LineString ls = new GeometryFactory().createLineString(new Coordinate[]{new Coordinate(5,-1), new Coordinate(5,11)}); 
// calculate intersection points 
Geometry intersectionPoints = lr.intersection(ls); 
// simple output of points 
for(Coordinate c : intersectionPoints.getCoordinates()){ 
    System.out.println(c.toString()); 
} 

結果是：

(5.0, 0.0, NaN) 
(5.0, 10.0, NaN)