포인트 배열이 사각형 배열 안에 있는지 확인하십시오.

Question

저는 정점 목록과 사각형 목록 인 정사각형/직사각형 목록을 가지고 있습니다. 정점에는 x와 y 좌표가 있고 영역에는 (x, y, 높이와 너비)가 있습니다. 모든 정점/영역에 대해 어느 정점이 어느 정점에 있는지를 효율적으로 확인할 수있는 방법은 무엇입니까?

편집 :

이것은 내가 작성한 코드입니다.

   if (!g.getVertices().isEmpty()) { 

       for (int i = 0; i < g.getVertices().size(); i++) { 

        Vertex v = g.getVertices().get(i); 
        Point vertexPoint = new Point(v.getX(), v.getY()); 

        for (int j = 0; j < g.getNumberOfRegions(); j++) { 

         int x = g.getRegions().get(j).getX(); 
         int y = g.getRegions().get(j).getY(); 
         int height = g.getRegions().get(j).getHeight(); 
         int width = g.getRegions().get(j).getWidth(); 

         Grid regionGrid = new Grid(j+1, x, y, height, width); 

         Rectangle regionRectangle = new Rectangle(x, y, height, width); 
         if (regionRectangle.contains(vertexPoint)) { 
          System.out.println("Vertex " + v + " lies inside region " + regionGrid.getRegionID()); 
         } 
        } 

       } 
      } 

편집 2 : 나는 영역을 생성하기 위해 사용,하지만 난 왼쪽에서 오른쪽으로 그리드 regionID에서 각 지역을 할당하는 방법이 필요합니다. 예 :

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

(3x3 격자) 순간 그 형식은 다음과 같습니다 JTS를 사용하는 동안 평면 구조 작업

이

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); 
       } 

      } 

Answer 1

정점이 정사각형 안에 있는지 또는 O (1)에서 원이 수행되는지를 검사. 당신은 라이브러리 함수 나 초등 수학으로 할 수 있습니다. 그래서 만들 수있는 작품 알고리즘은 O (#vertices * #regions)입니다. X 축과 Y 축으로 정점과 영역을 정렬하여 최적화하려고 시도하고 확실하게 false를 반환하는지 확인하지 않으려 고 시도 할 수 있습니다. 그러나 비관적 인 시나리오에서는 여전히 O (#vertices * #regions) 시간이 걸릴 것으로 보입니다.

Answer 2

매우 쉽습니다. 사용중인 오브젝트를 JTS 전용으로 변환 해 볼 수 있습니다.

Answer 3

당신은 아마 자신으로 라이브러리 코어 자바를 사용할 수 있습니다 : 나는 소스 코드와 함께 원래의 게시물을 업데이트 한

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); 
     } 
    }