Java - point d'Intersection d'un Polygone et de la Ligne

Vous êtes ici. Les méthodes intéressantes sont getIntersections et getIntersection. L'ex-analyse sur tous les segments de polygone et des contrôles pour les intersections, ce dernier effectue le calcul. Ne gardez à l'esprit que le calcul peut être sérieusement optimisé et ne vérifie pas de division par 0. Cela permettra également de travailler uniquement pour les polygones. Il pourrait être adapté pour fonctionner avec d'autres formes, si vous introduisez de calculs pour cubique et quadratique courbes. Il est supposé que Line2D.Double est utilisé à la place de Line2D.Flotteur. Un Ensemble est utilisé pour éviter de dupliquer des points peut se produire sur un polygone coin intersections).

S'il vous plaît ne pas utiliser ce sans de nombreux essais, depuis que j'ai juste piraté ensemble rapidement et je suis pas sûr que c'est complètement le son.

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

OriginalL'auteur

Que vous devez garder à l'esprit qu'il pourrait se croisent à plusieurs endroits.

Appelons le segment du polygone P et le réel segment de la ligne L.

Nous trouvons la pente de chaque ligne de pente (m)

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

Trouver l'ordonnée à l'origine de chaque ligne
//y = mx+b, où b est l'ordonnée à l'origine
bl = ly1 - (ml*lx1);
bp = py1 - (pl*px1);

Vous pouvez résoudre pour la valeur x avec:

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

Puis branchez le X, dans l'une des équations pour obtenir les Y

y = ml * x + bl

Voici une version mise en application de l'algorithme

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

et résultats:

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

OriginalL'auteur

Si vous n'êtes pas limité à l'utilisation de la Polygone et Line2D Objets je vous recommande d'utiliser JTS.

• Créer LinearRing géométrie (votre polygone).
• Créer LineString géométrie.
• Créer des points d'intersection(s) à l'aide de la intersection méthode.

Exemple de code Simple:

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

Résultat est:

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

OriginalL'auteur