Poszukuję metody sprawdzającej, czy podany <thickness> zasłania choć w najmniejszym stopni inny <thickness>

0

Witam. Napisałem metodę, która dzieli <thickness> na 4 linie i następnie sprawdza, czy któraś z linii przecina się z liniami obszaru drugiego. Niestety obliczenie 90 takich elementów trwa już ponad 2 sekundy (elementów będzie ponad 200 i będą one wczytywane co 2 sekundy). Czy znacie może coś przydatnego?

0

przydałaby się graficzna wizualizacja, i póki co jak rozumiem liczysz przecięcie każdej linii z pozostałymi? co daje o(n^2) i jeśli to to o czym myślę to można zejść do O(n log n)
Przecinanie się zbioru odcinków

0

Czerwony - thickness A
Zielony - thickness B
screenshot-20200226080629.png

... narysowałem to sobie i teraz wiem! Po prostu policzę pole części wspólnej prostokątów i tyle ;) DZIĘKI!

4

Ale po co liczyć pole, skoro to są prostokąty, to sprawdzenie jest bardzo proste:

// Returns true if two rectangles (l1, r1) and (l2, r2) overlap 
bool doOverlap(Point l1, Point r1, Point l2, Point r2) 
{ 
    // If one rectangle is on left side of other 
    if (l1.x > r2.x || l2.x > r1.x) 
        return false; 
  
    // If one rectangle is above other 
    if (l1.y < r2.y || l2.y < r1.y) 
        return false; 
  
    return true; 
} 

dla n=90, sprawdzanie każdego z każdym powinno dać radę, dla większej ilości (n > 1000) jeśli prostokąty są w miarę równomiernie rozłożone polecam spatial hashing, w innym przypadku pozostają drzewa czwórkowe.

0

Neves próbowałem tak, ale sprawdzanie punktów okaże się błędne. Spójrz na rysunek w prawym dolnym rogu. Nie ma tam punktów pokrywających , a mimo to jeden prostokąt przykrywa drugi

3

kod który wkleiłem jest 100% poprawny i obsłuży wszystkie przypadki z rysunku, zapomniałem tylko wspomnieć że:
l1- lewy dolny wierzchołek prostokąta 1
r1 - prawy górny wierzchołek prostokąta 1
l2- lewy dolny wierzchołek prostokąta 2
r2 - prawy górny wierzchołek prostokąta 2

0

Chyba wiem już o co chodzi. Przetestuję to i dam znać, dziękuję Ci :)

1

@neves: Wszystko działa. Jest to trochę irytujące, bo to są zaledwie dwie linijki kodu
screenshot-20200226195038.png
Praktycznie 0 latencji dla ponad 150 elementów <3

Dla porównania mój kod (Proszę się nie śmiać)

AreaInArea

        /// <summary>
        /// Oblicza, czy podane obszary nie zasłaniają siebie wzajemnie
        /// </summary>
        /// <param name="Area1">Obszar 1</param>
        /// <param name="Area2">Obszar 2</param>
        /// <returns>Zwraca true, jeden z obszarów przykrywa drugi</returns>
        public static bool AreaInArea(Thickness Area1, Thickness Area2)
        {
            Point[] PointA = AreaConverters.ConvertAreaToPoints(Area1);
            Point[] PointB = AreaConverters.ConvertAreaToPoints(Area2);
            return (
                PolylineInArea(PointA[0], PointA[1], Area2) ||
                PolylineInArea(PointA[1], PointA[2], Area2) ||
                PolylineInArea(PointA[2], PointA[3], Area2) ||
                PolylineInArea(PointA[3], PointA[0], Area2) ||
            
                PolylineInArea(PointB[0], PointB[1], Area1) ||
                PolylineInArea(PointB[1], PointB[2], Area1) ||
                PolylineInArea(PointB[2], PointB[3], Area1) ||
                PolylineInArea(PointB[3], PointB[0], Area1) ||
            
                (Area2.Left >= Area1.Left && Area2.Right <= Area1.Right && Area2.Top >= Area1.Top && Area2.Bottom <= Area1.Bottom) ||
                (Area1.Left >= Area2.Left && Area1.Right <= Area2.Right && Area1.Top >= Area2.Top && Area1.Bottom <= Area2.Bottom)
            
                ) ? true : false;
        }

ConvertAreaToPoints

/// <summary>
        /// Konwertuje położenie prostokątne okna <see cref="Thickness"/> do punktów wierzchołków <see cref="Point"/> w układzie wpółrzędnych
        /// </summary>
        /// <param name="Area">Położenie okna</param>
        /// <returns></returns>
        public static Point[] ConvertAreaToPoints(Thickness Area)
        {
            return new Point[]
            {
                new Point(Area.Left, Area.Top),
                new Point(Area.Right, Area.Top),
                new Point(Area.Left, Area.Bottom),
                new Point(Area.Right, Area.Bottom)
            };
        }

PolylineInArea

public static bool PolylineInArea(Point P1, Point P2, Thickness Area)
        {
            Point[] AreaPoints = AreaConverters.ConvertAreaToPoints(Area);
            bool result = (
                MathConverters.IsLinesCrossed(P1, P2, AreaPoints[0], AreaPoints[1]) ||
                MathConverters.IsLinesCrossed(P1, P2, AreaPoints[1], AreaPoints[2]) ||
                MathConverters.IsLinesCrossed(P1, P2, AreaPoints[2], AreaPoints[3]) ||
                MathConverters.IsLinesCrossed(P1, P2, AreaPoints[0], AreaPoints[3])
                ) ? true : false;
            return result;
        }

IsLinesCrossed

public static bool IsLinesCrossed(Point A1, Point A2, Point B1, Point B2)
        {
            bool A_Poziome = (A1.Y == A2.Y) ? true : false;
            bool B_Poziome = (B1.Y == B2.Y) ? true : false;

            if(A_Poziome && B_Poziome)
                return (A1.Y != B1.Y) ? false : true; 
            if(!A_Poziome && !B_Poziome)
                return (A1.X != B1.X) ? false : true;

            if(A_Poziome)
            {
                if(A1.X < A2.X)
                {
                    if(B1.Y < B2.Y)
                    {
                        return (B1.X >= A1.X && B1.X <= A2.X && B1.Y <= A1.Y && B2.Y >= A1.Y) ? true : false;
                    }
                    else
                    {
                        return (B2.X >= A1.X && B2.X <= A2.X && B2.Y <= A1.Y && B1.Y >= A1.Y) ? true : false;
                    }
                }
                else
                {
                    if (B1.Y < B2.Y)
                    {
                        return (B1.X >= A2.X && B1.X <= A1.X && B1.Y <= A2.Y && B2.Y >= A2.Y) ? true : false;
                    }
                    else
                    {
                        return (B2.X >= A2.X && B2.X <= A1.X && B2.Y <= A2.Y && B1.Y >= A2.Y) ? true : false;
                    }
                }
            }
            if(B_Poziome)
            {
                if (B1.X < B2.X)
                {
                    if (A1.Y < A2.Y)
                    {
                        return (A1.X >= B1.X && A1.X <= B2.X && A1.Y <= B1.Y && A2.Y >= B1.Y) ? true : false;
                    }
                    else
                    {
                        return (A2.X >= B1.X && A2.X <= B2.X && A2.Y <= B1.Y && A1.Y >= B1.Y) ? true : false;
                    }
                }
                else
                {
                    if (A1.Y < A2.Y)
                    {
                        return (A1.X >= B2.X && A1.X <= B1.X && A1.Y <= B2.Y && A2.Y >= B2.Y) ? true : false;
                    }
                    else
                    {
                        return (A2.X >= B2.X && A2.X <= B1.X && A2.Y <= B2.Y && A1.Y >= B2.Y) ? true : false;
                    }
                }
            }

            return false;
        }

Tak, wiem. Minęło parę dni zanim zaczęło działać.

teraz to wygląda tak:

/// <summary>
        /// Oblicza, czy podane obszary nie zasłaniają siebie wzajemnie
        /// </summary>
        /// <param name="Area1">Obszar 1</param>
        /// <param name="Area2">Obszar 2</param>
        /// <returns>Zwraca true, jeden z obszarów przykrywa drugi</returns>
        public static bool AreaInArea(Thickness Area1, Thickness Area2)
        {
            Point l1 = new Point(Area1.Left, Area1.Bottom);
            Point r1 = new Point(Area1.Right, Area1.Top);
            Point l2 = new Point(Area2.Left, Area2.Bottom);
            Point r2 = new Point(Area2.Right, Area2.Top);
            // If one rectangle is on left side of other 
            if (l1.X > r2.X || l2.X > r1.X)
                return false;

            // If one rectangle is above other 
            if (l1.Y < r2.Y || l2.Y < r1.Y)
                return false;

            return true;
        }
        /// <summary>
        /// Oblicza, czy podany obszar nie zasłania innych obszarów lub odwrotnie
        /// </summary>
        /// <param name="Area1">Obszar 1</param>
        /// <param name="Area2">Obszary 2</param>
        /// <returns>Zwraca true, przynajmniej jeden obszar przykrywa podany region</returns>
        public static bool AreaInAreas(Thickness Area1, IEnumerable<Thickness> Area2)
        {
            foreach (Thickness a in Area2)
            {
                if (AreaInArea(Area1, a))
                    return true;
            }
            return false;
        }

Jestem Ci naprawdę, naprawdę wdzięczny :)))

0

ale to ładne (prostokąty)

1 użytkowników online, w tym zalogowanych: 0, gości: 1