CODEWITHSUNDEEP
c#.net
Gary
Gary

Reputation: 33

Determining location of a Point3d on a grid with defined regions

I have a xy plane containing a series of alphabetically named non-overlapping rectangular regions defined by 2 corners each as Point3d's (z-dimension is immaterial here, they are outputted by api as point3ds).

How can I best find which region a random point3d lays within?

Also, how could I check to make sure the regions are infact not overlapping?

Thanks!

Upvotes: 0

Views: 54

Answers (1)

Rufus L
Rufus L

Reputation: 37020

Without code to represent your objects, it's a little difficult to answer, but here's an example using a Region struct that contains two Point properties (which I assume are similar to your Point3d classes except there's no Z, which you said is irrelevant).

First, I would include a property that represents the region as a Rectangle, since it has most of the functionality you already need. I would also include methods that tell you if a Region contains a Point, if one Region instance overlaps another Region, and a method that tells you if any Region in a list overlaps another in the list:

public struct Region
{
    public Point Corner1 { get; }

    public Point Corner2 { get; }

    public Rectangle Rectangle { get; }

    public Region(Point corner1, Point corner2)
    {
        Corner1 = corner1;
        Corner2 = corner2;
        var leftMost = Math.Min(Corner1.X, Corner2.X);
        var topMost = Math.Min(Corner1.Y, Corner2.Y);
        var width = Math.Abs(Corner1.X - Corner2.X);
        var height = Math.Abs(Corner1.Y - Corner2.Y);
        Rectangle = new Rectangle(leftMost, topMost, width, height);
    }

    public static bool AnyOverlap(List<Region> regions)
    {
        if (regions == null || regions.Count == 1) return false;

        for (int i = 0; i < regions.Count - 1; i++)
        {
            for (int j = i + 1; j < regions.Count; j++)
            {
                if (regions[i].Overlaps(regions[j]))
                {
                    return true;
                }
            }
        }

        return false;
    }

    public bool Contains(Point p)
    {
        return p.X >= Rectangle.Left && p.X <= Rectangle.Right &&
               p.Y >= Rectangle.Top && p.Y <= Rectangle.Bottom;
    }

    public bool Overlaps(Region other)
    {
        return Rectangle.Left < other.Rectangle.Right &&
               Rectangle.Right > other.Rectangle.Left &&
               Rectangle.Top > other.Rectangle.Bottom &&
               Rectangle.Bottom < other.Rectangle.Top;
    }

    public override bool Equals(object obj)
    {
        return obj is Region && Rectangle.Equals(((Region) obj).Rectangle);
    }

    public override int GetHashCode()
    {
        return Rectangle.GetHashCode();
    }
}

With this, if you have a List<Region> xyPlane, you can do:

Point randomPoint = new Point(20, 30);

bool anyRegionsOverlap = Region.AnyOverlap(xyPlane);
Region containsPoint = xyPlane.FirstOrDefault(region =>
    region.Contains(randomPoint));

Upvotes: 1

Related Questions