5

I want to find minimal enclosing rectangle for set of n points. First I found convex hull. If I have a convex hull from set of points ( I got it by doing Graham scan) stored as a sorted list. And from every edge of that convex hull, by binary search I found the point with the most distance. Now having that one edge and point with max distance, how can I find the rest of 2 points so I could make a rectangle. I know that at least two points of extremes of that convex hull must be on minimal enclosing rectangle (Xmin, Xmax, Ymin, Ymax). How can I use that? Does one need to be on edge of polygon and is there any way to do it like this? Reason I am doing this way is that I need O(nlogn) time complexity. Every help is appreciated.

Example:

Example

In this example we have Xmin and Ymax on rectangle, but not Xmin or X max

EvilTak
  • 7,091
  • 27
  • 36
user940009
  • 53
  • 3
  • Is the rectangle horizontally/vertically aligned, or in a free direction? – Stef Jul 01 '21 at 14:52
  • @Stef It does not need to be paralel to x or y axis. It is free direction, but needs to have contain one of edges from convex hull in one of its edges – user940009 Jul 01 '21 at 14:55
  • 2
    Now I understand the question better. Once you have that one edge, you can project every other point onto the line, to figure out the two extreme points. See https://stackoverflow.com/questions/61341712/calculate-projected-point-location-x-y-on-given-line-startx-y-endx-y about how to project a point on a line in python. – Stef Jul 01 '21 at 15:01
  • @Stef yes, I can always do that. But to do that it will take me n^2 time, and I need to do it in nlogn (reason I made a binary search at the first place ). I figure it out, that must be some connection with extreme points of convex hull (it would take a constant time, and would be great). But I just can't figure what is that – user940009 Jul 01 '21 at 15:12
  • 1
    Why will what @Stef proposed take `O(n^2)` time? All you have to do is look at the signed projected distance along the edge from each point on the convex hull to one of the points of the edge -- the two extreme points will then be the ones with the minimum and maximum signed projected distance. This should only take `O(n)` time, as you only need to iterate through the convex hull once. Note that this is done _after_ you have found your edge. – EvilTak Jul 01 '21 at 16:23
  • 2
    See also: the Wikipedia articles on [arbitrarily oriented bounding boxes](https://en.wikipedia.org/wiki/Minimum_bounding_box#Arbitrarily_oriented_minimum_bounding_box) and the [rotating calipers method](https://en.wikipedia.org/wiki/Rotating_calipers). – EvilTak Jul 01 '21 at 16:23
  • @EvilTak and thanks a lot! I think I get it how. If you could write this as an answer, it would be great, so I can accept it. Just to stay for others if anyone else stuck at this they could see answer – user940009 Jul 01 '21 at 16:53
  • see [2D OBB](https://stackoverflow.com/a/42997918/2521214) – Spektre Jul 02 '21 at 07:49

0 Answers0