Как вычислить пространственные отношения из ограничивающих прямоугольников?

Question

Предположим, что у меня есть изображение с фигурами в нем. Пользователь может выбрать 2 из них, нарисуя ограничительную рамку вокруг фигуры. То, что я хотел бы сделать, - вычислить различные пространственные отношения между этими двумя ограничивающими прямоугольниками (так что два прямоугольника), например: горизонтальный, вертикальный, диагональный, ближний, дальний, перекрывающий, содержит и т. Д.

Я должен это сделать в java.

Я уже знаю существования этой библиотеки: http://www.vividsolutions.com/jts/JTSHome.htm

Но я не уверен, что это может помочь мне с отношениями, такие как горизонтальные, вертикальные, диагональные, ближнего и дальнего. Возможно, это может помочь с перекрытием и содержит.

То, что я хочу спросить, если есть какая-то теория знать, чтобы решить эту проблему, прежде чем начать кодирование какой-то специальной реализации (конечно, у меня есть идеи о том, как реализовать, что отношения, но, возможно, есть то, что я должен знать).

Answer 1

Что вам нужно, так это определить пересечения и расстояния между ограничивающими прямоугольниками. Предполагая, что вы имеете ориентированные по оси ограничивающие прямоугольники (AABB, то есть прямоугольники прямоугольника прямоугольника, параллельные осям), вы можете уменьшить двумерные вычисления до 1D интервальных отношений - вычислить отношения между x и y интервалами отдельно и объединить их. Эта стратегия разделения и завоевания должна значительно упростить логику.

Это класс, который вы можете использовать в качестве отправной точки. Он довольно непроверен и не должен использоваться для производственного кода. Я знаю, что он не работает для особых случаев, таких как пустые интервалы (min> max) или одноэлементный интервал (min == max) -, но он должен помочь вам получить на вашем пути.

package stackoverflow; 

public enum IntervalRelation 
{ 
    LEFT, 
    LEFT_TOUCHING, 
    OVERLAP_LEFT, 
    CONTAINING, 
    CONTAINED, 
    OVERLAP_RIGHT, 
    RIGHT_TOUCHING, 
    RIGHT; 

    public static double getIntervalDistance(
      double min1, double max1, 
      double min2, double max2) { 
     double maxOfMin = Math.max(min1, min2); 
     double minOfMax = Math.min(max1, max2); 

     return maxOfMin - minOfMax; 
    } 

    public static IntervalRelation between(
      double min1, double max1, 
      double min2, double max2) { 
     double dist = getIntervalDistance(min1, max1, min2, max2); 

     if (dist > 0) { 
      // not touching or intersecting 
      return min1 < min2? LEFT : RIGHT; 
     } else if (dist == 0) { 
      // touching 
      return min1 < min2? LEFT_TOUCHING : RIGHT_TOUCHING; 
     } else { 
      // overlapping or containment 
      if (min1 < min2) { 
       // overlap left or containing 
       return max1 < max2? OVERLAP_LEFT : CONTAINING; 
      } else { 
       return max1 < max2? CONTAINED : OVERLAP_RIGHT; 
      } 
     } 

    } 
    public static void main(String[] args) { 
     System.out.println(between(0.0,+1.0, -2.0,-1.0)); 
     System.out.println(between(0.0,+1.0, +2.0,+3.0)); 
     System.out.println(between(0.0,+1.0, -2.0,+0.0)); 
     System.out.println(between(0.0,+1.0, +1.0,+3.0)); 
     System.out.println(between(0.0,+1.0, +0.5,+1.5)); 
     System.out.println(between(0.0,+1.0, -0.5,+0.5)); 
     System.out.println(between(0.0,+1.0, -0.5,+1.5)); 
     System.out.println(between(0.0,+1.0, +0.5,+0.6)); 
    } 
} 

В общем, я нашел, что это очень полезно предоставить Interval классы вместо всегда приходится обеспечивать мин/макс пар аргументов и того, чтобы проверить на пустоту или singletonness.