List of operations without ForLoops

Question

I have a class with the following members:

• X
• Y
• Width
• Height

You can create a rectangle with these options.

Now my problem is that I have a list of this class, List<MyClass> .

I need to compare each object of the list with all other objects in such a way that if currentObject.Location(X, Y) falls into the rectangle(X, Y, Width, Height) another object, I need to remove another object from the list.

I implemented it using loops.

But the main problem: performance. My list of minimum lists is 300,000.

Is there any procedure to improve performance for this task on any version of .NET, including LINQ?

`public class RectBase {private int _rectId; private PointF _rectLocation; private SizeF _rectSize;

  public RectBase() { _rectId = -911; _rectLocation = new PointF(0, 0); _rectSize = new SizeF(0, 0); } public RectBase(int id, PointF loc, SizeF size) { _rectId = id; _rectLocation = loc; _rectSize = size; } public bool IsIntersected(RectBase otherRectObject) { RectangleF currentRect = new RectangleF(_rectLocation, _rectSize); if (currentRect.Contains(otherRectObject.RectLocation)) return true; else return false; } public int RectId { get { return _rectId; } set { _rectId = value; } } public PointF RectLocation { get { return _rectLocation; } set { _rectLocation = value; } } public SizeF RectSize { get { return _rectSize; } set { _rectSize = value; } } } public class RectProcessor { List<RectBase> _rectList; int maxCount = 300000; public RectProcessor() { _rectList = new List<RectBase>(); FillList(); } private void FillList() { // Adding the items to the list with dummy values for (int i = 0; i < maxCount; i++) { int id = i+1; PointF loc = new PointF(id, id); SizeF sz = new SizeF(id, id); RectBase obj = new RectBase(id, loc, sz); _rectList.Add(obj); } } private void RemoveIntersectedObjects() { List<RectBase> filteredList = new List<RectBase>(); bool isIntersected = false; for (int i = 0; i < maxCount; i++) { for (int j = 0; j < maxCount; j++) { if (_rectList[i].IsIntersected(_rectList[j])) { isIntersected = true; break; } } if (!isIntersected) { filteredList.Add(_rectList[i]); } isIntersected = false; } } } 

`

Answer 1

The problem does not fix the for loops, at least the way you think about it. Rewriting this in LINQ will simply hide the for loops, but they will still be there. And this is the main problem. Your algorithm, as it is written, is O(n^2) , and why you see a funny explosion in time when you go from 20,000 elements to 300,000 elements. In the first case, you make 400,000,000 comparisons, and in the second case, 90,000,000,000, and it will continue to grow as O(n^2) .

So, the question you really want to ask is this: is there an algorithm with time complexity better than O(n^2) for this problem?

Honestly, I do not know the answer to this question. I suspect the answer is no: you cannot know if a point is contained in any rectangle without comparing it with all the rectangles, and you need to check all the points. But maybe there is a smart way to do this, for example, to calculate the convex hull of all the rectangles and use it somehow?

This problem is an example of a computational geometry field.