Java Intersección ¿Hay alguna función que me dará la punta de un Polygon y Line2D intersección?punto de un polígono y línea
que tienen un polígono y un segmento de línea, que yo sepa se cruzan Quiero que el valor real del punto de intersección no una respuesta booleana.
Hay java.awt.geom.Area.intersect(Area) usando el constructor Area(Shape) con su polígono y pasando su Line2D como un área para intersecar le dará el área que se cruza.
Debe tener en cuenta que puede cruzarse en varios lugares.
Llamemos al segmento de línea del polígono P y el segmento de recta real L.
Encontramos la pendiente de cada línea (pendiente es m)
ml = (ly1-ly2)/(lx1-lx2);
mp = (ply-pl2)/(px1-px2);
Encuentre la intersección de cada línea // y = mx + b donde b es el intercepto y bl = ly1 - (ml * lx1); bp = py1 - (pl * px1);
Puede resolver el valor de x con:
x = (bp - bl)/(ml - mp)
Luego enchufe que X en una de las ecuaciones para obtener la Y
y = ml * x + bl
Aquí es una versión práctica del 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]);
}
}
y resultados:
C:\Documents and Settings\glow\My Documents>java pointtest
3.4 3.4
C:\Documents and Settings\glow\My Documents>
Debo señalar que hay algunas condiciones que no se tratan aquí. ¿Qué pasa cuando las líneas son las mismas? ¿Qué sucede cuando las líneas no se cruzan (pendiente igual)? ¿Qué sucede si la intersección ocurre fuera del segmento de línea? ¿Qué pasa si uno de ellos tiene pendiente cero? Hay algunos casos especiales para cubrir que se dejan como un ejercicio para el lector. – corsiKa
Aquí tienes. Los métodos interesantes son getIntersections y getIntersection. El primero analiza todos los segmentos del polígono y verifica las intersecciones; el segundo realiza el cálculo real. Tenga en cuenta que el cálculo puede optimizarse seriamente y no verifica la división por 0. Esto también funcionará solo para los polígonos. Se puede adaptar para trabajar con otras formas si introduce cálculos para curvas cúbicas y cuadráticas. Se supone que se utiliza Line2D.Double en lugar de Line2D.Float. Un conjunto se usa para evitar puntos duplicados (puede ocurrir en intersecciones de esquina de polígono).
Por favor, no use esto sin pruebas exhaustivas, ya que sólo he hackeado juntos rápidamente y no estoy seguro de que es completamente sonido.
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);
}
}
¡¡¡Niza !!!!!!!!!!! – Evgeny
Con gran éxito, he utilizado este enfoque:
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)
}
Si no está limitado a utilizar el Polígono y Line2D objetos que recomendaría usar JTS.
código de ejemplo 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());
}
El resultado es:
(5.0, 0.0, NaN)
(5.0, 10.0, NaN)
probablemente debería añadir Sé que cruza exactamente en 1 lugar, porque sé que un punto está fuera y uno es dentro del polígono Pero no sé qué segmento del polígono interseca – bryan