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?
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
Czerwony - thickness A
Zielony - thickness B
... narysowałem to sobie i teraz wiem! Po prostu policzę pole części wspólnej prostokątów i tyle ;) DZIĘKI!
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.
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
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
Chyba wiem już o co chodzi. Przetestuję to i dam znać, dziękuję Ci :)
@neves: Wszystko działa. Jest to trochę irytujące, bo to są zaledwie dwie linijki kodu
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 :)))
ale to ładne (prostokąty)