我正在尋找一種有效的方法來找到凸多邊形的最小面積矩形。
運行時間應該是 O(n)，其中 n 是頂點數。
找到一般多邊形的邊界框有一個復雜的演算法，但是對于凸多邊形應該有一個更簡單的演算法。
對于凸多邊形，如何輕松做到這一點？
謝謝。
uj5u.com熱心網友回復：
旋轉卡尺是您最好的朋友。
最緊密的邊界矩形是它的一個邊與多邊形的一個邊重合。所以，
從任意邊開始，旋轉多邊形以使該邊水平，在底部；
找到分別最大化 Y、-X 和 X 的三個頂點。這樣，您就獲得了一個邊界框；
然后順時針移動到下一側，并調整旋轉；
通過更新最大值找到接下來的三個頂點（跟隨輪廓并在 Y 減小之前停止；與 -X 和 X 相同）；
對于每個位置，計算面積并保持最佳。轉一圈后停下。
重要的是要意識到您不會將旋轉應用于所有頂點，而是僅在需要時應用。要獲得初始邊界框，您需要處理 O(N) 個頂點，但 N-1 次更新僅需要 O(N) 個額外作業（已攤銷），并且您不必計算兩個坐標。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/422781.html
標籤：
最近新學習了下區塊鏈這方面的知識，所學不多，給大家分享下。 # 1. 關于web3j web3j是一個高度模塊化，反應性，型別安全的Java和Android庫，用于與智能合約配合并與以太坊網路上的客戶端（節點）集成。 # 2. 準備作業 jdk版本1.8 引入maven <dependency> < ......
uj5u.com 2020-09-10 03:03:06 more前言 部署智能合約有多種方式，命令列的瀏覽器的渠道都有，但往往跟我們程式員的風格不太相符，因為我們習慣了在IDE里寫了代碼然后打包運行看效果。 雖然現在IDE中已經存在了Solidity插件，可以撰寫智能合約，但是部署智能合約卻要另走他路，沒辦法進行一個快捷的部署與測驗。 如果團隊管理的區塊節點多、 ......
uj5u.com 2020-09-10 03:03:12 more前言 谷歌身份驗證器，前些年大家都比較陌生，但隨著國內互聯網安全的加強，它越來越多地出現在大家的視野中。 比較廣泛接觸的人群是國際3A游戲愛好者，游戲盜號現象嚴重+國外賬號安全應用廣泛，這類游戲一般都會要求用戶系結名為“兩步驗證”、“雙重驗證”等，平臺一般都推薦用谷歌身份驗證器。 后來區塊鏈業務風靡 ......
uj5u.com 2020-09-10 03:03:17 more目錄 ##1.1 ASCII編碼 ASCII（American Standard Code for Information Interchange，美國資訊交換標準代碼）是基于拉丁字母的一套電腦編碼系統，主要用于顯示現代英語和其他西歐語言。它是現今最通用的單位元組編碼系統，并等同于國際標準ISO/IE ......
uj5u.com 2020-09-10 03:04:50 moreNTP時鐘服務器的特點（京準電子） NTP時鐘服務器的特點（京準電子） 京準電子官V——ahjzsz 首先對時間同步進行了背景介紹，然后討論了不同的時間同步網路技術，最后指出了建立全球或區域時間同步網存在的問題。 一、概 述 在通信領域，“同步”概念是指頻率的同步，即網路各個節點的時鐘頻率和相位同步 ......
uj5u.com 2020-09-10 03:05:47 more標準化考場時鐘同步系統推進智能化校園建設 標準化考場時鐘同步系統推進智能化校園建設 安徽京準電子科技官微——ahjzsz 一、背景概述隨著教育事業的快速發展，學校建設如雨后春筍，隨之而來的學校教育、管理、安全方面的問題成了學校管理人員面臨的最大的挑戰，這些問題同時也是學生家長所擔心的。為了讓學生有更 ......
uj5u.com 2020-09-10 03:05:51 more北斗對時服務器（北斗對時設備）電力系統應用 北斗對時服務器（北斗對時設備）電力系統應用 京準電子科技官微（ahjzsz） 中國北斗衛星導航系統（英文名稱：BeiDou Navigation Satellite System，簡稱BDS），因為是目前世界范圍內唯一可以大面積提供免費定位服務的系統，所以 ......
uj5u.com 2020-09-10 03:06:20 moreMetamask錢包是一種基于區塊鏈技術的數字貨幣錢包，它允許用戶在安全、便捷的環境下管理自己的加密資產。Metamask錢包是以太坊生態系統中最流行的錢包之一，它具有易于使用、安全性高和功能強大等優點。 本文將詳細介紹Metamask錢包的功能和使用方法。 一、 Metamask錢包的功能 數字資 ......
uj5u.com 2023-04-20 08:46:47 more在上個實驗中，我們已經實作了簡單智能合約實作及客戶端開發，但該實驗中智能合約只有基礎的增刪改查功能，且其中的資料管理功能與傳統 MySQL 比相差甚遠。本文將在前面實驗的基礎上，將 Hyperledger Fabric 的默認資料庫支持 LevelDB 改為 CouchDB 模式，以實作更復雜的資料... ......
uj5u.com 2023-04-16 07:28:31 moreGet Started NuGet You can run the following command to install the Tron.Wallet.Net in your project. PM> Install-Package Tron.Wallet.Net 配置 public reco ......
uj5u.com 2023-04-14 08:08:00 more概述： 2023 年 2 月 8 日，針對 DKP 協議的閃電貸攻擊導致該協議的用戶損失了 8 萬美元，因為 execute() 函式取決于 USDT-DKP 對中兩種代幣的余額比率。 智能合約黑客概述： 攻擊者的交易：0x0c850f，0x2d31 攻擊者地址：0xF38 利用合同：0xf34ad ......
uj5u.com 2023-04-07 07:46:09 more// SPDX-License-Identifier: GPL-3.0 pragma solidity >=0.7.0 <0.9.0; import "hardhat/console.sol"; //ERC20 同質化代幣，每個代幣的本質或性質都是相同 //ETH 是原生代幣，它不是ERC20代幣, ......
uj5u.com 2023-03-21 07:56:29 more在solidity語言中 參考型別修飾符(參考型別為存盤空間不固定的數值型別) memory、calldata與storage,它們只能修飾參考型別變數，比如字串、陣列、位元組等... memory 適用于方法傳參、返參或在方法體內使用，使用完就會清除掉，釋放記憶體 calldata 僅適用于方法傳參 ......
uj5u.com 2023-03-08 07:57:54 more在solidity語言中 注釋符為// 注解符為/* 內容*/ 或者 是 ///內容 注解中含有這幾個標簽給予我們使用 @title 一個應該描述合約/介面的標題 contract, library, interface @author 作者的名字 contract, library, interf ......
uj5u.com 2023-03-08 07:57:49 more【代碼注釋自動生成方法綜述】 這些評測指標主要來自機器翻譯和文本總結等研究領域,可以評估候選文本(即基于代碼注釋自動方法而生成)和參考文本(即基于手工方式而生成)的相似度. BLEU指標^[^?88^^?^]^:其全稱是bilingual evaluation understudy.該指標是最早用于 ......
uj5u.com 2023-02-23 07:27:39 more最近，一個幽靈，Web3的幽靈，在網路游蕩，它叫Damus，這玩意詮釋了什么叫做病毒式營銷，滑稽的是，一個Web3產品卻在Web2的產品鏈上瘋狂傳銷，各方大佬紛紛為其背書，到底發生了什么？Damus的葫蘆里，賣的是什么藥？ 注冊和簡單實用 很少有什么產品在用戶注冊環節會有什么噱頭，但Damus確實出 ......
uj5u.com 2023-02-05 06:48:39 more