Schnittpunkt Strecke mit Polygon

[Java xyrse123]

Hallo,

ich wollte eine Methode schreiben, die ein boolean zurückgibt, ob eine Strecke (x1,y1,x2,y2) und ein Polygon sich schneiden.
Wenn die Strecke einen Eckpunkt durchläuft oder auf einer Polygonseite liegt, soll es nicht als schneiden gelten.

Meine Idee war, z.B 1000 Punkte auf der Strecke zu nehmen(durch Einsetzen in Geradengleichung) und mit der Polygon contains Methode zu überprüfen, ob der Punkt im Polygon liegt.

public boolean intersectsLine(double x1, double y1, double x2, double y2) {

    boolean intersects = false;

    if (x2 - x1 == 0) { // unendliche Steigung
        return intersects;
    }

    double m  =  (y2 - y1) / (x2 - x1); // Steigung
    double b = y1 - m * x1;
    double l = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)); // Läbnge der Strecke
    double s = l / 1000.0;  // Strecke in 1000 teilstrecken teilen


    if( m == 0.0) { // keine Steigung
        m = 1;
    }

    for (double i = x1 + s; i < x2; i += s) { // 1000 Teilpunkte von Strecke testen
        double j = m * i + b;

        if (polygon.contains(i, j)) { // Test ob Punkt in Polygon
            intersects = true;
            break;            }

    }
    return intersects;
}

Diese Vorgehensweise funktioniert nur in den wenigsten Fällen, hat wer eine Idee wo der Fehler ist?

Danke im Vorraus.

 

[krgewb]

double i = x1 + s;

Wieso addierst du schon mal s?

Wie dem auch sei. Du wirst immer Abweichungen im Nachkommastellenbereich haben. Deshalb vergleiche ich nicht mit == sondern ich setze mir einen Toleranzwert, der meinetwegen epsilon heißt und dann vergleiche ich mithilfe von <.

 

[Blender3D]

Diese Vorgehensweise funktioniert nur in den wenigsten Fällen, hat wer eine Idee wo der Fehler ist?

Die Idee ist nicht gut.
Lösungsweg:
1) Bilde aus der Strecke eine Gerade g:
2) Bilde aus allen Punkte des Polygons Paare und mache Geraden p1, p2 .. pn
3) Suche den Schnittpunkt der Geraden p1, p2.. pn mit der Geraden g. Wenn der Schnittpunkt im Intervall der Stecke liegt schneiden sich die Strecke und das Polygon.

 

[Enceladus271]

Ich stimme Blender zu dass die Idee nicht gut ist. Insbesondere weil der Algorithmus nicht zuverlässig das korrekte Ergebnis liefert.

Bilde aus allen Punkte des Polygons Paare

Der Nachteil hierbei ist aber, dass man einen Algorithmus mit quadratischer Laufzeit bekommt. Wenn du die Kanten des Polygons kennst könntest du einfach Prüfen ob eine der Kanten deine Strecke schneidet. Der Algo hätte dann lineare Laufzeit.

 

[mihe7]

mit der Polygon contains Methode zu überprüfen, ob der Punkt im Polygon liegt.

       v
       |
 +-----|-----+
 |     |     | P
 +-----|-----+
       |

v schneidet ganz offensichtlich P aber keiner der Endpunkte von v liegt im Polygon P. Schon deswegen wir Dein Vorgehen nicht für alle Fälle funktionieren.

Wenn Du die Kanten kennst, mach es wie @Enceladus271 geschrieben hat. Kennst Du nur die Eckpunkte, und handelt es sich um ein einfaches Polygon, sollte sich das Problem mit einem Sweep lösen lassen.

Was die Existenz eines Schnittpunkts betrifft, kannst Du Dich der Determinanten zur Berechnung des Doppelten der Dreiecksfläche bedienen. Mit dieser lässt sich bestimmen, ob ein Punkt auf, links oder rechts (von) einer Geraden befindet, die durch zwei gegebene Punkte verläuft. Das Vorzeichen zeigt an, auf welcher Seite der Punkt liegt (ist das Ergebnis 0, liegt der Punkt auf der Geraden).

Wenn ich mich nicht vertan habe ist: f(p, q, r) := qx*(ry - py) + px*(qy - ry) + rx*(py-qy) mit p=(px, py), q = (qx, qy) und r = (rx, ry). Dann zeigt f(p,q,r) die Lage der Punkts r in Bezug auf die Gerade an, die durch die Punkte p und q verläuft.

Dann dürften sich zwei Liniensegmente u=(u1, u2) und v=(v1, v2) schneiden, gdw. sgn(f(u1, u2, v1)) != sgn(f(u1, u2, v2)) und sgn(f(v1, v2, u1)) != sgn(f(v1, v2, u2)) gilt.

 

[Blender3D]

Der Nachteil hierbei ist aber, dass man einen Algorithmus mit quadratischer Laufzeit bekommt. Wenn du die Kanten des Polygons kennst könntest du einfach Prüfen ob eine der Kanten deine Strecke schneidet. Der Algo hätte dann lineare Laufzeit.

Bei Javas Polygon hast Du die Punkte als Pfad in xpoints[], ypoints[] vorliegen.
Vorgänger mit Nachfolger bilden jeweils eine Gerade. Bei einem Dreieck --> 3 Geraden , Viereck -- > 4 .. usw. Das ist linear.

 

[Thallius]

Bei Javas Polygon hast Du die Punkte als Pfad in xpoints[], ypoints[] vorliegen.
Vorgänger mit Nachfolger bilden jeweils eine Gerade. Bei einem Dreieck --> 3 Geraden , Viereck -- > 4 .. usw. Das ist linear.

Nimm mal ein polygon wo sie die Kanten schneiden. Dann wird’s ekelig..

 

[mrBrown]

Bei Javas Polygon hast Du die Punkte als Pfad in xpoints[], ypoints[] vorliegen.
Vorgänger mit Nachfolger bilden jeweils eine Gerade. Bei einem Dreieck --> 3 Geraden , Viereck -- > 4 .. usw. Das ist linear.

Das ist aber nicht, aus allen Punkten Paare zu bilden, sondern nur jeweils die Paare, die zu einer Kante gehören, und damit genau das, was @Enceladus271 meinte.

Nimm mal ein polygon wo sie die Kanten schneiden. Dann wird’s ekelig..

Die Laufzeit in Bezug auf Ecken/Kanten wird ekelig oder was?

Eigentlich sollte da die genannte Lösung genauso funktionieren, und nicht ekeliger werden, oder was meinst du?

Kommt drauf an, wie man die genannten Sonderfälle (Ecken/Kanten nur „berührt“) behandelt, wenn das Polygon zb die Form zwei sich an den Spitzen berührender Dreiecke hat, und die Gerade genau den Punkt in der Mitte schneidet...

 

[Blender3D]

Das ist aber nicht, aus allen Punkten Paare zu bilden

War nicht gut formuliert. War aber für den der die Idee versanden hat aber nicht wirklich das Problem.

 

[mrBrown]

War nicht gut formuliert. War aber für den der die Idee versanden hat aber nicht wirklich das Problem.

Letzteres gilt wohl auch, wenn du „Foo Bar“ als Antwort geschrieben hättest

 

[mihe7]

    public static boolean intersects(Polygon poly, Point l1, Point l2) {
        Point p = new Point(poly.xpoints[0], poly.ypoints[0]);
        
        for (int i = 1, n = poly.npoints; i < n; i++) {
            Point q = new Point(poly.xpoints[i], poly.ypoints[i]);

            int t1 = (int)Math.signum(tria(p,q,l1));
            int t2 = (int)Math.signum(tria(l1, l2, p));
            if (t1 != 0 && t1 == -(int)Math.signum(tria(p,q,l2)) &&
                    t2 != 0 && t2 == -(int)Math.signum(tria(l1,l2,q))) {
                return true;
            }

            p = q;
        }

        return false;
    }

    public static int tria(Point p, Point q, Point r) {
        return q.x*(r.y - p.y) + p.x*(q.y - r.y) + r.x*(p.y - q.y);
    }

 

[Java xyrse123]

Hallo,

danke für die Antworten. Ich glaube es nicht ganz klar geworden wie ich vorgehen wollte.

Die Strecke möchte ich in 1000 Teilstrecken zerlegen und alle Eckpunkte dieser Teilstrecken ( bis auf den Start und -Endpunkt der Strecke) mit der Polygon contains-Methode überprüfen ob sie im Polygon liegen. Wenn einer dieser Punkte im Polygon liegt, schneidet auch die Strecke das Polygon.

Die Idee ist nicht gut.
Lösungsweg:

Warum ist die Idee nicht gut?
Mit der Zerteilung ist es nur eine Annäherung, aber für die aller meisten Fälle müsste es ausreichen.

Ich habe mein Programm jetzt noch verändert, aber es funktioniert immer noch nicht richtig:
(In manchen Testfällen klappt es aber)

public boolean intersectsLine2(double x1, double y1, double x2, double y2) {

    ArrayList<PointF> points = lineToPoints(x1, y1, x2, y2);

    for(PointF p: points) {

        if(polygon.contains(p.x, p.y)) {
          return true;
        }
    }

    return false;
}

/*
Teilt eine Linie in 1000 Teilstrecken auf und gibt
1000  punkt zurück die auf der linie liegen
*/

public ArrayList<PointF> lineToPoints(double x1, double y1, double x2, double y2) {

    ArrayList<PointF> points = new ArrayList<>();

    double s = (x1 - x2) / 1000.0;

    if(x2 - x1 == 0) {  // Linie senkrecht zu y-Achse
        s = (y2 - y1) / 1000.0;

        for(int i = 1; i < 1000; i++) {
            double y = y1 + i * s;
            points.add(new PointF(x1, y));
        }
        return points;
    }


    double m  = (y2 - y1) / (x2 - x1); // Steigung
    double b = y2 - (m * x2); // Y-Achsenabschnitt


    if(m == 0.0) { // Linie waagerecht zu x-Achse
        m = 1.0;
    }

    for(int i = 1; i < 1000.0; i++) {
         double x = x1 - s * i;
         double y = m * x + b;
         points.add(new PointF(x, y));
    }

    return points;
}

 

[mihe7]

Die Strecke möchte ich in 1000 Teilstrecken zerlegen und alle Eckpunkte dieser Teilstrecken ( bis auf den Start und -Endpunkt der Strecke) mit der Polygon contains-Methode überprüfen ob sie im Polygon liegen. Wenn einer dieser Punkte im Polygon liegt, schneidet auch die Strecke das Polygon.

Warum willst Du denn die Strecke nochmal in 1000 Teilstrecken zerlegen?!? Das ist ja gleich noch unsinniger.

 

[mrBrown]

Warum ist die Idee den nicht gut?
Mit der Zerteilung ist es nur eine Annäherung, aber für die aller meisten Fälle müsste es ausreichen.

Warum willst du denn ’ne Annäherung, wenn du’s genau haben kannst?

 

[Java xyrse123]

Warum willst Du denn die Strecke nochmal in 1000 Teilstrecken zerlegen?!? Das ist ja gleich noch unsinniger.

Weil ich dann 1000 Punkte auf der Strecke bekomme und die dann einzeln testen kann.

Meine Frage ist nur, ihr schreibt alle die Idee wäre unsinnig, aber nicht warum sie unsinnig ist.

Warum willst du denn ’ne Annäherung, wenn du’s genau haben kannst?

Die anderen Vorschläge verstehe ich nicht wirklich, deswegen wollte ich es erstmal so weiterversuchen.

 

[mrBrown]

Meine Frage ist nur, ihr schreibt alle die Idee wäre unsinnig, aber nicht warum sie unsinnig ist.

Es ist nur eine Annäherung und ist deutlich aufwändiger, als die übliche Variante.

Die anderen Vorschläge verstehe ich nicht wirklich, deswegen wollte ich es erstmal so weiterversuchen.

Die übliche Variante wäre: gibt es einen Schnittpunkt zwischen der zu testenden Strecke und einer Kante?
Strecke und alle Kanten hast du, du musst also nur noch das schneiden testen, und auch das ist in Java bereits gelöst (Line2D...)

 

[httpdigest]

Bilde vielleicht wenigstens in der Geradengleichung y nicht als Funktion von x ab. Da krieg ich immer Augenkrebs, wenn Leute anfangen, Steigungen auszurechnen und Sonderfälle mit m=inf abzudecken. Bitte verwende die wesentlich einfachere und robustere Variante mit einer parametrisierten Geradengleichung, also `x(t) = x₁ + t*(x₂-x₁)` und `y(t) = y₁ + t*(y₂-y₁)`:

public static List<PointF> lineToPoints(
    int N, double x1, double y1, double x2, double y2) {
  double dx = x2 - x1, dy = y2 - y1;
  List<Point2D> points = new ArrayList<>(N);
  for (int i = 1; i <= N; i++)
    points.add(new PointF(
        x1 + dx * (double) i / (N + 1),
        y1 + dy * (double) i / (N + 1)
    ));
  return points;
}

 

[Blender3D]

if (x2 - x1 == 0) { // unendliche Steigung return intersects; } double m = (y2 - y1) / (x2 - x1); // Steigung double b = y1 - m * x1; double l = Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)); // Läbnge der Strecke double s = l / 1000.0; // Strecke in 1000 teilstrecken teilen

a) Unendliche Steigung stimmt hier nicht sondern Steigung ist 0. Das bedeutet, dass die Strecke parallel zur y-Achse ist und es sehr wohl möglich ist, dass sie das Polygon schneidet.
b) Das ständige addieren der Teillänge s kumuliert den Fehler. -> Du bewegst dich nicht wirklich auf der Geraden.

c) Warum annähern wenn man analytisch genau lösen kann ?


Wie schon erwähnt keine gute Idee.

 

[httpdigest]

a) Unendliche Steigung stimmt hier nicht sondern Steigung ist 0. Das bedeutet, dass die Strecke parallel zur y-Achse ist

"Gerade parallel zur y-Achse" und "Gerade mit unendlicher Steigung" ist dasselbe (zumindest in der Analysis), da man eine Gerade dort immer als Funktion y von x angibt: y(x) = m*x + c. Und damit diese Funktion (welche dann keine Funktion mehr wäre) parallel zur Y-Achse ist, müsste m (also die "Steigung") = unendlich sein.

 

[mihe7]

Meine Frage ist nur, ihr schreibt alle die Idee wäre unsinnig, aber nicht warum sie unsinnig ist.

Das ist nicht richtig. In Kommentar #5 habe ich das Problem geschildert und mit 1000 Teilstrecken vertausendfachst Du es nur. Fairerweise muss man dazu sagen, dass Du andererseits die Wahrscheinlichkeit erhöhst, einen Punkt zu treffen, der tatsächlich im Polygon liegt, allerdings gilt das nun mal nicht für den allgemeinen Fall.

Hinzu kommt, dass die Frage, ob ein Punkt in einem Polygon enthalten ist, den gleichen Aufwand nach sich zieht, wie die Frage, ob eine gegebene Strecke eine Kante des Polygons schneidet. Du erhöhst den Aufwand nur künstlich.

 

[mihe7]

Ganz übersehen:

Die anderen Vorschläge verstehe ich nicht wirklich, deswegen wollte ich es erstmal so weiterversuchen.

Was verstehst Du denn nicht? Die Vorschläge sagen im Prinzip alle dasselbe: prüfe für jede Kante des Polygons, ob sich Deine Strecke und die Kante schneiden.

 

[Blender3D]

Gerade parallel zur y-Achse" und "Gerade mit unendlicher Steigung" ist dasselbe (zumindest in der Analysis), da man eine Gerade dort immer als Funktion y von x angibt: y(x) = m*x + c. Und damit diese Funktion (welche dann keine Funktion mehr wäre) parallel zur Y-Achse ist, müsste m (also die "Steigung") = unendlich sein.

In der Analysis spricht man hier im Konjunktiv.
Die Steigung einer Gerade, die parallel zur y-Achse verläuft, wäre "unendlich". Es kann allerdings keine Funktion in Abhängigkeit von x x mit einer solchen Gerade als Graphen geben, da dem gleichen x-Wert verschiedene y-Werte zugeordnet werden müssten.

Trotzdem lässt sich eine solche Gerade durch eine Gleichung von der Form x=r x=r beschreiben.
Aber der Punkt ist das ein Schnittpunkt möglich ist.

 

[Blender3D]

Meine Idee war, z.B 1000 Punkte auf der Strecke zu nehmen(durch Einsetzen in Geradengleichung) und mit der Polygon contains Methode zu überprüfen, ob der Punkt im Polygon liegt.

Hier eine Variante das Problem analytisch zu lösen.
Die Klasse Segment repräsentiert eine Teilstrecke. Sie besitzt Methoden, die Schnittpunkte mit einem Polygon oder einem anderen Segment liefert.

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Point;
import java.awt.Polygon;
import java.util.Vector;

public class Segment {
    private Point2D a;
    private Point2D b;
    private Color color = Color.BLACK;

    public Segment(Point2D a, Point2D b) {
        this.a = a;
        this.b = b;
    }

    public Segment(Point a, Point b) {
        this.a = new Point2D(a.x, a.y);
        this.b = new Point2D(b.x, b.y);
    }

    public Segment(int x1, int y1, int x2, int y2) {
        this.a = new Point2D(x1, y1);
        this.b = new Point2D(x2, y2);
    }

    public void draw(Graphics g) {
        Point a = this.a.toPoint();
        Point b = this.b.toPoint();
        Color old = g.getColor();
        g.setColor(color);
        g.drawLine(a.x, a.y, b.x, b.y);
        g.setColor(old);
    }

    public Point2D getLinedIntersectPoint(Segment s) {
        float divXseg1 = s.a.getX() - s.b.getX();
        float slopeSeg1 = divXseg1 == 0 ? 0 : (s.a.getY() - s.b.getY()) / divXseg1;
        float interceptSeg1 = s.a.getY() - slopeSeg1 * s.a.getX();

        float divXseg2 = a.getX() - b.getX();
        float slopeSeg2 = divXseg2 == 0 ? 0 : (a.getY() - b.getY()) / divXseg2;
        float interceptSeg2 = a.getY() - slopeSeg2 * a.getX();

        if (divXseg1 == 0 && divXseg2 != 0) // parallel to y axis
            return new Point2D(s.a.getX(), s.a.getX() * slopeSeg2 + interceptSeg2);

        float div = slopeSeg1 - slopeSeg2;
        if (div == 0) // parallel
            return null;
        float x = (interceptSeg2 - interceptSeg1) / div;
        float y = slopeSeg2 * x + interceptSeg2;
        return new Point2D(x, y);
    }

    public Point2D getIntersectPoint(Segment s) {
        Point2D intersectPoint = getLinedIntersectPoint(s);
        if (intersectPoint == null)
            return null;
        boolean xRange = isInRange(a.getX(), b.getX(), intersectPoint.getX());
        boolean xxRange = isInRange(s.a.getX(), s.b.getX(), intersectPoint.getX());
        return (xRange && xxRange) ? intersectPoint : null;
    }

    public Point2D[] getIntersectPoints(Polygon p) {
        if (p == null)
            return null;
        int[] x = p.xpoints;
        int[] y = p.ypoints;
        int len = x.length;
        if (len < 2)
            return null;
        Vector<Point2D> tmp = new Vector<Point2D>();
        for (int i = 0; i < len; i++) {
            Segment test = i == 0 ? new Segment(x[0], y[0], x[len - 1], y[len - 1])
                    : new Segment(x[i - 1], y[i - 1], x[i], y[i]);
            Point2D intersectPoint = null;
            if ((intersectPoint = test.getIntersectPoint(this)) != null)
                tmp.add(intersectPoint);
        }
        if (tmp.size() == 0)
            return null;
        Point2D[] points = new Point2D[tmp.size()];
        return tmp.toArray(points);
    }

    public static boolean isInRange(float start, float end, float pos) {
        if (start > end) {
            float tmp = start;
            start = end;
            end = tmp;
        }
        return start <= pos && pos <= end;
    }

    public void setColor(Color color) {
        this.color = color;
    }

    @Override
    public String toString() {
        return "<" + a + " - " + b + ">";
    }
}

import java.awt.Point;

public class Point2D {
    private final float x;
    private final float y;

    public Point2D(float x, float y) {
        this.x = x;
        this.y = y;
    }

    public float getDistanceTo(Point2D p) {
        float xx = p.x - x;
        float yy = p.y - y;
        return (float) Math.sqrt(xx * xx + yy * yy);
    }

    public float getX() {
        return x;
    }

    public float getY() {
        return y;
    }

    public Point toPoint() {
        return new Point((int) x, (int) y);
    }

    @Override
    public String toString() {
        return String.format("[%.2f|%.2f]", x, y);
    }
}

 

[Blender3D]

Zum testen der Klasse Segment ein kleine GUI.
Durch 2x linksklicken kann man das Segment neu Zeichen.

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.awt.Polygon;
import java.awt.RenderingHints;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;

import javax.swing.JPanel;

@SuppressWarnings("serial")
public class SegmentPanel extends JPanel {
    private Segment segment = null;
    private Polygon polygon = null;
    private Point mouseClick = null; // saves first click for new segment

    public SegmentPanel(int width, int height) {
        super.setPreferredSize(new Dimension(width, width));
        createSegement(new Point(250, 100), new Point(250, 300));
        int[] x = { 200, 450,300 ,200,150 };
        int[] y = { 300, 50, 400,150,350 };
        polygon = new Polygon(x, y, x.length);
        setBackground(Color.BLACK);
        addMouseListener(new MouseAdapter() {
            @Override
            public void mouseReleased(MouseEvent e) {
                Point pos = e.getPoint();
                if (mouseClick != null) {
                    if (e.getButton() == MouseEvent.BUTTON3)
                        pos.x = mouseClick.x;// vertical line
                    if (e.getButton() == MouseEvent.BUTTON2)
                        pos.y = mouseClick.y;// horizontal line
                    createSegement(pos, mouseClick);
                    mouseClick = null;
                } else
                    mouseClick = pos;
                repaint();
            }
        });

    }

    private void createSegement(Point p1, Point p2) {
        segment = new Segment(p1, p2);
        segment.setColor(Color.WHITE);
    }

    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);
        ((Graphics2D) g).setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
        g.setColor(Color.GREEN);
        if (polygon != null)
            g.drawPolygon(polygon); // draw polygon
        if (segment != null) {
            segment.draw(g); // draw segment
            Point2D[] intersectPoints = segment.getIntersectPoints(polygon);
            if (intersectPoints != null) {
                for (Point2D p : intersectPoints) { // draw intersect points
                    Point pos = p.toPoint();
                    g.setColor(Color.RED);
                    g.drawOval(pos.x - 8, pos.y - 5, 16, 16);
                }
            }
        }
        if (mouseClick != null) { // draw segment's start point
            g.setColor(Color.WHITE);
            g.drawOval(mouseClick.x - 5, mouseClick.y - 5, 10, 10);
        }
    }

}

public static void main(String[] args) {       
        JFrame frame = new JFrame("Strecke in Polygon");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.add(new SegmentPanel(500, 500));
        frame.pack();
        frame.setVisible(true);
    }

 

[MoxxiManagarm]

Ich sehe noch keinen Vorschlag mit dem PathIterator.

public class Test {
    // (0,0) is explicit contained
    public static Polygon p = new Polygon(new int[]{0, 2, 2}, new int[]{2, 2, 0}, 3);
   
    public static boolean intersects(double x1, double y1, double x2, double y2) {
        Line2D.Double lineStatic = new Line2D.Double(x1, y1, x2, y2);
        Line2D.Double linePolygon = new Line2D.Double(0.0, 0.0, 0.0, 0.0);
       
        PathIterator pIter = p.getPathIterator(null);
       
        while(!pIter.isDone()) {
            double[] endPoint = new double[2];
            pIter.currentSegment(endPoint);
           
            linePolygon.setLine(linePolygon.getX2(), linePolygon.getY2(), endPoint[0], endPoint[1]);
           
            if(lineStatic.intersectsLine(linePolygon)) {
                if(linePolygon.ptLineDist(lineStatic.getP1()) != 0.0 && linePolygon.ptLineDist(lineStatic.getP2()) != 0.0) {
                    return true;
                }
            }
           
            pIter.next();
        }
       
        return false;
    }
   
    public static void main(String args[]) {
        System.out.println(intersects(0, 2, 2, 2));
        System.out.println(intersects(0, 2, 1, 2));
        System.out.println(intersects(1, 1, 1, 3)); // true
        System.out.println(intersects(2, 1, 3, 1));
        System.out.println(intersects(3, 3, 3, 5));
        System.out.println(intersects(-1, 1, 3, 1)); // true
    }
}

Edit: Mein Vorschlag fängt noch nicht den Beispielfall intersects(-1, 2, 3, 2) ab, bei dem also eine Linie des Polygons vollständig Teil der Strecke ist. Das wäre vom TE dann noch zu ergänzen.

 

[Blender3D]

Zum testen der Klasse Segment ein kleine GUI.

Ein Screenshot des Test Programms von Post #24.

 

[Java xyrse123]

Ich habe es jetzt so umgesetzt wir ihr es geschrieben habt(also testen ob die Strecke eine der Polygonkanten schneidet) und es scheint zu funktionieren und ist auch weniger aufwändig.
Statt Line2D verwende ich nur meine eigene Line Klasse um die Sonderfälle abzudecken.

Danke für Eure Bespiele @Blender3D und @MoxxiManagarm.