List Operations without ForLoops

I have a class with the following members:

• X
• Y
• Width
• Height

One can create a rectangle with these parameters.

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

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

I implemented it with for loops.

But the major problem is: performance. My minimum list count is 300000.

Is there any procedure to improve the performance for this task uisng any of the .Net versions 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;
        }
    }
}

`

---

The problem isn't eliminating for loops, at least in the way that you're thinking of it. Rewriting this in LINQ is just going to hide the for loops but they'll still be there. And that's the fundamental problem. Your algorithm, as written, is O(n^2) and that's why you see a ridiculous explosion in time as you go from 20,000 elements to 300,000 elements. You're doing 400,000,000 comparisons in the first case, and 90,000,000,000 in the second case and it will continue to grow like O(n^2).

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

Frankly, I don't know the answer to that question. I suspect that the answer is no: you can't know if a point is contained in some rectangle without comparing it to all the rectangles, and you have to inspect all the points. But maybe there's a clever way to do it such as computing the convex hull of all the rectangles and use that somehow?

This problem is an example of the field of computational geometry.