Подсчет пересечений прямоугольников

Question

Необходимо подсчитать сколько раз каждый прямоугольник пересекается с другими введенными прямоугольниками. На вход даются координаты диагоналей каждого прямоугольника. Проблема в функции, перепробовал много разных и ни одна правильно не работает. В чем проблема?

package main

import (
    "fmt"
    "math"
)

type Rect struct {
    x, x1, y, y1 float64
}

func intersects(a, b Rect) bool {
    return a.y < b.y1 || a.y1 > b.y || a.x1 < b.x || a.x > b.x1
}

func main() {
    var n int
    var rects = map[int]Rect{}
    fmt.Scan(&n)
    for i := 0; i < n; i++ {
        var r Rect
        fmt.Scan(&r.x, &r.x1, &r.y, &r.y1)
        rects[i] = r
    }
    for i := 0; i < n; i++ {
        count := 0
        for j := 1; j < n; j++ {
            if intersects(rects[i], rects[j]) {
                count++
            }
        }
        fmt.Print(count)
    }
}

Answer 1

По сути, все прямоугольники ориентированы вдоль осей X и Y?

Функция

func intersects(a, b Rect) bool {
    return a.y < b.y1 || a.y1 > b.y || a.x1 < b.x || a.x > b.x1
}

неверна. Можно, например, просто посчитать пересечение и убедиться, что таковое существует (код на С++, с Go, боюсь, не справлюсь :))

bool inter1( rect a, rect b)
{
    float x = max(a.x,b.x);
    float y = max(a.y,b.y);
    float x1 = min(a.x1,b.x1);
    float y1 = min(a.y1,b.y1);
    return (x < x1) && (y < y1);
}

Ваша формула ничего не дает. Посмотрите на иллюстрацию внизу. Если считать, что она работает верно — то в первом примере она дает ответ true - очевидно неверный. Если считать, что она дает ответ обратный, т.е. говорит о том, что треугольники НЕ пересекаются... тогда смотрим второй контрпример, где для пересекающихся прямоугольников она возвращает false...

Проверить мою формулу с вычислением пересечения можете самостоятельно.

Да, написанная мною формула требует, чтобы первые координаты были левым нижним углом, вторые — правым верхним. Имеет смысл добавить соответствующую проверку входных данных.

P.S. Да, и еще — вам надо для каждого смотреть пересечения со всеми, кроме себя:

 for i := 0; i < n; i++ {
    count := 0
    for j := 0; j < n; j++ {
        if i != j && intersects(rects[i], rects[j]) {
            count++
        }
    }

БЛОГ НА HUSL

Подсчет пересечений прямоугольников

Ответы (1 шт):