鱼缸
CONTINUE
ABOUT
MSG
Lab
最新博客
search
5b5c2abe-796e-48e0-bffd-513e76156d75
不规则图形内的最大内接矩形计算
<p><b>背景:</b></p><p>游戏中的一块地图,其中圈出了一块作为相位区域(不规则多边形),凡是进入区域的角色将自动切进相位内,有两种解决方案,</p><p><u>A. </u>角色每移动一次位置就拿当前坐标 (x, y) 与不规则区域进行计算(计算量很大)是否在区域内</p><p><u>B. </u>提前缓存区域内所有坐标点,角色每移动一次拿当前坐标与缓存坐标匹配</p><p><br></p><p>A方案计算量太大,因为角色每次移动都得计算一次;</p><p>B方案几乎没有计算量,但是需要占用内存太大,因为地图不止一张,每张地图上圈出的区域不止一个</p><p><br></p><p>因此进行折中,在区域中求出最大内接矩形的位置(左上和右下点),缓存除此矩形之外的其他坐标点,</p><p>这样就内存大大减少,且使用最大矩形位置就可以过滤非常多的坐标点而不需要大量计算。<br></p><p><br></p><p><b>算法:</b></p><p>这和leetcode上的一道题就一模一样了<a href="https://leetcode.com/problems/maximal-rectangle/" target="_blank">https://leetcode.com/problems/maximal-rectangle/</a><br></p><p>只需在矩形面积最大时将最位置求出即可</p><p><br></p><p><u>代码如下</u></p><pre data-source-line="1" style="box-sizing: border-box; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace; font-size: 11.899999618530273px; margin-top: 0px; margin-bottom: 16px; font-style: normal; font-variant-caps: normal; font-weight: normal; font-stretch: normal; line-height: 1.45; word-wrap: normal; padding: 16px; overflow: auto; background-color: rgb(246, 248, 250); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px; caret-color: rgb(36, 41, 46); color: rgb(36, 41, 46); letter-spacing: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none;"> <code class="hljs" style="box-sizing: border-box; display: inline; overflow: visible; padding: 0px; color: rgb(51, 51, 51); background-color: transparent; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace, sans-serif; font-size: 11.899999618530273px; margin: 0px; border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px; word-break: normal; white-space: pre; border: 0px; line-height: inherit; word-wrap: normal; background-position: initial initial; background-repeat: initial initial;"><span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">struct</span> Area { <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">public</span> <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">int</span> Size; <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">public</span> <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">int</span> XMin; <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">public</span> <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">int</span> XMax; <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">public</span> <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">int</span> YMin; <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">public</span> <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">int</span> YMax; } <span class="hljs-function" style="box-sizing: border-box;"><span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">private</span> <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">static</span> Area <span class="hljs-title" style="box-sizing: border-box; color: rgb(153, 0, 0); font-weight: bold;">MaxRect</span>(<span class="hljs-params" style="box-sizing: border-box;"><span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">char</span>[][] matrix</span>) </span>{ Area max = <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">new</span> Area { Size = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">-1</span>, XMax = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">-1</span>, XMin = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">-1</span>, YMax = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">-1</span>, YMin = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">-1</span> }; <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">if</span> (matrix == <span class="hljs-literal" style="box-sizing: border-box; color: rgb(0, 128, 128);">null</span> || matrix.Length == <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">0</span> || matrix[<span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">0</span>].Length == <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">0</span>) <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">return</span> max; <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">int</span> cLen = matrix[<span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">0</span>].Length; <span class="hljs-comment" style="box-sizing: border-box; color: rgb(153, 153, 136); font-style: italic;"></span> <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">int</span> rLen = matrix.Length; <span class="hljs-comment" style="box-sizing: border-box; color: rgb(153, 153, 136); font-style: italic;"></span><span class="hljs-comment" style="box-sizing: border-box; color: rgb(153, 153, 136); font-style: italic;"></span> <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">int</span>[] h = <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">new</span> <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">int</span>[cLen + <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">1</span>]; h[cLen] = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">0</span>; <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">for</span> (<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">int</span> row = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">0</span>; row < rLen; row++) { Stack<<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">int</span>> s = <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">new</span> Stack<<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">int</span>>(); <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">for</span> (<span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">int</span> i = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">0</span>; i < cLen + <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">1</span>; i++) { <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">if</span> (i < cLen) <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">if</span> (matrix[row][i] == <span class="hljs-string" style="box-sizing: border-box; color: rgb(221, 17, 68);">'1'</span>) h[i] += <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">1</span>; <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">else</span> h[i] = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">0</span>; <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">if</span> (s.Count <= <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">0</span> || h[s.Peek()] <= h[i]) s.Push(i); <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">else</span> { <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">while</span> (s.Count > <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">0</span> && h[i] < h[s.Peek()]) { <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">int</span> top = s.Pop(); Area area = <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">new</span> Area <br></code> <code class="hljs" style="box-sizing: border-box; display: inline; overflow: visible; padding: 0px; color: rgb(51, 51, 51); background-color: transparent; font-family: SFMono-Regular, Consolas, "Liberation Mono", Menlo, Courier, monospace, sans-serif; font-size: 11.899999618530273px; margin: 0px; border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px; word-break: normal; white-space: pre; border: 0px; line-height: inherit; word-wrap: normal; background-position: initial initial; background-repeat: initial initial;">{ Size = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">-1</span>, XMax = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">-1</span>, XMin = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">-1</span>, YMax = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">-1</span>, YMin = <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">-1</span> }; <span class="hljs-comment" style="box-sizing: border-box; color: rgb(153, 153, 136); font-style: italic;">// <span class="zh-hans" style="box-sizing: border-box; font-family: "Microsoft YaHei", 微软雅黑, SimSun, sans-serif;">这一行是重点</span> <span class="zh-hans" style="box-sizing: border-box; font-family: "Microsoft YaHei", 微软雅黑, SimSun, sans-serif;">(高</span> * <span class="zh-hans" style="box-sizing: border-box; font-family: "Microsoft YaHei", 微软雅黑, SimSun, sans-serif;">宽)</span></span> area.Size = h[top] * (s.Count <= <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">0</span> ? i : (i - s.Peek() - <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">1</span>)); <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">if</span> (area.Size > max.Size) { <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">if</span> (s.Count == <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">0</span>) { area.XMax = i - <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">1</span>; area.XMin = i - area.Size / h[top]; area.YMax = row; area.YMin = row - h[top] + <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">1</span>; } <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">else</span> { area.XMin = s.Peek() + <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">1</span>; area.XMax = area.Size / h[top] + area.XMin - <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">1</span>; area.YMax = row; area.YMin = row - h[top] + <span class="hljs-number" style="box-sizing: border-box; color: rgb(0, 128, 128);">1</span>; } max = area; } } s.Push(i); } } } <span class="hljs-keyword" style="box-sizing: border-box; color: rgb(51, 51, 51); font-weight: bold;">return</span> max; }</code></pre><p>核心算法其实为求柱状图的最大矩形面积,难理解的地方为最大面积更新时的坐标点的计算,</p><p>其中栈中存的是递增数列的下标,<br></p><p>分为两种情况:</p><p>A 当栈为空时,矩形的X最大值一定是当前遍历到的下标</p><p>B 当栈不空时,矩形的X最小值一定时当前栈顶,即递增数列的某个下标</p><p>嗯,只可意会不可文传啊<br></p>
2018/11/14 下午11:32:59
发放的说法
103.37.140.39
发放的说法
103.37.140.39
沙发已备好!
提交
关闭