檢查一組點是否在矩形數組內？

我有一個頂點列表和一個區域列表（矩形/矩形）的形狀。頂點具有x和y座標，並且區域具有（x，y，高度和寬度）。我怎樣纔能有效地檢查哪個頂點位於每個頂點/區域的哪個區域？檢查一組點是否在矩形數組內？

編輯：

這是我寫的代碼來做到這一點。編輯2：我用它來生成區域，但我需要一種方法來從左到右分配網格中的每個區域regionID。例如：

1 - 2 - 3 
4 - 5 - 6 
7 - 8 - 9

對於3x3網格。目前，它是以下形式：

1 - 1 - 1 
2 - 2 - 2 
3 - 3 - 3 

       for (int i = 0; i < rowValue; i++) { 

       for (int j = 0; j < columnValue; j++) { 

        Grid r = new Grid(0, 20 + i * size, 20 + j * size, size, size); 
        r.setRegionID(j + 1); 
        g.addRegion(r); 
       } 

      }

來源

2012-08-05 RikudouSennin

檢查頂點是否在正方形或圓圈內可以在O（1）中完成。你可以用庫函數或初等數學來做到這一點。所以您可以創建的工作算法是O（#vertices * #regions）。您可以嘗試通過X軸和Y軸對頂點和區域進行排序來優化，並嘗試消除肯定返回false的檢查。但似乎在悲觀的情況下，你仍然會有O（#vertices * #regions）時間。

來源

2012-08-05 14:38:33 piotrek

我已經更新了原來的職位的源代碼。你能看到任何可以改進的地方嗎？ – RikudouSennin 2012-08-05 14:50:27

如果你的get（x）在O（1）中工作，那麼你的算法在O（#vertices * #regions）中工作。如果因此需要對列表（頂點，區域），那麼可以有O（#vertices * #regions）這樣的對，所以您的算法是最優的。如果你的結果更加緊湊，例如對於每個頂點至多1個區域，那麼更快的算法可能是可能的 – piotrek 2012-08-05 15:05:29

與平面幾何工作是非常容易的，而使用JTS。您可以嘗試將您正在使用的對象轉換爲特定於JTS的對象。

來源

2012-08-05 14:34:33

你或許可以使用Core Java庫本身：

List<Rectangle2D.Double> rectangles = Arrays.asList(
               new Rectangle2D.Double(0d, 0d, 100d, 100d), 
               new Rectangle2D.Double(100d, 0d, 100d, 100d), 
               new Rectangle2D.Double(0d, 100d, 100d, 100d), 
               new Rectangle2D.Double(100d, 100d, 100d, 100d)); 

    Point2D.Double aPoint = new Point2D.Double(30d, 40d); 

    for (Rectangle2D.Double rectangle:rectangles){ 
     if (rectangle.contains(aPoint)){ 
      System.out.println(rectangle + " has the point " + aPoint); 
     } 
    }

來源

2012-08-05 14:49:00

檢查一組點是否在矩形數組內？

回答

相關問題