Je dois trouver si Path2D s'intersecte. Pour l'instant, je le fais en extrayant simplement un tableau de lignes à partir de path, et en trouvant si l'une d'entre elles se croisent. Mais il a O (n^2) complexité, et c'est donc très lent. Y a-t-il un moyen plus rapide de le faire?Trouver si Path2D s'auto-intersecte
10
A
Répondre
3
Vous pouvez le faire plus rapidement en utilisant l'algorithme ligne de balayage: http://en.wikipedia.org/wiki/Sweep_line_algorithm
pseudocode:
Each line has a start point and an end point. Say that `start_x` <= `end_x` for all the lines.
Create an empty bucket of lines.
Sort all the points by their x coordinates, and then iterate through the sorted list.
If the current point is a start point, test its line against all the lines in the bucket, and then add its line to the
bucket.
if the current point is an end point, remove its line from the bucket.
Le pire des cas est encore O(N^2)
, mais le cas moyen est O(NlogN)
+0
Merci! Mais une amélioration à votre méthode - si vous maintenez l'ordre "above-below" dans le bucket (trier par le premier point y coordonnée de la ligne), vous pouvez tester la nouvelle ligne uniquement contre les lignes au-dessus et en dessous. log n) complexité du temps au lieu de O (n). Trouvé sur:
3
Voici mon Implémentation Java de cet algorithme:
import java.awt.Point;
import java.awt.geom.Line2D;
import java.awt.geom.PathIterator;
import java.util.*;
/**
* Path2D helper functions.
* <p/>
* @author Gili Tzabari
*/
public class Path2Ds
{
/**
* Indicates if a Path2D intersects itself.
* <p/>
* @return true if a Path2D intersects itself
*/
public static boolean isSelfIntersecting(PathIterator path)
{
SortedSet<Line2D> lines = getLines(path);
if (lines.size() <= 1)
return false;
Set<Line2D> candidates = new HashSet<Line2D>();
for (Line2D line: lines)
{
if (Double.compare(line.getP1().distance(line.getP2()), 0) <= 0)
{
// Lines of length 0 do not cause self-intersection
continue;
}
for (Iterator<Line2D> i = candidates.iterator(); i.hasNext();)
{
Line2D candidate = i.next();
// Logic borrowed from Line2D.intersectsLine()
int lineRelativeToCandidate1 = Line2D.relativeCCW(line.getX1(), line.getY1(), line.
getX2(),
line.getY2(), candidate.getX1(), candidate.getY1());
int lineRelativeToCandidate2 = Line2D.relativeCCW(line.getX1(), line.getY1(), line.
getX2(),
line.getY2(), candidate.getX2(), candidate.getY2());
int candidateRelativeToLine1 = Line2D.relativeCCW(candidate.getX1(),
candidate.getY1(),
candidate.getX2(), candidate.getY2(), line.getX1(), line.getY1());
int candidateRelativeToLine2 = Line2D.relativeCCW(candidate.getX1(),
candidate.getY1(),
candidate.getX2(), candidate.getY2(), line.getX2(), line.getY2());
boolean intersection = (lineRelativeToCandidate1 * lineRelativeToCandidate2 <= 0)
&& (candidateRelativeToLine1 * candidateRelativeToLine2 <= 0);
if (intersection)
{
// Lines may share a point, so long as they extend in different directions
if (lineRelativeToCandidate1 == 0 && lineRelativeToCandidate2 != 0)
{
// candidate.P1 shares a point with line
if (candidateRelativeToLine1 == 0 && candidateRelativeToLine2 != 0)
{
// line.P1 == candidate.P1
continue;
}
if (candidateRelativeToLine1 != 0 && candidateRelativeToLine2 == 0)
{
// line.P2 == candidate.P1
continue;
}
// else candidate.P1 intersects line
}
else if (lineRelativeToCandidate1 != 0 && lineRelativeToCandidate2 == 0)
{
// candidate.P2 shares a point with line
if (candidateRelativeToLine1 == 0 && candidateRelativeToLine2 != 0)
{
// line.P1 == candidate.P2
continue;
}
if (candidateRelativeToLine1 != 0 && candidateRelativeToLine2 == 0)
{
// line.P2 == candidate.P2
continue;
}
// else candidate.P2 intersects line
}
else
{
// line and candidate overlap
}
return true;
}
if (candidate.getX2() < line.getX1())
i.remove();
}
candidates.add(line);
}
return false;
}
/**
* Returns all lines in a path. The lines are constructed such that the starting point is found
* on the left (or same x-coordinate) of the ending point.
* <p/>
* @param path the path
* @return the lines, sorted in ascending order of the x-coordinate of the starting point and
* ending point, respectively
*/
private static SortedSet<Line2D> getLines(PathIterator path)
{
double[] coords = new double[6];
SortedSet<Line2D> result = new TreeSet<Line2D>(new Comparator<Line2D>()
{
@Override
public int compare(Line2D o1, Line2D o2)
{
int result = Double.compare(o1.getX1(), o2.getX1());
if (result == 0)
{
// Ensure we are consistent with equals()
return Double.compare(o1.getX2(), o2.getX2());
}
return result;
}
});
if (path.isDone())
return result;
int type = path.currentSegment(coords);
assert (type == PathIterator.SEG_MOVETO): type;
Point.Double startPoint = new Point.Double(coords[0], coords[1]);
Point.Double openPoint = startPoint;
path.next();
while (!path.isDone())
{
type = path.currentSegment(coords);
assert (type != PathIterator.SEG_CUBICTO && type != PathIterator.SEG_QUADTO): type;
switch (type)
{
case PathIterator.SEG_MOVETO:
{
openPoint = startPoint;
break;
}
case PathIterator.SEG_CLOSE:
{
coords[0] = openPoint.x;
coords[1] = openPoint.y;
break;
}
}
Point.Double endPoint = new Point.Double(coords[0], coords[1]);
if (Double.compare(startPoint.getX(), endPoint.getX()) < 0)
result.add(new Line2D.Double(startPoint, endPoint));
else
result.add(new Line2D.Double(endPoint, startPoint));
path.next();
startPoint = endPoint;
}
return result;
}
}
Questions connexes
- 1. Méthode pour trouver si Path2D croise ou contient un autre Path2D
- 2. Comment couper un Path2D?
- 3. Ajouter path2d à un jpanel
- 4. Analyseur Path2d de SVG vers Java
- 5. détection de pointeur de la souris sur une Path2D
- 6. Problèmes Création d'un outil de plume avec Java Path2D
- 7. Comment calculer la longueur d'un Path2D en Java?
- 8. onglet Facebook, trouver si aimé
- 9. Impossible de trouver le mot pour trouver "Si ..."
- 10. Trouver si: -char est entre [et]
- 11. DataTable trouver ou si introuvable insérer ligne
- 12. Trouver l'emplacement de la cellule si vide
- 13. Prototype trouver l'élément et seulement effectuer si
- 14. Comment trouver si une étiquette est ouverte
- 15. Regex trouver des chaînes si par
- 16. Comment trouver si un document est versionnable?
- 17. comment trouver si l'élément existe dans TBXML?
- 18. Mysql: trouver le plus proche valeur maximale, si pas trouver la valeur minimale la plus proche
- 19. Clojure: tâche lein ne peut pas trouver jdbc, même si l'application peut trouver bien
- 20. comment trouver EMI et comment trouver le montant principal si EMI est donné?
- 21. Comment trouver si une page redirige ou non?
- 22. trouver si le navigateur prend en charge JavaScript ou non
- 23. Trouver si une chaîne commence entre deux sections de l'alphabet
- 24. Comment trouver si un type générique est Liste <>
- 25. Comment trouver si l'application est appelée par "Share-Via"?
- 26. Trouver si le JDK est openJDK ou Oracle JDK
- 27. Trouver un projet par Permalink, 404 si pas trouvé
- 28. Comment trouver si l'image est cliquée dans JApplet?
- 29. Trouver un utilisateur amis et déterminer si elles ont l'application
- 30. Comment trouver si le fichier est un fichier CSV?
Question équivalente pour PHP: http://stackoverflow.com/questions/2411636/is-there-an-easy-way-to-detect-line-segment-intersections – finnw