凸多边形顶点排序问题的一种分治算法

【摘 要】对凸多边形顶点排序问题做深入分析，提出一种基于矢量方向比较的凸多边形顶点排序分治算法。首先深入分析凸多边形顶点排序问题的背景；其次提出基于矢量方向比较的凸多边形顶点排序分治算法；最后通过C++编程实现该算法，并分析该算法的时间复杂度和空间复杂度。该算法已经应用在实际项目中，证明该算法是简单高效的。

【关键词】凸多边形 顶点排序 凸包问题 分治算法

一、问题描述

（一）凸包问题和凸多边形定义

凸包问题[1]是计算机图形学中一个很重要的基础问题，在GIS、CAD等领域有广泛的应用。对凸包问题的求解有不少高效算法，例如卷包裹算法[2]，分治算法[3]等。简单多边形[4]的凸包问题是其中一个特例，而凸多边形顶点排序问题又是简单多边形凸包问题的一个特例，目前对其研究不多。下面给出凸多边形的严格定义。

[定义1]在一个简单多边形中，如果所有顶点都是凸顶点[5]，则称该多边形是一个凸多边形。

（二）凸多边形顶点排序问题

作者在开发有限元系统时遇到这样的问题，一个空间六面体网格单元被一个平面切割， 12条边可能与切割面相交于n（3

六面体与平面相交后只有n个交点的坐标信息，顶点的连接顺序就是我们要解决的凸多边形顶点排序问题。

二、算法分析

首先可以简化问题：当切平面与某坐标平面不垂直时，可以将n个交点投影到该坐标平面（例如xoy平面）上，这样将三维问题简化为二维问题。

在二维坐标平面上的n个点排序就是一个典型的凸包问题，我们提出一种全新的快速分治算法。基础思想就是找一个凸多边形的内部点，然后将该点与所有n个顶点连接形成n个矢量，最后根据矢量与坐标轴夹角将n个点排序。假设P为凸多边形内部任意点，PQ为x轴正方向，A到F是凸多边形的6个顶点。显然按照PA、PB等矢量方向与PQ的逆时针夹角从小到大的顺序，可以将所有6个顶点逆时针排序，反之亦可。

该算法具体实现时，有以下几个问题需要解决。

（一）如何选择投影坐标面。

任取三个顶点所在平面与某坐标面不垂直时，我们可以投影到该坐标面。一个平面不可能同时与三个坐标面垂直，所以总能找到一个坐标面来投影。计算可以利用叉积求法向量的方式，但是该方式计算量大，我们可以逆用如下定理。

[定理1]：任取三点的xy坐标比值相同，则该平面必然垂直于xoy平面。

简单证明如下：当（Xa/Ya） = （Xb/Yb） = （Xc/Yc）时，a、b、c三点在xoy平面上的投影共线，则a、b、c三点所在平面垂直于xoy面。同理可得到xoz和yoz平面的类似结论。

（二）如何选择凸多边形内部点。

任取三顶点，求其几何中心P，则P点必然在凸多边形内。如公式（2.1）所示。

Xp=（Xa+Xb+Xc）/3

Yp=（Ya+Yb+Yc）/3

Xp=（Ya+Yb+Yc）/3 （2.1）

（三）如何对各顶点排序。

夹角的cos值在[0，π]之间随角度增大而减小，[π，2π]之间随角度增大而增大。因此，我们在对所有点排序前，需要将全部点分为两个子集。以在xoy平面的投影为例，按照y坐标是否大于P点可以将全部点分为“上部点”（例如{ABC}）和“下部点”（例如{DEF}）两个子集。对“上部点”我们按照cos值降序排列，对“下部点”按照cos值升序排列，这样就得到全部点的排列。而这种将问题分解，减小问题规模分而治之的思想正是典型的“分治”算法。cos值可以按照公式（2.2）求得。

cos（QPA）=（Xa-Xp）/（Ya-Yp） （2.2）

三、算法实现和复杂度分析

在c++中函数的声明形式为：int sortpolynode（int n， double *nodes）。其中函数返回值为排序的顶点数，返回值为-1时表示函数出错。参数n为多边形的顶点数，nodes是一个长度为3n的数组，存储n个顶点排序前的xyz坐标；排序后的顶点坐标仍然放在该数组中，实现数据的输出。

算法定义的辅助变量主要包括几个double类型的vector，包括upnodes、downnodes、upcoss、downcoss。前两个分别存储上部点和下部点的坐标，后两个存对应顶点与内部点P形成的矢量与横坐标正方向夹角的余弦值。前两个vector长度相加为3n，后两个相加等于n，另外还需要一些零散辅助空间，所以算法的空间复杂度为O（n）。

算法运行时，需要四个重要的循环。第一个循环次数为n，将n个顶点按照是否高于内部点p的纵坐标划分到“上部点”upnodes和“下部点”downnodes中。第二个循环次数为n，用于求所有顶点的cos值。第三个循环利用选择法或起泡法对upnodes、downnodes、upcoss和downcoss排序，循环次数为：（n-1）！=n（n-1）/2。第四个循环用于将upnodes和downnodes数据复制回nodes中作为函数输出，循环次数为n。所以整个算法的时间复杂度为O（n^2）。

四、结语

通过上述分析可知，该算法时空效率都很高。该算法已经应用在实际项目中，实践证明该算法是准确高效的。

参考文献：

[1] （美）莱维丁.算法设计与分析基础[M].北京：清华大学出版社，2007：53-105.

[2] 宋丽，姜旭东.卷包裹法求凸包问题算法分析与程序实现[J].牡丹江师范学院学报（自然科学版）， 2005， 04期：18-19.

[3] 刘新，刘任任.一种改进的构建凸包的分治算法[J].计算机工程与科学，2006，vol.28， NO.8：63-65.

[4] 刘润涛.简单多边形凸包的算法[J].哈尔滨理工大学学报，2002，vol.7，NO.2：98-100.

[5] 吴尚智.一种求简单多边形凸包的算法[J].甘肃科学学报，2000，vol.12，NO.4：11-13. 1Ppm4bmiJDnlLXot6/kvY7lip/ogJforr7orqHmioDmnK9kAgEPZBYCZg8VBAANc3poaDIwMTMxNzE3NirosIjosIjnu4TlkIjpgLvovpHnlLXot6/nmoTliIbmnpDlkozorr7orqEq6LCI6LCI57uE5ZCI6YC76L6R55S16Lev55qE5YiG5p6Q5ZKM6K6+6K6hZAICD2QWAmYPFQQADXN6aGgyMDEzMTcxNzcv5Z+65LqO55So5oi35L2T6aqM55qE55WM6Z2i6K6+6K6h77yIVUnvvInnoJTnqbYv5Z+65LqO55So5oi35L2T6aqM55qE55WM6Z2i6K6+6K6h77yIVUnvvInnoJTnqbZkAgMPZBYCZg8VBAANc3poaDIwMTMxNzE3ODHln7rkuo5SRklE5oqA5pyv55qE56e75Yqo55S15a2Q5ZWG5Yqh5bqU55So6K6+6K6hMeWfuuS6jlJGSUTmioDmnK/nmoTnp7vliqjnlLXlrZDllYbliqHlupTnlKjorr7orqFkAgQPZBYCZg8VBAANc3poaDIwMTMxNzE3OTDlhbPkuo7nlLXlrZDkv6Hmga/mioDmnK/moIflh4bljJbnmoTlj5HlsZXliIbmnpAw5YWz5LqO55S15a2Q5L+h5oGv5oqA5pyv5qCH5YeG5YyW55qE5Y+R5bGV5YiG5p6QZAIFD2QWAmYPFQQADXN6aGgyMDEzMTcxODBC5Z+O5biC5aSp54S25rCU5bi455So6K6h6YeP5Luq6KGo5bel5L2c5Y6f55CG5Y+K6YCJ5Z6L5bqU55So5rWF5p6QQuWfjuW4guWkqeeEtuawlOW4uOeUqOiuoemHj+S7quihqOW3peS9nOWOn+eQhuWPiumAieWei+W6lOeUqOa1heaekGQCBg9kFgJmDxUEAA1zemhoMjAxMzE3MTgxP0NMMjAwNeezu+WIl0xFROeUteWtkOmAmuiur+Wxj+aOp+WItuezu+e7n+eahOWuieijheS9v+eUqOeglOeptj9DTDIwMDXns7vliJdMRUTnlLXlrZDpgJrorq/lsY/mjqfliLbns7vnu5/nmoTlronoo4Xkvb/nlKjnoJTnqbZkAgcPZBYCZg8VBAANc3poaDIwMTMxNzE4MhjnlLXlrZDnur/ot6/lrp7pqozliIbmnpAY55S15a2Q57q/6Lev5a6e6aqM5YiG5p6QZAIID2QWAmYPFQQADXN6aGgyMDEzMTcxODM35Z+65LqOVlhNTOaKgOacr+eahOWkmua4oOmBk+mAmuiur+W5s+WPsOeahOeglOeptuWunui3tTfln7rkuo5WWE1M5oqA5pyv55qE5aSa5rig6YGT6YCa6K6v5bmz5Y+w55qE56CU56m25a6e6Le1ZAIJD2QWAmYPFQQADXN6aGgyMDEzMTcxODQw55S15a2Q6YCa6K6v6K6+5aSH55qE5Y+v6Z2g5oCn6K6+6K6h5oqA5pyv6K666L+wMOeUteWtkOmAmuiur+iuvuWkh+eahOWPr+mdoOaAp+iuvuiuoeaKgOacr+iuuui/sGQCCg9kFgJmDxUEAA1zemhoMjAxMzE3MTg1ReeUteWtkOW8j+eUteiDveihqOWcqOajgOWumui/h+eoi+S4reW6lOazqOaEj+eahOmXrumimOWPiuino+WGs+WKnuazlUXnlLXlrZDlvI/nlLXog73ooajlnKjmo4Dlrprov4fnqIvkuK3lupTms6jmhI/nmoTpl67popjlj4rop6PlhrPlip7ms5VkAgsPZBYCZg8VBAANc3poaDIwMTMxNzE4NifnlLXlrZDpgJrorq/kuqfkuJrnmoTlj5HlsZXnirblhrXliIbmnpAn55S15a2Q6YCa6K6v5Lqn5Lia55qE5Y+R5bGV54q25Ya15YiG5p6QZAIMD2QWAmYPFQQADXN6aGgyMDEzMTcxODct5paw5pe25pyf55S15a2Q6YCa6K6v55qE6aKE57yW56CB5oqA5pyv5o6i5b6uLeaWsOaXtuacn+eUteWtkOmAmuiur+eahOmihOe8lueggeaKgOacr+aOouW+rmQCDQ9kFgJmDxUEAA1zemhoMjAxMzE3MTg4JeWfuuS6jlNPUEPnmoTmtrLmmbbmmL7npLrns7vnu5/orr7orqEl5Z+65LqOU09QQ+eahOa2suaZtuaYvuekuuezu+e7n+iuvuiuoWQCDg9kFgJmDxUEAA1zemhoMjAxMzE3MTg5J+WNs+aMh+WNs+ivkee/u+ivkeWZqOeahOiuvuiuoeS4juWunueOsCfljbPmjIfljbPor5Hnv7vor5HlmajnmoTorr7orqHkuI7lrp7njrBkAgkPZBYEZg8VAQznu4/mtY7nrqHnkIZkAgEPFgIfAQIKFhRmD2QWAmYPFQQADXN6aGgyMDEzMTcxOTAn5LyB5Lia5bm26LSt56iO5pS256255YiS55qE6aOO6Zmp5YiG5p6QJ+S8geS4muW5tui0reeojuaUtuetueWIkueahOmjjumZqeWIhuaekGQCAQ9kFgJmDxUEAA1zemhoMjAxMzE3MTkxIea1heiwiOeOsOS7o+S8geS4mueahOWuieWFqOeuoeeQhiHmtYXosIjnjrDku6PkvIHkuJrnmoTlronlhajnrqHnkIZkAgIPZBYCZg8VBAANc3poaDIwMTMxNzE5Mhjlhazlj7jnmoTku7flgLzpk77liIbmnpAY5YWs5Y+455qE5Lu35YC86ZO+5YiG5p6QZAIDD2QWAmYPFQQADXN6aGgyMDEzMTcxOTMw5aSn5a2m55Sf572R57uc5Yib5Lia55qE546w54q244CB5Y6f5Zug5Y+K5a+5562WMOWkp+WtpueUn+e9kee7nOWIm+S4mueahOeOsOeKtuOAgeWOn+WboOWPiuWvueetlmQCBA9kFgJmDxUEAA1zemhoMjAxMzE3MTk0NuaOoueptuWvueaIkeWbveS8geS4muS8muiuoeaUv+etlumAieaLqeeahOeQhuaAp+aAneiAgzbmjqLnqbblr7nmiJHlm73kvIHkuJrkvJrorqHmlL/nrZbpgInmi6nnmoTnkIbmgKfmgJ3ogINkAgUPZBYCZg8VBAANc3poaDIwMTMxNzE5NTDmtYXmnpDln47kuaHop4TliJLlu7rorr7kuK3nmoTotKLliqHnrqHnkIbpl67popgw5rWF5p6Q5Z+O5Lmh6KeE5YiS5bu66K6+5Lit55qE6LSi5Yqh566h55CG6Zeu6aKYZAIGD2QWAmYPFQQADXN6aGgyMDEzMTcxOTYz5oiR5Zu95LiK5biC5YWs5Y+455uI5L2Z566h55CG5pa55rOV5LiO5a6h6K6h562W55WlM+aIkeWbveS4iuW4guWFrOWPuOebiOS9meeuoeeQhuaWueazleS4juWuoeiuoeetlueVpWQCBw9kFgJmDxUEAA1zemhoMjAxMzE3MTk3NuS9jueis+e7j+a1juinhuinkuS4i+eahOWMuuWfn+e7j+a1juWPkeWxlei3r+W+hOeglOeptjbkvY7norPnu4/mtY7op4bop5LkuIvnmoTljLrln5/nu4/mtY7lj5HlsZXot6/lvoTnoJTnqbZkAggPZBYCZg8VBAANc3poaDIwMTMxNzE5OBjorrrkvIHkuJrmoLjlv4Pnq57kuonlipsY6K665LyB5Lia5qC45b+D56ue5LqJ5YqbZAIJD2QWAmYPFQQADXN6aGgyMDEzMTcxOTkz5Yqg5by66YCa5L+h6KGM5Lia5qyg6LS5566h55CG77yM5o6n5Yi25Z2P6LSm6aOO6ZmpM+WKoOW8uumAmuS/oeihjOS4muasoOi0ueeuoeeQhu+8jOaOp+WItuWdj+i0pumjjumZqWQCCg9kFgRmDxUBDOe7vOWQiOiuuuWdm2QCAQ8WAh8BAiQWSGYPZBYCZg8VBAANc3poaDIwMTMxNzIwMCHmgJ3mg7PlrqPkvKDlkozkvIHkuJrmlofljJbovqjmnpAh5oCd5oOz5a6j5Lyg5ZKM5LyB5Lia5paH5YyW6L6o5p6QZAIBD2QWAmYPFQQADXN6aGgyMDEzMTcyMDEV5pGG6ISx5Y2V5LiA55qE5o+t56eYFeaRhuiEseWNleS4gOeahOaPreenmGQCAg9kFgJmDxUEAA1zemhoMjAxMzE3MjAyJOeOsOS7o+aVsOWtl+iInuWPsOWxleekuuW5s+WPsOeglOeptiTnjrDku6PmlbDlrZfoiJ7lj7DlsZXnpLrlubPlj7DnoJTnqbZkAgMPZBYCZg8VBAANc3poaDIwMTMxNzIwMy3or5XorrrlpoLkvZXlgZrlpb3kvIHkuJrmgJ3mg7PmlL/msrvlt6XkvZzogIUt6K+V6K665aaC5L2V5YGa5aW95LyB5Lia5oCd5oOz5pS/5rK75bel5L2c6ICFZAIED2QWAmYPFQQADXN6aGgyMDEzMTcyMDRGMjAxMeW5tOa+s+e9keWls+WNleWGs+i1m+adjuWonOS4juWFi+mHjOaWr+eJueWwlOaWr+aKgOacr+avlOi+g+eglOeptkYyMDEx5bm05r6z572R5aWz5Y2V5Yaz6LWb5p2O5aic5LiO5YWL6YeM5pav54m55bCU5pav5oqA5pyv5q+U6L6D56CU56m2ZAIFD2QWAmYPFQQADXN6aGgyMDEzMTcyMDU75YWz5LqO5o+Q5Y2H5YuY5rWL6K6+6K6h5LyB5LiaSVTov5Dnu7TnrqHnkIbotKjph4/nmoTmjqLnqbY75YWz5LqO5o+Q5Y2H5YuY5rWL6K6+6K6h5LyB5LiaSVTov5Dnu7TnrqHnkIbotKjph4/nmoTmjqLnqbZkAgYPZBYCZg8VBAANc3poaDIwMTMxNzIwNjblr7nmj5Dpq5jlhpvpmJ/mlL/msrvmnLrlhbPlubLpg6jntKDotKjnmoTlh6DngrnmgJ3ogIM25a+55o+Q6auY5Yab6Zif5pS/5rK75py65YWz5bmy6YOo57Sg6LSo55qE5Yeg54K55oCd6ICDZAIHD2QWAmYPFQQADXN6aGgyMDEzMTcyMDc25YWz5LqO5pWw5a2X55S16KeG57O757uf55qE5pWw5a2X5Lia5Yqh5bmz5Y+w55qE56CU56m2NuWFs+S6juaVsOWtl+eUteinhuezu+e7n+eahOaVsOWtl+S4muWKoeW5s+WPsOeahOeglOeptmQCCA9kFgJmDxUEAA1zemhoMjAxMzE3MjA4UeWFs+S6juWMu+WtpumZouagoeW8gOWxleWkp+WtpueUn+WIm+aWsOWIm+S4muiuree7g+iuoeWIkumhueebrueahOWunui3teS4juaAneiAg1HlhbPkuo7ljLvlrabpmaLmoKHlvIDlsZXlpKflrabnlJ/liJvmlrDliJvkuJrorq3nu4PorqHliJLpobnnm67nmoTlrp7ot7XkuI7mgJ3ogINkAgkPZBYCZg8VBAANc3poaDIwMTMxNzIwOVHlnZrmjIHnlKjnpL7kvJrkuLvkuYnmoLjlv4Pku7flgLzkvZPns7vogrLkurrliqrlipvmiqzpq5jpq5jmoKHmlofljJblu7rorr7msLTlubNR5Z2a5oyB55So56S+5Lya5Li75LmJ5qC45b+D5Lu35YC85L2T57O76IKy5Lq65Yqq5Yqb5oqs6auY6auY5qCh5paH5YyW5bu66K6+5rC05bmzZAIKD2QWAmYPFQQADXN6aGgyMDEzMTcyMTBR5Yqg5by65Yy75a2m6Zmi5qCh5a6e5pa95aSn5a2m55Sf5Yib5paw5Yib5Lia6K6t57uD6K6h5YiS566h55CG55qE5a+5562W5ZKM5bu66K6uUeWKoOW8uuWMu+WtpumZouagoeWunuaWveWkp+WtpueUn+WIm+aWsOWIm+S4muiuree7g+iuoeWIkueuoeeQhueahOWvueetluWSjOW7uuiurmQCCw9kFgJmDxUEAA1zemhoMjAxMzE3MjExMOa1heaekOeUteW9seOAiuWFrOawkeWHr+aBqeOAi+eahOWIm+aWsOS4jueqgeegtDDmtYXmnpDnlLXlvbHjgIrlhazmsJHlh6/mganjgIvnmoTliJvmlrDkuI7nqoHnoLRkAgwPZBYCZg8VBAANc3poaDIwMTMxNzIxMjnorrrlronlhajkuLvku7vliLblnKjljJblt6XkvIHkuJrlronlhajnrqHnkIbkuK3nmoTlupTnlKg56K665a6J5YWo5Li75Lu75Yi25Zyo5YyW5bel5LyB5Lia5a6J5YWo566h55CG5Lit55qE5bqU55SoZAIND2QWAmYPFQQADXN6aGgyMDEzMTcyMTM55b2T5LuK5oiR5Zu95pS/5bqc6YeH6LSt55qE546w54q244CB6Zeu6aKY5Y+K5a+5562W56CU56m2OeW9k+S7iuaIkeWbveaUv+W6nOmHh+i0reeahOeOsOeKtuOAgemXrumimOWPiuWvueetlueglOeptmQCDg9kFgJmDxUEAA1zemhoMjAxMzE3MjE0M+aVsOWtl+WMluaKgOacr+WPkeWxleWvueS8oOWqkuS6p+S4mueahOW9seWTjeWIhuaekDPmlbDlrZfljJbmioDmnK/lj5HlsZXlr7nkvKDlqpLkuqfkuJrnmoTlvbHlk43liIbmnpBkAg8PZBYCZg8VBAANc3poaDIwMTMxNzIxNRXkuLrkurrpgKDniannmoToibrmnK8V5Li65Lq66YCg54mp55qE6Im65pyvZAIQD2QWAmYPFQQADXN6aGgyMDEzMTcyMTYe5LyB5Lia572R56uZ55qE5byA5Y+R5LiO5bqU55SoHuS8geS4mue9keermeeahOW8gOWPkeS4juW6lOeUqGQCEQ9kFgJmDxUEAA1zemhoMjAxMzE3MjE3JOa1heaekOe+juWGm+WQjuWLpOaMh+aMpeWPkeWxleWKqOaAgSTmtYXmnpDnvo7lhpvlkI7li6TmjIfmjKXlj5HlsZXliqjmgIFkAhIPZBYCZg8VBAANc3poaDIwMTMxNzIxOCrlr7nlvZPliY3lhpzmnZHnjq/looPkv53miqTpl67popjnmoTnoJTnqbYq5a+55b2T5YmN5Yac5p2R546v5aKD5L+d5oqk6Zeu6aKY55qE56CU56m2ZAITD2QWAmYPFQQADXN6aGgyMDEzMTcyMTkw6K+X5oSP55qE5qCW5bGF77ya5LuO5bGx5rC06K+X55yL5ZSQ5a6L6K+X5LmL5YirMOivl+aEj+eahOagluWxhe+8muS7juWxseawtOivl+eci+WUkOWui+ivl+S5i+WIq2QCFA9kFgJmDxUEAA1zemhoMjAxMzE3MjIwH+a1geihjOivreKAnFjpl6jigJ3miJDlm6DliIbmnpAf5rWB6KGM6K+t4oCcWOmXqOKAneaIkOWboOWIhuaekGQCFQ9kFgJmDxUEAA1zemhoMjAxMzE3MjIxNuWkluadpeiqnuOBruWPl+WuueOBjOaXpeacrOekvuS8muOBq+OCguOBn+OCieOBmeW9semfvzblpJbmnaXoqp7jga7lj5flrrnjgYzml6XmnKznpL7kvJrjgavjgoLjgZ/jgonjgZnlvbHpn79kAhYPZBYCZg8VBAANc3poaDIwMTMxNzIyMiflhbPkuo7ln47luILlgaXlurflj5HlsZXnmoTlk7LlrabmgJ3ogIMn5YWz5LqO5Z+O5biC5YGl5bq35Y+R5bGV55qE5ZOy5a2m5oCd6ICDZAIXD2QWAmYPFQQADXN6aGgyMDEzMTcyMjMh6K665Lit5Zu95Zu95a625a6h6K6h5Y+R5bGV6LaL5Yq/IeiuuuS4reWbveWbveWutuWuoeiuoeWPkeWxlei2i+WKv2QCGA9kFgJmDxUEAA1zemhoMjAxMzE3MjI0Kua3seW6puaKpemBk+S4uue6uOWqkuWinuWKoOaguOW/g+ernuS6ieWKmyrmt7HluqbmiqXpgZPkuLrnurjlqpLlop7liqDmoLjlv4Pnq57kuonliptkAhkPZBYCZg8VBAANc3poaDIwMTMxNzIyNVzlpK/lrp7ln7rnoYAg56ev5p6B5o6i57SiIOazqOmHjeWunuaViOaehOW7uuW3peeoi+W7uuiuvumihuWfn+W7ieaUv+mjjumZqemYsuaOp+mVv+aViOacuuWItlzlpK/lrp7ln7rnoYAg56ev5p6B5o6i57SiIOazqOmHjeWunuaViOaehOW7uuW3peeoi+W7uuiuvumihuWfn+W7ieaUv+mjjumZqemYsuaOp+mVv+aViOacuuWItmQCGg9kFgJmDxUEAA1zemhoMjAxMzE3MjI2M+OAiuivtOaWh+ino+Wtl+OAi+mHiuS5ieWFg+ivreiogOeglOeptuaKgOacr+i3r+e6vzPjgIror7Tmlofop6PlrZfjgIvph4rkuYnlhYPor63oqIDnoJTnqbbmioDmnK/ot6/nur9kAhsPZBYCZg8VBAANc3poaDIwMTMxNzIyNznmj5DljYfnhaTnn7/kvIHkuJrlrqPkvKDmiqXpgZPlt6XkvZzmlYjog73nmoTot6/lvoTmjqLmnpA55o+Q5Y2H54Wk55+/5LyB5Lia5a6j5Lyg5oql6YGT5bel5L2c5pWI6IO955qE6Lev5b6E5o6i5p6QZAIcD2QWAmYPFQQADXN6aGgyMDEzMTcyMjgt5paw5Z6L55S15Yqb5a6i5oi35pyN5Yqh5L+d6Zqc5L2T57O755qE5bu66K6+LeaWsOWei+eUteWKm+WuouaIt+acjeWKoeS/nemanOS9k+ezu+eahOW7uuiuvmQCHQ9kFgJmDxUEAA1zemhoMjAxMzE3MjI5Hua1heiwiOi+o+akkumrmOS6p+agveWfueaKgOacrx7mtYXosIjovqPmpJLpq5jkuqfmoL3ln7nmioDmnK9kAh4PZBYCZg8VBAANc3poaDIwMTMxNzIzMDznuqrmo4Dlt6XkvZzlnKjln7rlsYLlhZrliqHlt6XkvZznrqHnkIbkuK3nmoTkuKXogoPmgKfliIbmnpA857qq5qOA5bel5L2c5Zyo5Z+65bGC5YWa5Yqh5bel5L2c566h55CG5Lit55qE5Lil6IKD5oCn5YiG5p6QZAIfD2QWAmYPFQQADXN6aGgyMDEzMTcyMzEh6K665Lit5Zu95Lyg57uf5Zut5p6X6KaB57Sg54m554K5IeiuuuS4reWbveS8oOe7n+Wbreael+imgee0oOeJueeCuWQCIA9kFgJmDxUEAA1zemhoMjAxMzE3MjMyMeWKoOW8uumBk+W+t+W7uuiuviDlhajpnaLmj5Dpq5jlhazmsJHpgZPlvrfntKDotKgx5Yqg5by66YGT5b635bu66K6+IOWFqOmdouaPkOmrmOWFrOawkemBk+W+t+e0oOi0qGQCIQ9kFgJmDxUEAA1zemhoMjAxMzE3MjMzMOa1heiuruWmguS9leW8uuWMlumBk+i3r+i/kOi+k+W4guWcuuS+neazleeuoeeQhjDmtYXorq7lpoLkvZXlvLrljJbpgZPot6/ov5DovpPluILlnLrkvp3ms5XnrqHnkIZkAiIPZBYCZg8VBAANc3poaDIwMTMxNzIzNCflm73lhoXlvq7nlLXlvbHlkoznlLXlvbHmioDmnK/nmoTnjrDnirYn5Zu95YaF5b6u55S15b2x5ZKM55S15b2x5oqA5pyv55qE546w54q2ZAIjD2QWAmYPFQQADXN6aGgyMDEzMTcyMzU856ue5oqA5YGl576O5pON6L+Q5Yqo5ZGY6Lid5YWz6IqC5o2f5Lyk5Y6f5Zug5Y+K6aKE6Ziy5o6q5pa9POernuaKgOWBpee+juaTjei/kOWKqOWRmOi4neWFs+iKguaNn+S8pOWOn+WboOWPiumihOmYsuaOquaWvWRk+w2ZJyE+B4PPGRwyQTp9dM13tR4=" /> // monitor