Avatar of Bill-Hanson
Bill-HansonFlag for United States of America asked on

Oriented bounding rectangle for a line

I'm working on a flowchart application, and need to define the click-able region for a shape connector (line-segment).

To do this, I a need to generate the vertexes for an oriented rectangle that fully encloses an arbitrary line.  In addition, I need to be able to specify some padding (in pixels) such that the resulting rectangle will be slightly larger than the line.

The code below is the closest solution I have found, but the resulting rectangle does not include the padding at the end of the line, only at the sides.

The image below illustrates the difference between what the GetSegmentBounds function does and what I need it to do.

For reference, I found the code below here:  https://www.experts-exchange.com/Q_22951696.html#20261839
protected Point[] GetSegmentBounds(Point p1, Point p2, Double offset)
        {
            Point[] rect = new Point[4];
            Double len = Math.Sqrt((Double)((p1.X - p2.X) * (p1.X - p2.X) + (p1.Y - p2.Y) * (p1.Y - p2.Y)));// +(offset * 2);
            rect[0].X = (Int32)(p1.X - (p1.Y - p2.Y) * offset / len);
            rect[0].Y = (Int32)(p1.Y + (p1.X - p2.X) * offset / len);
            rect[1].X = (Int32)(p1.X + (p1.Y - p2.Y) * offset / len);
            rect[1].Y = (Int32)(p1.Y - (p1.X - p2.X) * offset / len);
            rect[2].X = (Int32)(p2.X + (p1.Y - p2.Y) * offset / len);
            rect[2].Y = (Int32)(p2.Y - (p1.X - p2.X) * offset / len);
            rect[3].X = (Int32)(p2.X - (p1.Y - p2.Y) * offset / len);
            rect[3].Y = (Int32)(p2.Y + (p1.X - p2.X) * offset / len);
            return rect;
        }

Open in new window

Rectangles.jpg
Game ProgrammingAlgorithmsMath / Science

Avatar of undefined
Last Comment
Bill-Hanson

8/22/2022 - Mon
d-glitch

Since you have a horizontal line, the term (p1.Y - p2.Y) is zero.
So you don't add any offset to the x coordinates.

You would have the same problem with a vertical line and the (p1.X - p2.X) term.

Your code would work for a line at 45 degrees.

Why can't you just add fixed offsets all around?
d-glitch

Arbitrary line segment:             (x1, y1)  (x2, y2)

Box enclosing the segment:     (x1, y1)  (x1, y2)  (x2, y2)  (x2, y1)

                                                 If x1 > x2, then dx= +3 else dx= -3
                                                 If y1 > y2, then dy= +3 else dy= -3

Padded box:                            (x1+dx, y1+dy)  (x1+dx, y2-dy)  (x2-dx, y2-dy)  (x2-dx, y1+dy)
ASKER
Bill-Hanson

Wouldn't that result in an axis-aligned bounding box?  I need an oriented bounding box.
Experts Exchange has (a) saved my job multiple times, (b) saved me hours, days, and even weeks of work, and often (c) makes me look like a superhero! This place is MAGIC!
Walt Forbes
ASKER CERTIFIED SOLUTION
ozo

Log in or sign up to see answer
Become an EE member today7-DAY FREE TRIAL
Members can start a 7-Day Free trial then enjoy unlimited access to the platform
Sign up - Free for 7 days
or
Learn why we charge membership fees
We get it - no one likes a content blocker. Take one extra minute and find out why we block content.
See how we're fighting big data
Not exactly the question you had in mind?
Sign up for an EE membership and get your own personalized solution. With an EE membership, you can ask unlimited troubleshooting, research, or opinion questions.
ask a question
ASKER
Bill-Hanson

Thanks ozo!  I wish I had more time to understand why this works, but as usual, I'm under the gun.
ASKER
Bill-Hanson

ozo,

Thanks again for the help, but I'm still having a little trouble with your algorithm.

The results I'm getting are very close, but not precise.  I tried some trial and error (mostly error), and I see some definite patterns in the algorithm, but I'd rather have someone who understands it take a closer look.

I've included my source and a few screen shots using different line orientations.

Thank you in advance for any help you can provide!
        protected override void OnPaint(PaintEventArgs e)
        {
            base.OnPaint(e);
            Point pt1 = new Point(50, 100);
            Point pt2 = new Point(100, 50);
            e.Graphics.DrawLine(new Pen(Color.White, 1), pt1, pt2);
            e.Graphics.DrawPolygon(new Pen(Color.Red, 1), GetSegmentBounds(pt1, pt2, 4));
        }
 
        protected Point[] GetSegmentBounds(Point p1, Point p2, Double offset)
        {
            Point[] rect = new Point[4];
            Double len = Math.Sqrt((Double)((p1.X - p2.X) * (p1.X - p2.X) + (p1.Y - p2.Y) * (p1.Y - p2.Y)));
            rect[0].X = (Int32)(p1.X - (p1.Y - p2.Y - p1.X + p2.X) * offset / len);
            rect[0].Y = (Int32)(p1.Y + (p1.X - p2.X + p1.Y - p2.Y) * offset / len);
            rect[1].X = (Int32)(p1.X + (p1.Y - p2.Y + p1.X - p2.X) * offset / len);
            rect[1].Y = (Int32)(p1.Y - (p1.X - p2.X - p2.Y + p2.Y) * offset / len);
            rect[2].X = (Int32)(p2.X + (p1.Y - p2.Y + p2.X - p1.X) * offset / len);
            rect[2].Y = (Int32)(p2.Y - (p1.X - p2.X - p2.Y + p1.Y) * offset / len);
            rect[3].X = (Int32)(p2.X - (p1.Y - p2.Y - p2.X + p1.X) * offset / len);
            rect[3].Y = (Int32)(p2.Y + (p1.X - p2.X + p2.Y - p1.Y) * offset / len);
            return rect;
        }

Open in new window

50-50to100-100.gif
50-100to50-50.gif
50-100to100-50.gif
50-50-50-100.gif