使用Java計算多個2D形狀的交集

請注意我對使用任何第三方JAR或AWT作爲此解決方案的一部分不感興趣。我正在盡我所能地保持我的項目無依賴關係，我想保持這種狀態。而且，如果JRE提供了可以解決這個問題的任何類，我仍然對這裏的一個定製解決方案感興趣，這樣我就可以真正理解數學，而不是盲目地進行一些API調用。使用Java計算多個2D形狀的交集

我有各種形狀以下POJO結構：

public class Coordinate { 
    private Double xVal; 
    private Double yVal; 

    // Constructors, getters/setters, etc. 

    public static Double distance(Coordinate c1, Coordinate c2) { 
     // Calculates the Cartesian distance between c1 and c2 using the standard 
     // distance formula. 
    } 
} 

public abstract class Shape { 
    // Some properties inherent to all 2D shapes. 

    public abstract Double calcArea(); 
    public abstract Double calcPerimeter(); 
} 

public class Rectangle extends Shape { 
    private Coordinate upperLeft; 
    private Coordinate upperRight; 
    private Coordinate lowerLeft; 
    private Coordinate lowerRight; 

    // Constructors, overrides, getters/setters, etc. 
} 

public class Circle extends Shape { 
    private Coordinate center; 
    private Double radius; 

    // Constructors, overrides, getters/setters, etc. 
}

那麼現在，我將給出一個List<Shape>（含有0+ Rectangle S和0+ Circle S混合集）。我需要確定是否有任何在此列表中的形狀相互（true或false）相交：

public boolean intersectionsExist(List<Shape> shapes) { 
    // ??? 
}

我想在這裏實施的最佳實踐，所以我不知道是否有任何已算法來做到這一點（可能）幾十個形狀。我在SO和網上找到的所有「交集檢測」代碼片段都在兩種形狀之間。但是如果我在列表中有3個矩形和7個圓圈怎麼辦？！？

我的想法是，通過列表中的每個Shape迭代，並與所有其他Shape（因此一個二次解決方案，我不激動不已）進行比較。但這樣，我可以返回true我立即找到與另一個相交的Shape。

至於檢測實際的交叉點，我想知道是否有什麼我可以做，把這些形狀像維恩圖。意思是，以某種方式確定是否一個形狀是重疊另一個。但至於我如何確定「重疊」，我不知道。

那麼幾個問題：

是否有任何標準算法在那裏爲3+形狀中檢測交點？如果是這樣，有人可以給我一些鏈接/信息對他們？
如果上面＃1的答案是「否」，那麼我的二次解決方案是否是最佳方法之一（雙嵌套for-將每個Shape彼此進行比較並在發現一個交叉點時返回true）？還是有更好/更有效的方法？
最重要的是：如何檢測實際的交叉點？有沒有標準的算法來完成這個（鏈接？）？有人可以提供一個代碼示例（使用上面的POJO），甚至可以提供一個簡單的僞代碼示例來說明我可以在這裏做什麼？

在此先感謝！

來源

2013-12-07 IAmYourFaja

1.不，您只能檢測2個形狀的交集。你的二次方案是最好的。如果您有10個對象，則少於100個相交測試。您不測試形狀A與形狀A的交集。3.使用形狀的交集（和包含）方法。 Shape是一個接口，因此Shape將選擇要使用的具體相交（和包含）方法。 –

謝謝@GilbertLeBlanc（+1） - 什麼庫是「形狀」的一部分？你能提供一個鏈接到它的Javadoc？一旦我知道在哪裏可以找到源代碼，我會仔細分析一下，看看能否找到真正的「相交」算法。再次感謝！ – IAmYourFaja

http://docs.oracle.com/javase/7/docs/api/java/awt/Shape.html –

碰撞檢測有多種解決方案。與現代遊戲及其成千上萬的模型一樣，您可以處理大量對象中的檢測，但您只是一次比較兩個項目的碰撞

最快和最簡單的代碼選項是使用包含你的對象的圓圈（如果你的對象是圓形的話很容易）並且使用距離測試。如果兩個圓的中心點之間的距離小於它們的組合半徑，則它們正在碰撞。

此選項有一些缺點，例如矩形對象上的圓將在未繪製矩形的某些區域發生碰撞（如果該圓大於矩形）或在某些時候不會碰撞應該（如果圓小於矩形）。

你可以看到的其他一些東西是軸對齊邊界框或n-DOP碰撞，這兩者在數學上都比較密集。這裏有一個很好的general collisions tutorial

如果你想獲得極其複雜和mathy，這裏是被稱爲SAT的方法（分離軸定理）http://www.metanetsoftware.com/technique/tutorialA.html

來源

2013-12-07 21:20:43 Coder101101010

謝謝@ Coder101101010（+1） - 請在A.H.的答案下看到我的評論 - 我對你有同樣的問題！再次感謝！ – IAmYourFaja

有幾個在那裏。當它歸結爲代碼時，它是一個非常簡單的數學庫，所以很多人剛剛創建了簡單的自定義庫，它們免費贈送。這是一個[很好的例子]（http://ganeshtiwaridotcomdotnp.blogspot.com/2011/12/java-collision-detection-complete.html）和[這個sourceforge項目]（http://sourceforge.net/projects/ jgame-engine /），它是2D的整個遊戲引擎。 – Coder101101010

謝謝@ Code101101010（+1再次） - 不幸的是我可能需要檢測2 **矩形**之間的交集，在這種情況下，這些「泡沫」算法將無法工作。你知道任何Java庫可以執行這種檢測（2個矩形之間）嗎？ – IAmYourFaja

您的問題通常被稱爲Constructive Solid Geometry。查閱維基百科和/或有關計算機圖形學的標準書籍，但請不要期望將有關這些複雜內容的代碼作爲即時可用的答案。

來源

2013-12-07 21:17:44

謝謝@ A.H。（+1） - 好吧，我沒想到它會變得複雜！在那種情況下，你可以推薦哪些開源Java庫來實現所有這些東西？如果我能得到他們的源代碼，我想要通過它。再次感謝！ – IAmYourFaja

-1

如果你有興趣在交叉口的理論，有一個分析在普林斯頓Chazelle和Dobkin的一篇論文中的問題^†。這篇文章在這裏總結時間太長，但它提供了一個冗長的逐步算法和證明。您仍然需要自己編寫算法。然而，OP did要求鏈接和/或引用。

^{^† Chazelle，B.和Daniel P. Dobkin。 Intersection of Convex Objects in Two and Three Dimensions。普林斯頓，新澤西州：普林斯頓U，計算機科學系，1986年。}

來源

2015-10-15 19:04:34

將人員發送到其他地方的pdf並不是那麼有用。 – Teepeemm

爲了公平起見，OP做了「是否有任何標準算法用於檢測3個以上形狀之間的交叉點？如果有，有人可以給我一些鏈接/信息嗎？」所以也許這是一個糟糕的問題，而不僅僅是答案。 – shoover

使用Java計算多個2D形狀的交集

回答

相關問題