我需要找到Path2D是否相交。現在,我只需從路徑中提取一系列行,然後查找是否存在任何這些行相交。但它具有O(n^2)的複雜性,所以它非常慢。有沒有更快的方法來做到這一點?尋找Path2D自相交
10
A
回答
3
爲此,您可以更快地使用掃線算法:http://en.wikipedia.org/wiki/Sweep_line_algorithm
僞代碼:
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.
最壞的情況是仍然O(N^2)
,但平均情況O(NlogN)
+0
謝謝!但是對你的方法有一個改進 - 如果你在桶中保持「高於 - 低於」的順序(按行的第一個點y座標排序),你可以測試新行僅針對它上面和下面的行,這會給你O(記錄n)時間複雜度而不是O(n)。找到它:
3
這裏是我的該算法的Java實現:
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;
}
}
相關問題
- 1. 尋找對相交集的任意集
- 2. CGPath相交的尋找區域CGRect
- 3. 尋找交集
- 4. 檢查兩個Path2D之間的交集
- 5. 尋找git提交從
- 6. 創建一個變量與兩個.map()尋找匹配或相交兩個陣列。尋找匹配或交叉
- 7. 尋找popUpMenuPositioningItem:atLocation:inView:相當於10.5
- 8. 尋找相似的值
- 9. 尋找相當於scanf的
- 10. 尋找相當於xpath,Lxml
- 11. 查找相交
- 12. 動畫繪製Path2D
- 13. 如何剪輯Path2D?
- 14. Path2D繪製錯誤?
- 15. 尋找一個交互式決策樹
- 16. 尋找最後的交易,每個ID
- 17. 尋找REGEXP交換兩個字
- 18. 正在尋找相機自動對焦指示器示例
- 19. 關於尋找相同的文件對
- 20. 尋找相當於'onRender'的javascript事件
- 21. 尋找到CSV欄的值相同
- 22. 尋找相對位置加上形狀
- 23. 尋找類似相冊的推薦
- 24. 尋找相機之間的extrinsics
- 25. 安卓正在尋找相機
- 26. 尋找在相同的塊或陣列
- 27. 尋找k最相似的文件
- 28. GAWK - 尋找相應的動作
- 29. SQL查詢來尋找相關匹配
- 30. jquery - 尋找相同的內容
PHP的等效問題:http://stackoverflow.com/questions/2411636/is-there-an-easy-way-to-detect-line-segment-intersections – finnw 2010-12-20 12:51:38