7

How can I devise an R-code that can derive a rectangular bounding box (with 90-degree angle on each corner) for a set of points with arbitrary orientation? e.g. if the 2 longer edges have a 45-degree angular direction, or 15-degree, or any angle. It seems to have been solved on the paper below, but I cannot read their mathematical notation.

http://www.cccg.ca/proceedings/2004/29.pdf

It is partially solved on the link below, however, it looks only for the "minimum area rectangle" and not the minimum bounding rectangle for a specified orientation.

Finding minimum-area-rectangle for given points?

BERA
  • 72,339
  • 13
  • 72
  • 161
Jun Folledo
  • 341
  • 2
  • 14
  • 1
    Maybe this will help? https://stackoverflow.com/questions/41833933/how-to-create-minimum-bounding-rectangle-over-complete-dataset-in-r – GBG Oct 17 '17 at 16:56
  • No, the orientation of the bounding box on that thread is always vertical/horizontal, it means its pair of parallel sides are always 90 degrees and 0 degrees respectively. My question is, find the smallest bounding box if the orientation of one of the parallel sides is say 45 degrees, 10 degrees, etc. Thanks for your response. – Jun Folledo Oct 17 '17 at 23:43
  • do you mean minimum oriented bounding box? QGIS has an implementation but that doesn't answer the implementation in R... but it might clarify / be a starting point? – Steven Kay Oct 18 '17 at 19:06
  • @Steven Kay, I think this is what I am looking for, but I'm not familiar in Python coding in QGIS, but I'm willing to study it if needed. Can you please illustrate how to implement it? I suggest that you post your answer, but not in the comment section so you can earn the bounty. Thank you very much! – Jun Folledo Oct 18 '17 at 22:25
  • I see that the code is in C++, how do we run it in QGIS? – Jun Folledo Oct 18 '17 at 23:13
  • 2
    The solution is already provided by @whuber in https://gis.stackexchange.com/questions/22895/finding-minimum-area-rectangle-for-given-points/181883#181883 The rectangle is being rotated, isnt that what you want?? – BERA Oct 19 '17 at 09:21
  • @BERA Thanks, I wondered how the algorithm works! That link takes me to a deleted answer for some reason, it's a duplicate of this question. I've withdrawn my answer, the answers over there should answer the original question far better. – Steven Kay Oct 19 '17 at 20:04
  • Bera, my original question has a link to that post, unfortunately, it's not what I need since it simply gives the smallest bounding box but we cannot control the orientation/direction/angle of the box. In fact, I asked this same question on that post, but Kersten suggestion that I should open a new post for my follow up question. The orientedMinimumBoundingBox shared by Stephen Kay is almost perfect except that I need to understand how to implement it, preferably in R or QGIS. Thanks for your help. – Jun Folledo Oct 19 '17 at 23:49
  • Hi @StevenKay, it is not a duplicate question, the last reply on that post is mine asking this same question, but Kersten suggestion that I should post a new question. Thanks for your help. – Jun Folledo Oct 20 '17 at 04:38

2 Answers2

5

I guess you need Principal Component Analysis (PCA), read this publication:

On the Bounding Boxes Obtained by Principal Component Analysis

Look at this as well:

https://www.rdocumentation.org/packages/shotGroups/versions/0.1/topics/getMinBBox

pnz1337
  • 1,565
  • 1
  • 13
  • 25
  • I'm not merely looking for the minimum bounding box, I need a solution wherein I can specify first the orientation of the bounding box, then get the minimum bounding. If I cannot control the orientation of the bounding box, then it won't answer my query here. Thanks for your help though. – Jun Folledo Oct 21 '17 at 00:22
  • Then rotate (constrain: alpha parameter) the points with a rotation matrix. Use the usual boundary box: https://www.rdocumentation.org/packages/spatstat/versions/1.6-1/topics/bounding.box And rotate back the box.

    Or, simpler:

    1. Rotate the points.
    2. Create corners of boundary box (4 points) with the combinations of xmin, xmax, ymin, ymax.
    3. Rotate back the corner points, and create the box with convexhull for example.
     – pnz1337 Oct 21 '17 at 11:22
  • I also thought about that before but rotating the points back and forth would be cumbersome when iterated on thousands of data. The orientedMinimumBounding shared by @Steven Kay may do the trick only if I am able to implement it – Jun Folledo Oct 22 '17 at 08:00
  • You needed an R solution:

    orientedMinimumBoundingBox (QGIS) Returns the oriented minimum bounding box for the geometry, which is the smallest (by area) rotated rectangle which fully encompasses the geometry.

    getMinBBox (R) Calculates the vertices of the minimum-area, possibly oriented bounding box given a set of 2D-coordinates.

    • They are the same.
    • Look at my 2. link, that's the answer for you question.
     – pnz1337 Oct 22 '17 at 10:59
  • Both algorithm return the same properties by the way: angle, width, height – pnz1337 Oct 22 '17 at 11:20
  • Yes, but I need to be able to specify the angle, then it will give me the bounding box. – Jun Folledo Oct 22 '17 at 23:12
  • I think there is a bit of confusion here. If you are wanting to specify the orientation of the bounding box then @pnz 's comment about rotating the points would be pretty simple to implement. But I think people are assuming you want to find the angle that has the minimum bounding box as per the paper you linked, in which case it is confusing why you would specify the angle first? – Liam G Oct 24 '17 at 01:56
  • at this point, the question is now clear and i think is no longer confusing, but as to "why I need to specify the angle first before deriving the smallest bounding box" is another lengthy discussion which may further confuse the readers. – Jun Folledo Oct 24 '17 at 19:02
  • and yes, i may have no choice but to rotate the points to a desired angle, then derive the smallest vertical bounding box, and finally rotate back the points with the new bounding box. but it seems that there should be a more direct solution which i'm trying to figure out. thanks everyone for your contribution in the discussion – Jun Folledo Oct 24 '17 at 19:11
2

Then rotate (constrain: alpha parameter) the points with a rotation matrix.

Use the usual boundary box: https://www.rdocumentation.org/packages/spatstat/versions/1.6-1/topics/bounding.box

And rotate back the box.

Or, simpler:

  1. Rotate the points.
  2. Create corners of boundary box (4 points) with the combinations of xmin, xmax, ymin, ymax.
  3. Rotate back the corner points, and create the box with convexhull for example.
pnz1337
  • 1,565
  • 1
  • 13
  • 25