Java – Punto di intersezione di un poligono e una linea

C’è qualche funzione che mi darà il punto di intersezione di un Polygon e Line2D ?

Ho un poligono e un segmento di linea che so intersecano Voglio il valore reale del punto di intersezione non una risposta booleana.

Ecco qui. I metodi interessanti sono getIntersections e getIntersection. Il precedente analizza tutti i segmenti poligonali e verifica le intersezioni, il secondo esegue il calcolo effettivo. Tieni presente che il calcolo può essere seriamente ottimizzato e non controlla la divisione per 0. Ciò funzionerà anche solo per i poligoni. Potrebbe essere adattato per lavorare con altre forms se si introducono calcoli per le curve cubiche e quadratiche. Si presume che Line2D.Double venga utilizzato al posto di Line2D.Float. Un Set viene utilizzato per evitare punti duplicati (potrebbe verificarsi in intersezioni angolo poligono).

Si prega di non usare questo senza test approfonditi, dal momento che ho appena hackerato insieme rapidamente e non sono sicuro che sia completamente sano.

 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 intersections = getIntersections(poly, line); for(Iterator it = intersections.iterator(); it.hasNext();) { final Point2D point = it.next(); System.out.println("Intersection: " + point.toString()); } } public static Set 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 intersections = new HashSet(); //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); } } 

C’è java.awt.geom.Area.intersect(Area) usando l’ Area(Shape) costruttore Area(Shape) con il Poligono e passando il Line2D come un’Area da intersecare ti darà l’Area che è intersecata.

È necessario tenere presente che potrebbe intersecarsi in più punti.

Chiamiamo il segmento di linea del poligono P e il segmento di linea reale L.

Troviamo la pendenza di ogni linea (la pendenza è m)

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

Trova l’intercetta y di ogni riga // y = mx + b dove b è y-intercetta bl = ly1 – (ml * lx1); bp = py1 – (pl * px1);

Puoi risolvere il valore x con:

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

Quindi collega quella X in una delle equazioni per ottenere la Y

 y = ml * x + bl 

Ecco una versione implementata dell’algoritmo

 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]); } } 

e risultati:

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

Con grande successo, ho usato questo approccio:

 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) } 

Se non si è obbligati a utilizzare gli oggetti Polygon e Line2D , consiglierei di utilizzare JTS .

  • Crea geometria LinearRing (il tuo poligono).
  • Crea geometria LineString .
  • Crea punti di intersezione usando il metodo di intersezione .

Esempio di codice semplice:

 // 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()); } 

Il risultato è:

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