{
"cells": [
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"name": "stderr",
"output_type": "stream",
"text": [
"/Users/sth/dev/rust-polylabel/venv/lib/python2.7/site-packages/matplotlib/__init__.py:913: UserWarning: axes.color_cycle is deprecated and replaced with axes.prop_cycle; please use the latter.\n",
" warnings.warn(self.msg_depr % (key, alt_key))\n"
]
}
],
"source": [
"from shapely.geometry import LineString, Polygon, MultiPolygon, MultiLineString, GeometryCollection, Point, MultiPoint, box, shape\n",
"from shapely.geometry.polygon import orient\n",
"from shapely.affinity import rotate, scale\n",
"from scipy.spatial import Delaunay\n",
"import numpy as np\n",
"import matplotlib.pyplot as plt\n",
"from matplotlib.tri import Triangulation"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"polygon = Polygon([(0.0, 0.0), (4.0, 0.0), (4.0, 1.0), (1.0, 1.0), (1.0, 4.0), (0.0, 4.0),\n",
" (0.0, 0.0)])"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"-0.16 -0.16 4.32 4.32\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,4.0)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.0864\" opacity=\"0.6\" d=\"M 0.0,0.0 L 4.0,0.0 L 4.0,1.0 L 1.0,1.0 L 1.0,4.0 L 0.0,4.0 L 0.0,0.0 z\" /></g></svg>"
],
"text/plain": [
"<shapely.geometry.polygon.Polygon at 0x104e3fe10>"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"polygon"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(0.0, 0.0, 4.0, 4.0)"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"polygon.bounds"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"-0.16 -0.16 4.32 4.32\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,4.0)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.0864\" opacity=\"0.6\" d=\"M 0.0,0.0 L 0.0,4.0 L 1.0,4.0 L 4.0,1.0 L 4.0,0.0 L 0.0,0.0 z\" /></g></svg>"
],
"text/plain": [
"<shapely.geometry.polygon.Polygon at 0x104e3f790>"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"polygon.convex_hull"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(0.0, 0.0), (4.0, 0.0), (4.0, 1.0), (1.0, 4.0), (0.0, 4.0), (0.0, 0.0)]"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"list(orient(polygon.convex_hull).exterior.coords)"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"-0.16 -0.16 4.32 4.32\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,4.0)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.0864\" opacity=\"0.6\" d=\"M 0.0,0.0 L 0.0,0.0 L 4.0,0.0 L 4.0,1.0 L 1.0,4.0 L 0.0,4.0 L 0.0,0.0 z\" /></g></svg>"
],
"text/plain": [
"<shapely.geometry.polygon.Polygon at 0x104e7d6d0>"
]
},
"execution_count": 10,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# From Rust \n",
"Polygon([(0., 0.), (0., 0.), (4., 0.), (4., 1.), (1., 4.), (0., 4.), (0., 0.)])"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"-0.16 -0.16 4.32 4.32\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,4.0)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.0864\" opacity=\"0.6\" d=\"M 0.0,0.0 L 0.0,4.0 L 1.0,4.0 L 4.0,1.0 L 4.0,0.0 L 0.0,0.0 z\" /></g></svg>"
],
"text/plain": [
"<shapely.geometry.polygon.Polygon at 0x104e7d2d0>"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# From Rust Quickhull\n",
"Polygon([(0., 0.), (0., 4.), (1., 4.), (4., 1.), (4., 0.), (0., 0.)])"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"300\" height=\"300\" viewBox=\"-273.968409519 -323.968409519 497.924569065 647.897482755\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,-0.0393362833963)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"4.3193165517\" opacity=\"0.6\" d=\"M -75.5727402877,110.019601411 L -47.0142500145,224.253562504 L -44.19860524,233.565201784 L -40.4915168482,242.559198518 L -35.9280666778,251.150438483 L -30.551440703,259.257618925 L -24.4125203449,266.804017962 L -17.5694009582,273.718220639 L -10.0868420484,279.934794756 L -2.03565442373,285.394910087 L 6.50796991896,290.046895113 L 15.4631788337,293.846726015 L 24.7452251651,296.758443291 L 34.2662687489,298.754492054 L 43.9362076827,299.815982802 L 53.6635310009,299.932870171 L 63.3561846833,299.104048004 L 72.9224428043,297.337359816 L 82.2717755762,294.649524569 L 91.3157060729,291.065978454 L 99.968647527,286.620634172 L 108.148713276,281.355560009 L 115.778491691,275.320581722 L 122.78577876,268.572811014 L 129.104261385,261.176105064 L 134.674144933,253.200462215 L 139.4427191,244.72135955 L 189.4427191,144.72135955 L 193.403164872,135.71902563 L 196.46014848,126.371191766 L 198.584100595,116.768276889 L 199.754476834,107.003167254 L 199.959956481,97.1703179803 L 199.19855199,87.3648394134 L 197.47762821,77.6815771497 L 194.813831145,68.2141946222 L 191.232926945,59.0542671207 L 186.769552674,50.2903960105 L 181.466881277,42.0073517161 L 175.376203983,34.2852537616 L 168.556434174,27.1987957973 L 161.073537538,20.816523109 L 152.999894,15.2001695995 L 98.3365328625,-18.9644311116 L 97.0142500145,-24.2535625036 L 94.1698350446,-33.6458343286 L 90.4185130847,-42.7140783764 L 85.7964114161,-51.3709624995 L 80.3480434044,-59.5331161715 L 74.125879812,-67.1219333906 L 67.1898434757,-74.0643296986 L 59.606732217,-80.293446024 L 51.4495755428,-85.7492925713 L 42.7969313308,-90.3793265557 L 33.7321292749,-94.1389582191 L 24.3424683743,-96.9919802532 L 14.7183761963,-98.9109164963 L 4.95253800962,-99.8772865434 L -4.86099582541,-99.8817837225 L -14.6277156134,-98.9243647234 L -17.9537568093,-98.264358359 L -53.648209037,-226.764386379 L -56.7355378616,-236.079635559 L -60.7210544402,-245.047418125 L -65.5663760693,-253.581369429 L -71.224839653,-261.599302856 L -77.6419510937,-269.024001322 L -84.7559101003,-275.783960923 L -92.4982053587,-281.814079553 L -100.794274333,-287.056283872 L -109.564221344,-291.460088588 L -118.723587009,-294.983082654 L -128.184161627,-297.59133771 L -137.854834695,-299.259734836 L -147.642472344,-299.972206454 L -157.452814273,-299.721891074 L -167.191381527,-298.511199369 L -176.764386379,-296.351790963 L -186.079635559,-293.264462138 L -195.047418125,-289.27894556 L -203.581369429,-284.433623931 L -211.599302856,-278.775160347 L -219.024001322,-272.358048906 L -225.783960923,-265.2440899 L -231.814079553,-257.501794641 L -237.056283872,-249.205725667 L -241.460088588,-240.435778656 L -244.983082654,-231.276412991 L -247.59133771,-221.815838373 L -249.259734836,-212.145165305 L -249.972206454,-202.357527656 L -249.721891074,-192.547185727 L -248.511199369,-182.808618473 L -246.351790963,-173.235613621 L -196.351790963,6.76438637861 L -193.325766603,15.9207640237 L -189.431849243,24.7430926622 L -184.706250787,33.1493281005 L -179.192917447,41.0612956486 L -172.943121057,48.4054171137 L -166.014982271,55.1133950487 L -158.472930061,61.1228478916 L -150.387102552,66.3778900898 L -75.5727402877,110.019601411 z\" /></g></svg>"
],
"text/plain": [
"<shapely.geometry.polygon.Polygon at 0x104ee6090>"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Polygon([\n",
" (-75.57274028771249, 110.01960141091608),\n",
" (-47.01425001453319, 224.2535625036333),\n",
" (-44.1986052400443, 233.56520178444188),\n",
" (-40.491516848197264, 242.55919851821028),\n",
" (-35.928066677809895, 251.1504384831045),\n",
" (-30.55144070299677, 259.2576189250935),\n",
" (-24.412520344941953, 266.8040179623472),\n",
" (-17.56940095820731, 273.7182206387879),\n",
" (-10.086842048356445, 279.93479475582495),\n",
" (-2.0356544237308825, 285.394910086574),\n",
" (6.507969918963688, 290.0468951126591),\n",
" (15.463178833668529, 293.8467260149487),\n",
" (24.745225165064543, 296.758443290685),\n",
" (34.26626874888323, 298.7544920543751),\n",
" (43.93620768274765, 299.8159828020204),\n",
" (53.66353100085455, 299.9328701709592),\n",
" (63.35618468325523, 299.10404800363494),\n",
" (72.92244280430123, 297.33735981566144),\n",
" (82.27177557618647, 294.64952456911897),\n",
" (91.31570607290114, 291.0659784535237),\n",
" (99.96864752703414, 286.6206341717666),\n",
" (108.14871327570971, 281.355560009008),\n",
" (115.77849169077639, 275.3205817216414),\n",
" (122.78577875973701, 268.57281101383126),\n",
" (129.10426138467784, 261.17610506386103),\n",
" (134.67414493283295, 253.20046221503722),\n",
" (139.44271909999156, 244.72135954999587),\n",
" (189.4427190999916, 144.72135954999578),\n",
" (193.40316487178438, 135.7190256296874),\n",
" (196.46014848027284, 126.37119176608674),\n",
" (198.5841005952538, 116.76827688896145),\n",
" (199.75447683394128, 107.00316725394137),\n",
" (199.959956480919, 97.1703179802708),\n",
" (199.19855199019082, 87.36483941339068),\n",
" (197.47762821014587, 77.68157714970485),\n",
" (194.8138311454814, 68.21419462218802),\n",
" (191.23292694514913, 59.05426712072333),\n",
" (186.76955267374814, 50.29039601045239),\n",
" (181.46688127708177, 42.007351716050565),\n",
" (175.37620398257155, 34.28525376159651),\n",
" (168.5564341738489, 27.198795797276006),\n",
" (161.07353753840516, 20.81652310901589),\n",
" (152.99989400031805, 15.200169599491232),\n",
" (98.33653286253586, -18.964431111622638),\n",
" (97.01425001453319, -24.253562503633297),\n",
" (94.16983504461093, -33.64583432864707),\n",
" (90.41851308474087, -42.71407837639184),\n",
" (85.79641141607766, -51.37096249948156),\n",
" (80.34804340438832, -59.53311617147662),\n",
" (74.12587981200636, -67.12193339062866),\n",
" (67.189843475707, -74.06432969864774),\n",
" (59.606732217031976, -80.2934460239878),\n",
" (51.44957554275259, -85.74929257125446),\n",
" (42.79693133079759, -90.37932655572841),\n",
" (33.73212927494458, -94.13895821910516),\n",
" (24.342468374316272, -96.99198025324264),\n",
" (14.718376196296493, -98.91091649633165),\n",
" (4.952538009623515, -99.87728654335396),\n",
" (-4.860995825414805, -99.88178372248515),\n",
" (-14.627715613363762, -98.92436472343178),\n",
" (-17.953756809330994, -98.26435835897965),\n",
" (-53.64820903700594, -226.76438637860946),\n",
" (-56.7355378616229, -236.07963555856995),\n",
" (-60.72105444017349, -245.0474181249662),\n",
" (-65.5663760693013, -253.58136942939535),\n",
" (-71.22483965299563, -261.59930285566344),\n",
" (-77.64195109371464, -269.02400132182726),\n",
" (-84.75591010033425, -275.7839609229046),\n",
" (-92.49820535873518, -281.81407955256725),\n",
" (-100.79427433320987, -287.05628387201347),\n",
" (-109.56422134444159, -291.46008858796654),\n",
" (-118.72358700857137, -294.98308265364733),\n",
" (-128.18416162723517, -297.59133771033885),\n",
" (-137.85483469517902, -299.2597348360279),\n",
" (-147.64247234423098, -299.9722064543555),\n",
" (-157.4528142733637, -299.72189107416057),\n",
" (-167.19138152692128, -298.5111993693906),\n",
" (-176.76438637860946, -296.3517909629941),\n",
" (-186.0796355585698, -293.26446213837716),\n",
" (-195.04741812496607, -289.2789455598266),\n",
" (-203.58136942939524, -284.4336239306988),\n",
" (-211.59930285566332, -278.7751603470045),\n",
" (-219.02400132182714, -272.3580489062855),\n",
" (-225.78396092290453, -265.2440898996658),\n",
" (-231.8140795525672, -257.50179464126495),\n",
" (-237.0562838720134, -249.20572566679022),\n",
" (-241.46008858796648, -240.4357786555585),\n",
" (-244.98308265364727, -231.27641299142869),\n",
" (-247.59133771033882, -221.8158383727649),\n",
" (-249.25973483602792, -212.145165304821),\n",
" (-249.97220645435553, -202.35752765576902),\n",
" (-249.72189107416057, -192.54718572663626),\n",
" (-248.51119936939062, -182.8086184730787),\n",
" (-246.35179096299407, -173.23561362139054),\n",
" (-196.35179096299407, 6.7643863786094585),\n",
" (-193.32576660256726, 15.920764023655508),\n",
" (-189.43184924301974, 24.74309266215056),\n",
" (-184.7062507874361, 33.14932810051302),\n",
" (-179.19291744665992, 41.0612956486063),\n",
" (-172.94312105678188, 48.40541711367358),\n",
" (-166.01498227118805, 55.11339504865113),\n",
" (-158.47293006129595, 61.12284789161923),\n",
" (-150.3871025524086, 66.37789008984335),\n",
" (-75.57274028771249, 110.01960141091608)\n",
"])"
]
},
{
"cell_type": "code",
"execution_count": 328,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"300\" height=\"300\" viewBox=\"-273.968409519 -323.968409519 497.924569065 647.897482755\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,-0.0393362833963)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"4.3193165517\" opacity=\"0.6\" d=\"M 199.19855199,87.3648394134 L 197.47762821,77.6815771497 L 194.813831145,68.2141946222 L 191.232926945,59.0542671207 L 186.769552674,50.2903960105 L 181.466881277,42.0073517161 L 175.376203983,34.2852537616 L -71.224839653,-261.599302856 L -77.6419510937,-269.024001322 L -84.7559101003,-275.783960923 L -92.4982053587,-281.814079553 L -100.794274333,-287.056283872 L -109.564221344,-291.460088588 L -118.723587009,-294.983082654 L -128.184161627,-297.59133771 L -137.854834695,-299.259734836 L -147.642472344,-299.972206454 L -157.452814273,-299.721891074 L -167.191381527,-298.511199369 L -176.764386379,-296.351790963 L -186.079635559,-293.264462138 L -195.047418125,-289.27894556 L -203.581369429,-284.433623931 L -211.599302856,-278.775160347 L -219.024001322,-272.358048906 L -225.783960923,-265.2440899 L -231.814079553,-257.501794641 L -237.056283872,-249.205725667 L -241.460088588,-240.435778656 L -244.983082654,-231.276412991 L -247.59133771,-221.815838373 L -249.259734836,-212.145165305 L -249.972206454,-202.357527656 L -249.721891074,-192.547185727 L -248.511199369,-182.808618473 L -246.351790963,-173.235613621 L -196.351790963,6.76438637861 L -193.325766603,15.9207640237 L -189.431849243,24.7430926622 L -184.706250787,33.1493281005 L -30.551440703,259.257618925 L -24.4125203449,266.804017962 L -17.5694009582,273.718220639 L -10.0868420484,279.934794756 L -2.03565442373,285.394910087 L 6.50796991896,290.046895113 L 15.4631788337,293.846726015 L 24.7452251651,296.758443291 L 34.2662687489,298.754492054 L 43.9362076827,299.815982802 L 53.6635310009,299.932870171 L 63.3561846833,299.104048004 L 72.9224428043,297.337359816 L 82.2717755762,294.649524569 L 91.3157060729,291.065978454 L 99.968647527,286.620634172 L 108.148713276,281.355560009 L 115.778491691,275.320581722 L 122.78577876,268.572811014 L 129.104261385,261.176105064 L 134.674144933,253.200462215 L 139.4427191,244.72135955 L 189.4427191,144.72135955 L 193.403164872,135.71902563 L 196.46014848,126.371191766 L 198.584100595,116.768276889 L 199.754476834,107.003167254 L 199.959956481,97.1703179803 L 199.19855199,87.3648394134 z\" /></g></svg>"
],
"text/plain": [
"<shapely.geometry.polygon.Polygon at 0x10506ab10>"
]
},
"execution_count": 328,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# from rust quick_hull\n",
"p = Polygon([\n",
" (199.19855199019082, 87.36483941339068),\n",
" (197.47762821014587, 77.68157714970485),\n",
" (194.8138311454814, 68.21419462218802),\n",
" (191.23292694514913, 59.05426712072333),\n",
" (186.76955267374814, 50.29039601045239),\n",
" (181.46688127708177, 42.007351716050565),\n",
" (175.37620398257155, 34.28525376159651),\n",
" (-71.22483965299563, -261.59930285566344),\n",
" (-77.64195109371464, -269.02400132182726),\n",
" (-84.75591010033425, -275.7839609229046),\n",
" (-92.49820535873518, -281.81407955256725),\n",
" (-100.79427433320987, -287.05628387201347),\n",
" (-109.56422134444159, -291.46008858796654),\n",
" (-118.72358700857137, -294.98308265364733),\n",
" (-128.18416162723517, -297.59133771033885),\n",
" (-137.85483469517902, -299.2597348360279),\n",
" (-147.64247234423098, -299.9722064543555),\n",
" (-157.4528142733637, -299.72189107416057),\n",
" (-167.19138152692128, -298.5111993693906),\n",
" (-176.76438637860946, -296.3517909629941),\n",
" (-186.0796355585698, -293.26446213837716),\n",
" (-195.04741812496607, -289.2789455598266),\n",
" (-203.58136942939524, -284.4336239306988),\n",
" (-211.59930285566332, -278.7751603470045),\n",
" (-219.02400132182714, -272.3580489062855),\n",
" (-225.78396092290453, -265.2440898996658),\n",
" (-231.8140795525672, -257.50179464126495),\n",
" (-237.0562838720134, -249.20572566679022),\n",
" (-241.46008858796648, -240.4357786555585),\n",
" (-244.98308265364727, -231.27641299142869),\n",
" (-247.59133771033882, -221.8158383727649),\n",
" (-249.25973483602792, -212.145165304821),\n",
" (-249.97220645435553, -202.35752765576902),\n",
" (-249.72189107416057, -192.54718572663626),\n",
" (-248.51119936939062, -182.8086184730787),\n",
" (-246.35179096299407, -173.23561362139054),\n",
" (-196.35179096299407, 6.7643863786094585),\n",
" (-193.32576660256726, 15.920764023655508),\n",
" (-189.43184924301974, 24.74309266215056),\n",
" (-184.7062507874361, 33.14932810051302),\n",
" (-30.55144070299677, 259.2576189250935),\n",
" (-24.412520344941953, 266.8040179623472),\n",
" (-17.56940095820731, 273.7182206387879),\n",
" (-10.086842048356445, 279.93479475582495),\n",
" (-2.0356544237308825, 285.394910086574),\n",
" (6.507969918963688, 290.0468951126591),\n",
" (15.463178833668529, 293.8467260149487),\n",
" (24.745225165064543, 296.758443290685),\n",
" (34.26626874888323, 298.7544920543751),\n",
" (43.93620768274765, 299.8159828020204),\n",
" (53.66353100085455, 299.9328701709592),\n",
" (63.35618468325523, 299.10404800363494),\n",
" (72.92244280430123, 297.33735981566144),\n",
" (82.27177557618647, 294.64952456911897),\n",
" (91.31570607290114, 291.0659784535237),\n",
" (99.96864752703414, 286.6206341717666),\n",
" (108.14871327570971, 281.355560009008),\n",
" (115.77849169077639, 275.3205817216414),\n",
" (122.78577875973701, 268.57281101383126),\n",
" (129.10426138467784, 261.17610506386103),\n",
" (134.67414493283295, 253.20046221503722),\n",
" (139.44271909999156, 244.72135954999587),\n",
" (189.4427190999916, 144.72135954999578),\n",
" (193.40316487178438, 135.7190256296874),\n",
" (196.46014848027284, 126.37119176608674),\n",
" (198.5841005952538, 116.76827688896145),\n",
" (199.75447683394128, 107.00316725394137),\n",
" (199.959956480919, 97.1703179802708),\n",
" (199.19855199019082, 87.36483941339068),\n",
"])\n",
"p"
]
},
{
"cell_type": "code",
"execution_count": 330,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(69, False)"
]
},
"execution_count": 330,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"len(p.exterior.coords), p.exterior.is_ccw"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"300\" height=\"300\" viewBox=\"-128.0 -128.0 756.0 756.0\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,500.0)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"5.04\" opacity=\"0.6\" d=\"M 0.0,-100.0 L -9.80171403296,-99.5184726672 L -19.5090322016,-98.0785280403 L -29.0284677254,-95.6940335732 L -38.2683432365,-92.3879532511 L -47.1396736826,-88.1921264348 L -55.557023302,-83.1469612303 L -63.4393284164,-77.3010453363 L -70.7106781187,-70.7106781187 L -77.3010453363,-63.4393284164 L -83.1469612303,-55.557023302 L -88.1921264348,-47.1396736826 L -92.3879532511,-38.2683432365 L -95.6940335732,-29.0284677254 L -98.0785280403,-19.5090322016 L -99.5184726672,-9.80171403296 L -100.0,0.0 L -100.0,500.0 L -99.5184726672,509.801714033 L -98.0785280403,519.509032202 L -95.6940335732,529.028467725 L -92.3879532511,538.268343237 L -88.1921264348,547.139673683 L -83.1469612303,555.557023302 L -77.3010453363,563.439328416 L -70.7106781187,570.710678119 L -63.4393284164,577.301045336 L -55.557023302,583.14696123 L -47.1396736826,588.192126435 L -38.2683432365,592.387953251 L -29.0284677254,595.694033573 L -19.5090322016,598.07852804 L -9.80171403296,599.518472667 L 0.0,600.0 L 500.0,600.0 L 509.801714033,599.518472667 L 519.509032202,598.07852804 L 529.028467725,595.694033573 L 538.268343237,592.387953251 L 547.139673683,588.192126435 L 555.557023302,583.14696123 L 563.439328416,577.301045336 L 570.710678119,570.710678119 L 577.301045336,563.439328416 L 583.14696123,555.557023302 L 588.192126435,547.139673683 L 592.387953251,538.268343237 L 595.694033573,529.028467725 L 598.07852804,519.509032202 L 599.518472667,509.801714033 L 600.0,500.0 L 599.518472667,490.198285967 L 598.07852804,480.490967798 L 595.694033573,470.971532275 L 592.387953251,461.731656763 L 588.192126435,452.860326317 L 583.14696123,444.442976698 L 577.301045336,436.560671584 L 570.710678119,429.289321881 L 563.439328416,422.698954664 L 555.557023302,416.85303877 L 547.139673683,411.807873565 L 538.268343237,407.612046749 L 529.028467725,404.305966427 L 519.509032202,401.92147196 L 509.801714033,400.481527333 L 500.0,400.0 L 100.0,400.0 L 100.0,100.0 L 500.0,100.0 L 509.801714033,99.5184726672 L 519.509032202,98.0785280403 L 529.028467725,95.6940335732 L 538.268343237,92.3879532511 L 547.139673683,88.1921264348 L 555.557023302,83.1469612303 L 563.439328416,77.3010453363 L 570.710678119,70.7106781187 L 577.301045336,63.4393284164 L 583.14696123,55.557023302 L 588.192126435,47.1396736826 L 592.387953251,38.2683432365 L 595.694033573,29.0284677254 L 598.07852804,19.5090322016 L 599.518472667,9.80171403296 L 600.0,0.0 L 599.518472667,-9.80171403296 L 598.07852804,-19.5090322016 L 595.694033573,-29.0284677254 L 592.387953251,-38.2683432365 L 588.192126435,-47.1396736826 L 583.14696123,-55.557023302 L 577.301045336,-63.4393284164 L 570.710678119,-70.7106781187 L 563.439328416,-77.3010453363 L 555.557023302,-83.1469612303 L 547.139673683,-88.1921264348 L 538.268343237,-92.3879532511 L 529.028467725,-95.6940335732 L 519.509032202,-98.0785280403 L 509.801714033,-99.5184726672 L 500.0,-100.0 L 0.0,-100.0 z\" /></g></svg>"
],
"text/plain": [
"<shapely.geometry.polygon.Polygon at 0x104ef1190>"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"a = Polygon(\n",
"[\n",
" (0.0, -100.0),\n",
" (-9.801714032956664, -99.51847266721963),\n",
" (-19.509032201613387, -98.07852804032294),\n",
" (-29.02846772544675, -95.69403357322072),\n",
" (-38.268343236509445, -92.38795325112848),\n",
" (-47.13967368260018, -88.19212643483529),\n",
" (-55.5570233019606, -83.14696123025428),\n",
" (-63.439328416364795, -77.30104533627349),\n",
" (-70.710678118655, -70.71067811865453),\n",
" (-77.30104533627389, -63.439328416364326),\n",
" (-83.14696123025468, -55.55702330196001),\n",
" (-88.1921264348356, -47.13967368259957),\n",
" (-92.38795325112875, -38.2683432365088),\n",
" (-95.69403357322092, -29.028467725446088),\n",
" (-98.07852804032306, -19.509032201612705),\n",
" (-99.5184726672197, -9.80171403295597),\n",
" (-100.0, 0.0),\n",
" (-100.0, 500.0),\n",
" (-99.51847266721968, 509.80171403295606),\n",
" (-98.07852804032305, 519.5090322016129),\n",
" (-95.69403357322088, 529.0284677254463),\n",
" (-92.38795325112868, 538.2683432365089),\n",
" (-88.1921264348355, 547.1396736825998),\n",
" (-83.14696123025453, 555.5570233019603),\n",
" (-77.3010453362737, 563.4393284163646),\n",
" (-70.71067811865474, 570.7106781186548),\n",
" (-63.439328416364525, 577.3010453362738),\n",
" (-55.55702330196019, 583.1469612302545),\n",
" (-47.13967368259977, 588.1921264348355),\n",
" (-38.268343236508976, 592.3879532511287),\n",
" (-29.028467725446223, 595.6940335732208),\n",
" (-19.5090322016128, 598.078528040323),\n",
" (-9.80171403295602, 599.5184726672197),\n",
" (0.0, 600.0),\n",
" (500.0, 600.0),\n",
" (509.8017140329562, 599.5184726672196),\n",
" (519.509032201613, 598.078528040323),\n",
" (529.0284677254464, 595.6940335732208),\n",
" (538.268343236509, 592.3879532511287),\n",
" (547.1396736825999, 588.1921264348355),\n",
" (555.5570233019603, 583.1469612302544),\n",
" (563.4393284163647, 577.3010453362737),\n",
" (570.7106781186549, 570.7106781186546),\n",
" (577.3010453362738, 563.4393284163644),\n",
" (583.1469612302545, 555.5570233019602),\n",
" (588.1921264348355, 547.1396736825997),\n",
" (592.3879532511287, 538.2683432365089),\n",
" (595.6940335732208, 529.0284677254463),\n",
" (598.078528040323, 519.5090322016129),\n",
" (599.5184726672197, 509.80171403295606),\n",
" (600.0, 500.0),\n",
" (599.5184726672197, 490.19828596704394),\n",
" (598.078528040323, 480.4909677983872),\n",
" (595.6940335732208, 470.9715322745538),\n",
" (592.3879532511287, 461.73165676349106),\n",
" (588.1921264348355, 452.8603263174003),\n",
" (583.1469612302545, 444.44297669803984),\n",
" (577.3010453362738, 436.5606715836355),\n",
" (570.7106781186548, 429.28932188134524),\n",
" (563.4393284163646, 422.69895466372634),\n",
" (555.5570233019603, 416.85303876974547),\n",
" (547.1396736825998, 411.8078735651645),\n",
" (538.2683432365089, 407.6120467488713),\n",
" (529.0284677254463, 404.3059664267791),\n",
" (519.5090322016127, 401.921471959677),\n",
" (509.801714032956, 400.4815273327803),\n",
" (500.0, 400.0),\n",
" (100.0, 400.0),\n",
" (100.0, 100.0),\n",
" (500.0, 100.0),\n",
" (509.8017140329562, 99.51847266721967),\n",
" (519.509032201613, 98.07852804032302),\n",
" (529.0284677254464, 95.69403357322085),\n",
" (538.268343236509, 92.38795325112864),\n",
" (547.1396736825999, 88.19212643483544),\n",
" (555.5570233019603, 83.14696123025446),\n",
" (563.4393284163647, 77.30104533627363),\n",
" (570.7106781186549, 70.7106781186547),\n",
" (577.3010453362738, 63.439328416364496),\n",
" (583.1469612302545, 55.55702330196017),\n",
" (588.1921264348355, 47.139673682599714),\n",
" (592.3879532511287, 38.26834323650893),\n",
" (595.6940335732208, 29.028467725446205),\n",
" (598.078528040323, 19.509032201612804),\n",
" (599.5184726672197, 9.801714032956049),\n",
" (600.0, 0.0),\n",
" (599.5184726672197, -9.801714032956049),\n",
" (598.078528040323, -19.509032201612804),\n",
" (595.6940335732208, -29.028467725446205),\n",
" (592.3879532511287, -38.26834323650893),\n",
" (588.1921264348355, -47.139673682599714),\n",
" (583.1469612302545, -55.557023301960186),\n",
" (577.3010453362738, -63.439328416364525),\n",
" (570.7106781186548, -70.71067811865474),\n",
" (563.4393284163646, -77.30104533627369),\n",
" (555.5570233019603, -83.14696123025452),\n",
" (547.1396736825998, -88.1921264348355),\n",
" (538.2683432365089, -92.38795325112868),\n",
" (529.0284677254463, -95.69403357322089),\n",
" (519.5090322016127, -98.07852804032305),\n",
" (509.801714032956, -99.5184726672197),\n",
" (500.0, -100.0),\n",
" (0.0, -100.0)\n",
"])\n",
"a"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"sa = set(a.convex_hull.exterior.coords)"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"300\" height=\"300\" viewBox=\"-128.0 -128.0 756.0 756.0\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,500.0)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"5.04\" opacity=\"0.6\" d=\"M 600.0,0.0 L 599.518472667,-9.80171403296 L 598.07852804,-19.5090322016 L 595.694033573,-29.0284677254 L 592.387953251,-38.2683432365 L 588.192126435,-47.1396736826 L 583.14696123,-55.557023302 L 577.301045336,-63.4393284164 L 570.710678119,-70.7106781187 L 563.439328416,-77.3010453363 L 555.557023302,-83.1469612303 L 547.139673683,-88.1921264348 L 538.268343237,-92.3879532511 L 529.028467725,-95.6940335732 L 519.509032202,-98.0785280403 L 509.801714033,-99.5184726672 L 500.0,-100.0 L 0.0,-100.0 L -9.80171403296,-99.5184726672 L -19.5090322016,-98.0785280403 L -29.0284677254,-95.6940335732 L -38.2683432365,-92.3879532511 L -47.1396736826,-88.1921264348 L -55.557023302,-83.1469612303 L -63.4393284164,-77.3010453363 L -70.7106781187,-70.7106781187 L -77.3010453363,-63.4393284164 L -83.1469612303,-55.557023302 L -88.1921264348,-47.1396736826 L -92.3879532511,-38.2683432365 L -95.6940335732,-29.0284677254 L -98.0785280403,-19.5090322016 L -99.5184726672,-9.80171403296 L -100.0,0.0 L -100.0,500.0 L -99.5184726672,509.801714033 L -98.0785280403,519.509032202 L -95.6940335732,529.028467725 L -92.3879532511,538.268343237 L -88.1921264348,547.139673683 L -83.1469612303,555.557023302 L -77.3010453363,563.439328416 L -70.7106781187,570.710678119 L -63.4393284164,577.301045336 L -55.557023302,583.14696123 L -47.1396736826,588.192126435 L -38.2683432365,592.387953251 L -29.0284677254,595.694033573 L -19.5090322016,598.07852804 L -9.80171403296,599.518472667 L 0.0,600.0 L 500.0,600.0 L 509.801714033,599.518472667 L 519.509032202,598.07852804 L 529.028467725,595.694033573 L 538.268343237,592.387953251 L 547.139673683,588.192126435 L 555.557023302,583.14696123 L 563.439328416,577.301045336 L 570.710678119,570.710678119 L 577.301045336,563.439328416 L 583.14696123,555.557023302 L 588.192126435,547.139673683 L 592.387953251,538.268343237 L 595.694033573,529.028467725 L 598.07852804,519.509032202 L 599.518472667,509.801714033 L 600.0,500.0 L 600.0,0.0 z\" /></g></svg>"
],
"text/plain": [
"<shapely.geometry.polygon.Polygon at 0x104ef1810>"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# rust convex hull\n",
"b = Polygon([\n",
" (600, 0),\n",
" (599.5184726672197, -9.801714032956049),\n",
" (598.078528040323, -19.509032201612804),\n",
" (595.6940335732208, -29.028467725446205),\n",
" (592.3879532511287, -38.26834323650893),\n",
" (588.1921264348355, -47.139673682599714),\n",
" (583.1469612302545, -55.557023301960186),\n",
" (577.3010453362738, -63.439328416364525),\n",
" (570.7106781186548, -70.71067811865474),\n",
" (563.4393284163646, -77.30104533627369),\n",
" (555.5570233019603, -83.14696123025452),\n",
" (547.1396736825998, -88.1921264348355),\n",
" (538.2683432365089, -92.38795325112868),\n",
" (529.0284677254463, -95.69403357322089),\n",
" (519.5090322016127, -98.07852804032305),\n",
" (509.801714032956, -99.5184726672197),\n",
" (500, -100),\n",
" (0, -100),\n",
" (-9.801714032956664, -99.51847266721963),\n",
" (-19.509032201613387, -98.07852804032294),\n",
" (-29.02846772544675, -95.69403357322072),\n",
" (-38.268343236509445, -92.38795325112848),\n",
" (-47.13967368260018, -88.19212643483529),\n",
" (-55.5570233019606, -83.14696123025428),\n",
" (-63.439328416364795, -77.30104533627349),\n",
" (-70.710678118655, -70.71067811865453),\n",
" (-77.30104533627389, -63.439328416364326),\n",
" (-83.14696123025468, -55.55702330196001),\n",
" (-88.1921264348356, -47.13967368259957),\n",
" (-92.38795325112875, -38.2683432365088),\n",
" (-95.69403357322092, -29.028467725446088),\n",
" (-98.07852804032306, -19.509032201612705),\n",
" (-99.5184726672197, -9.80171403295597),\n",
" (-100, 0),\n",
" (-100, 500),\n",
" (-99.51847266721968, 509.80171403295606),\n",
" (-98.07852804032305, 519.5090322016129),\n",
" (-95.69403357322088, 529.0284677254463),\n",
" (-92.38795325112868, 538.2683432365089),\n",
" (-88.1921264348355, 547.1396736825998),\n",
" (-83.14696123025453, 555.5570233019603),\n",
" (-77.3010453362737, 563.4393284163646),\n",
" (-70.71067811865474, 570.7106781186548),\n",
" (-63.439328416364525, 577.3010453362738),\n",
" (-55.55702330196019, 583.1469612302545),\n",
" (-47.13967368259977, 588.1921264348355),\n",
" (-38.268343236508976, 592.3879532511287),\n",
" (-29.028467725446223, 595.6940335732208),\n",
" (-19.5090322016128, 598.078528040323),\n",
" (-9.80171403295602, 599.5184726672197),\n",
" (0, 600),\n",
" (500, 600),\n",
" (509.8017140329562, 599.5184726672196),\n",
" (519.509032201613, 598.078528040323),\n",
" (529.0284677254464, 595.6940335732208),\n",
" (538.268343236509, 592.3879532511287),\n",
" (547.1396736825999, 588.1921264348355),\n",
" (555.5570233019603, 583.1469612302544),\n",
" (563.4393284163647, 577.3010453362737),\n",
" (570.7106781186549, 570.7106781186546),\n",
" (577.3010453362738, 563.4393284163644),\n",
" (583.1469612302545, 555.5570233019602),\n",
" (588.1921264348355, 547.1396736825997),\n",
" (592.3879532511287, 538.2683432365089),\n",
" (595.6940335732208, 529.0284677254463),\n",
" (598.078528040323, 519.5090322016129),\n",
" (599.5184726672197, 509.80171403295606),\n",
" (600, 500),\n",
" (600, 0),\n",
"])\n",
"b"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"sb = set(b.exterior.coords)"
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 18,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"sa == sb"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"-10.8 -10.8 21.6 21.6\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,0.0)\"><polyline fill=\"none\" stroke=\"#66cc99\" stroke-width=\"0.432\" points=\"0.0,10.0 1.0,1.0 10.0,0.0 1.0,-1.0 0.0,-10.0 -1.0,-1.0 -10.0,0.0 -1.0,1.0 0.0,10.0\" opacity=\"0.8\" /></g></svg>"
],
"text/plain": [
"<shapely.geometry.linestring.LineString at 0x104ee6150>"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ls = LineString([\n",
" (0.0, 10.0),\n",
" (1.0, 1.0),\n",
" (10.0, 0.0),\n",
" (1.0, -1.0),\n",
" (0.0, -10.0),\n",
" (-1.0, -1.0),\n",
" (-10.0, 0.0),\n",
" (-1.0, 1.0),\n",
" (0.0, 10.0)\n",
"])\n",
"ls"
]
},
{
"cell_type": "code",
"execution_count": 27,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"-0.4 -0.4 5.8 10.8\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,10.0)\"><g><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.216\" opacity=\"0.6\" d=\"M 0.0,0.0 L 1.0,10.0 L 2.0,0.0 L 0.0,0.0 z\" /><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.216\" opacity=\"0.6\" d=\"M 3.0,0.0 L 4.0,10.0 L 5.0,0.0 L 3.0,0.0 z\" /></g></g></svg>"
],
"text/plain": [
"<shapely.geometry.multipolygon.MultiPolygon at 0x105059290>"
]
},
"execution_count": 27,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"mp = MultiPolygon(polygons=[\n",
" Polygon([(0.0, 0.0), (1.0, 10.0), (2.0, 0.0), (0.0, 0.0)]),\n",
" Polygon([(3.0, 0.0), (4.0, 10.0), (5.0, 0.0), (3.0, 0.0)])\n",
"])\n",
"mp"
]
},
{
"cell_type": "code",
"execution_count": 28,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 28,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"mp.is_valid"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"60.959002616512684"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"p = Point(50, 50.)\n",
"p.distance(mp)"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"60.959002616512684"
]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"mp.distance(p)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
" let v1 = LineString(vec![Point::new(0.0, 0.0), Point::new(1.0, 10.0)]);\n",
" let v2 = LineString(vec![Point::new(1.0, 10.0), Point::new(2.0, 0.0), Point::new(3.0, 1.0)]);"
]
},
{
"cell_type": "code",
"execution_count": 32,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"-0.4 -0.4 3.8 10.8\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,10.0)\"><g><polyline fill=\"none\" stroke=\"#66cc99\" stroke-width=\"0.216\" points=\"0.0,0.0 1.0,10.0\" opacity=\"0.8\" /><polyline fill=\"none\" stroke=\"#66cc99\" stroke-width=\"0.216\" points=\"1.0,10.0 2.0,0.0 3.0,1.0\" opacity=\"0.8\" /></g></g></svg>"
],
"text/plain": [
"<shapely.geometry.multilinestring.MultiLineString at 0x105059750>"
]
},
"execution_count": 32,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"mls = MultiLineString(lines=[\n",
" LineString([(0.0, 0.0), (1.0, 10.0)]),\n",
" LineString([(1.0, 10.0), (2.0, 0.0), (3.0, 1.0)])\n",
"])\n",
"mls"
]
},
{
"cell_type": "code",
"execution_count": 33,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"63.25345840347388"
]
},
"execution_count": 33,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"p.distance(mls)"
]
},
{
"cell_type": "code",
"execution_count": 36,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"-10.8 -10.8 21.6 21.6\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,0.0)\"><g><circle cx=\"0.0\" cy=\"10.0\" r=\"0.648\" stroke=\"#555555\" stroke-width=\"0.216\" fill=\"#66cc99\" opacity=\"0.6\" /><circle cx=\"1.0\" cy=\"1.0\" r=\"0.648\" stroke=\"#555555\" stroke-width=\"0.216\" fill=\"#66cc99\" opacity=\"0.6\" /><circle cx=\"10.0\" cy=\"0.0\" r=\"0.648\" stroke=\"#555555\" stroke-width=\"0.216\" fill=\"#66cc99\" opacity=\"0.6\" /><circle cx=\"1.0\" cy=\"-1.0\" r=\"0.648\" stroke=\"#555555\" stroke-width=\"0.216\" fill=\"#66cc99\" opacity=\"0.6\" /><circle cx=\"0.0\" cy=\"-10.0\" r=\"0.648\" stroke=\"#555555\" stroke-width=\"0.216\" fill=\"#66cc99\" opacity=\"0.6\" /><circle cx=\"-1.0\" cy=\"-1.0\" r=\"0.648\" stroke=\"#555555\" stroke-width=\"0.216\" fill=\"#66cc99\" opacity=\"0.6\" /><circle cx=\"-10.0\" cy=\"0.0\" r=\"0.648\" stroke=\"#555555\" stroke-width=\"0.216\" fill=\"#66cc99\" opacity=\"0.6\" /><circle cx=\"-1.0\" cy=\"1.0\" r=\"0.648\" stroke=\"#555555\" stroke-width=\"0.216\" fill=\"#66cc99\" opacity=\"0.6\" /><circle cx=\"0.0\" cy=\"10.0\" r=\"0.648\" stroke=\"#555555\" stroke-width=\"0.216\" fill=\"#66cc99\" opacity=\"0.6\" /></g></g></svg>"
],
"text/plain": [
"<shapely.geometry.multipoint.MultiPoint at 0x1050508d0>"
]
},
"execution_count": 36,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"mpoint = MultiPoint(points=[\n",
" Point(0.0, 10.0),\n",
" Point(1.0, 1.0),\n",
" Point(10.0, 0.0),\n",
" Point(1.0, -1.0),\n",
" Point(0.0, -10.0),\n",
" Point(-1.0, -1.0),\n",
" Point(-10.0, 0.0),\n",
" Point(-1.0, 1.0),\n",
" Point(0.0, 10.0)]\n",
" )\n",
"mpoint"
]
},
{
"cell_type": "code",
"execution_count": 37,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"64.03124237432849"
]
},
"execution_count": 37,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"p.distance(mpoint)"
]
},
{
"cell_type": "code",
"execution_count": 153,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2.0"
]
},
"execution_count": 153,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Polygon([(5., 1.), (4., 2.), (4., 3.), (5., 4.), (6., 4.), (7., 3.), (7., 2.), (6., 1.), (5., 1.)]).distance(\n",
" Polygon([(10., 1.), (9., 2.), (9., 3.), (10., 5.), (11., 4.), (12., 3.),(12., 2.), (11., 1.), (10., 1.)]))"
]
},
{
"cell_type": "code",
"execution_count": 226,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"rotated = rotate(LineString([(6., 1.), (3., 1.)]), -45., origin=Point(6., 1.))\n",
"rotated2 = rotate(LineString([(10., 5. ), (14., 5.)]), -45., origin=Point(10., 5.))\n",
"\n",
"rotated3 = rotate(LineString([(6., 1.), (3., 1.)]), -0., origin=Point(6., 1.))"
]
},
{
"cell_type": "code",
"execution_count": 35,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"-35.2 -20.2 86.4 46.4\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,6.0)\"><g><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"1.728\" opacity=\"0.6\" d=\"M -22.0,-17.0 L -32.0,-7.0 L -32.0,3.0 L -22.0,13.0 L -12.0,13.0 L -2.0,3.0 L -2.0,-7.0 L -12.0,-17.0 L -22.0,-17.0 z\" /><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"1.728\" opacity=\"0.6\" d=\"M 28.0,-17.0 L 18.0,-7.0 L 18.0,3.0 L 28.0,23.0 L 38.0,13.0 L 48.0,3.0 L 48.0,-7.0 L 38.0,-17.0 L 28.0,-17.0 z\" /></g></g></svg>"
],
"text/plain": [
"<shapely.geometry.collection.GeometryCollection at 0x106d42650>"
]
},
"execution_count": 35,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"gc = GeometryCollection([\n",
" # polygon P\n",
" Polygon([(5., 1.), (4., 2.), (4., 3.), (5., 4.), (6., 4.), (7., 3.), (7., 2.), (6., 1.), (5., 1.)]),\n",
" # polygon Q\n",
" Polygon([(10., 1.), (9., 2.), (9., 3.), (10., 5.), (11., 4.), (12., 3.),(12., 2.), (11., 1.), (10., 1.)]),\n",
" # Lower line of support\n",
"# LineString([(6., 1.), (3., 1.)]),\n",
" # Upper line of support\n",
"# LineString([(10., 5. ), (14., 5.)]),\n",
" # poly1 ymin\n",
"# Point(6., 1.),\n",
" # poly2 ymax\n",
"# Point(10., 5.),\n",
" # line pq - need to work out the angle between poly1_ymin\n",
"# LineString([(6., 1), (10., 5.)]),\n",
"# rotated,\n",
"# rotated2,\n",
"# rotated3,\n",
"# Point(4., 3.),\n",
"# Point(12., 3.),\n",
"])\n",
"scale(gc, 10., 10.)"
]
},
{
"cell_type": "code",
"execution_count": 152,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# we've rotated 45 degrees\n",
"# we've hit two vertices p` (4., 3.) and q` (12., 3.)\n",
"# this implies parallel edges between P and Q\n",
"# calculate p_perp and q_perp and see if they intersect with the polygons:\n",
" # segment [p, p_perp] and edge [(10., 5), (12., 3.)] ([qj, q`])\n",
" # edge [(6., 1.), (4., 3.)] ([pi, p`]) and segment [q, q_perp]\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# then the vertex-edge anti-podal pair distance should be computed\n",
"# along with the new vertex-vertex anti-podal pair distance. "
]
},
{
"cell_type": "code",
"execution_count": 236,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"3.88 0.88 3.24 3.24\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,5.0)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.0648\" opacity=\"0.6\" d=\"M 5.0,1.0 L 4.0,2.0 L 4.0,3.0 L 5.0,4.0 L 6.0,4.0 L 7.0,3.0 L 7.0,2.0 L 6.0,1.0 L 5.0,1.0 z\" /></g></svg>"
],
"text/plain": [
"<shapely.geometry.polygon.Polygon at 0x104fb0dd0>"
]
},
"execution_count": 236,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ccw = Polygon([\n",
" (5., 1.), (4., 2.), (4., 3.), (5., 4.), (6., 4.), (7., 3.),\n",
" (7., 2.), (6., 1.), (5., 1.)\n",
"])\n",
"ccw"
]
},
{
"cell_type": "code",
"execution_count": 237,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(5.0, 1.0),\n",
" (6.0, 1.0),\n",
" (7.0, 2.0),\n",
" (7.0, 3.0),\n",
" (6.0, 4.0),\n",
" (5.0, 4.0),\n",
" (4.0, 3.0),\n",
" (4.0, 2.0),\n",
" (5.0, 1.0)]"
]
},
"execution_count": 237,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"list(orient(ccw).exterior.coords)"
]
},
{
"cell_type": "code",
"execution_count": 241,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"3.88 0.88 3.24 3.24\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,5.0)\"><g><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.0648\" opacity=\"0.6\" d=\"M 5.0,1.0 L 4.0,2.0 L 4.0,3.0 L 5.0,4.0 L 6.0,4.0 L 7.0,3.0 L 7.0,2.0 L 6.0,1.0 L 5.0,1.0 z\" /><circle cx=\"5.0\" cy=\"1.0\" r=\"0.0972\" stroke=\"#555555\" stroke-width=\"0.0324\" fill=\"#66cc99\" opacity=\"0.6\" /><circle cx=\"7.0\" cy=\"2.0\" r=\"0.0972\" stroke=\"#555555\" stroke-width=\"0.0324\" fill=\"#66cc99\" opacity=\"0.6\" /><circle cx=\"6.0\" cy=\"4.0\" r=\"0.0972\" stroke=\"#555555\" stroke-width=\"0.0324\" fill=\"#66cc99\" opacity=\"0.6\" /></g></g></svg>"
],
"text/plain": [
"<shapely.geometry.collection.GeometryCollection at 0x104fb0f90>"
]
},
"execution_count": 241,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"GeometryCollection([\n",
" ccw,\n",
" # some sort of minimum? (0.0, 1.0)\n",
" # (0.0, -1.0)\n",
" # (-1.0, 0.0)\n",
" Point(5., 1.),\n",
" # some sort of maximum (1.0, 0.0)\n",
" Point(7., 2.0),\n",
" # (90, 90)\n",
" Point(6., 4.0)\n",
"])"
]
},
{
"cell_type": "code",
"execution_count": 244,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(5.5, 2.5)]"
]
},
"execution_count": 244,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"list(ccw.centroid.coords)"
]
},
{
"cell_type": "code",
"execution_count": 250,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"-0.08 -0.08 2.16 2.16\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,2.0)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.0432\" opacity=\"0.6\" d=\"M 1.0,0.0 L 2.0,1.0 L 1.0,2.0 L 0.0,1.0 L 1.0,0.0 z\" /></g></svg>"
],
"text/plain": [
"<shapely.geometry.polygon.Polygon at 0x104fb2c50>"
]
},
"execution_count": 250,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ell = Polygon([(1.0, 0.0), (2.0, 1.0), (1.0, 2.0), (0.0, 1.0), (1.0, 0.0)])\n",
"ell"
]
},
{
"cell_type": "code",
"execution_count": 258,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(1.0, 0.0), (2.0, 1.0), (1.0, 2.0), (0.0, 1.0), (1.0, 0.0)]"
]
},
"execution_count": 258,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"list(orient(ell).exterior.coords)"
]
},
{
"cell_type": "code",
"execution_count": 254,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(1.0, 1.0)]"
]
},
"execution_count": 254,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"list(ell.centroid.coords)"
]
},
{
"cell_type": "code",
"execution_count": 291,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"-0.08 -0.08 2.16 2.16\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,2.0)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.0432\" opacity=\"0.6\" d=\"M 1.0,0.0 L 2.0,1.0 L 1.75,1.1 L 1.0,2.0 L 0.0,1.0 L 1.0,0.0 z M 1.0,0.5 L 1.5,1.0 L 1.0,1.5 L 0.5,1.0 L 1.0,0.5 z\" /></g></svg>"
],
"text/plain": [
"<shapely.geometry.polygon.Polygon at 0x104fb32d0>"
]
},
"execution_count": 291,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"shelled = Polygon(\n",
" [(1.0, 0.0), (2.0, 1.0), (1.75, 1.1), (1.0, 2.0), (0.0, 1.0), (1.0, 0.0)],\n",
" holes=[[(1.0, 0.5), (1.5, 1.0), (1.0, 1.5), (0.5, 1.0), (1.0, 0.5)]]\n",
" \n",
")\n",
"shelled"
]
},
{
"cell_type": "code",
"execution_count": 275,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(1.0, 0.5), (1.5, 1.0), (1.0, 1.5), (0.5, 1.0), (1.0, 0.5)]"
]
},
"execution_count": 275,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"shelled_oriented = orient(shelled, sign=1)\n",
"list(shelled.interiors[0].coords)"
]
},
{
"cell_type": "code",
"execution_count": 277,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(1.0, 0.5), (0.5, 1.0), (1.0, 1.5), (1.5, 1.0), (1.0, 0.5)]"
]
},
"execution_count": 277,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# wrong\n",
"list(orient(Polygon([(1.0, 0.5), (1.5, 1.0), (1.0, 1.5), (0.5, 1.0), (1.0, 0.5)]), sign=-1).exterior.coords)"
]
},
{
"cell_type": "code",
"execution_count": 297,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"ccw = Polygon([(0, 10), (-10, 0), (0, -10), (10, 0), (0, 10)])"
]
},
{
"cell_type": "code",
"execution_count": 298,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 298,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ccw.exterior.is_ccw"
]
},
{
"cell_type": "code",
"execution_count": 299,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"-10.8 -10.8 21.6 21.6\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,0.0)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.432\" opacity=\"0.6\" d=\"M 0.0,10.0 L -10.0,0.0 L 0.0,-10.0 L 10.0,0.0 L 0.0,10.0 z\" /></g></svg>"
],
"text/plain": [
"<shapely.geometry.polygon.Polygon at 0x104fb0e10>"
]
},
"execution_count": 299,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"ccw"
]
},
{
"cell_type": "code",
"execution_count": 308,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(0.0, 0.0), (0.0, 2.0), (1.75, 2.5), (2.5, 1.75), (2.0, 0.0), (0.0, 0.0)]"
]
},
"execution_count": 308,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"spike = Polygon([(0, 0), (2, 0), (2.5, 1.75), (2.3, 1.7), (1.75, 2.5), (1.3, 2), (0, 2), (0, 0)])\n",
"list(spike.convex_hull.exterior.coords)"
]
},
{
"cell_type": "code",
"execution_count": 307,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"-0.1 -0.1 2.7 2.7\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,2.5)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.054\" opacity=\"0.6\" d=\"M 0.0,0.0 L 0.0,2.0 L 1.75,2.5 L 2.5,1.75 L 2.0,0.0 L 0.0,0.0 z\" /></g></svg>"
],
"text/plain": [
"<shapely.geometry.polygon.Polygon at 0x104f55750>"
]
},
"execution_count": 307,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"spike.convex_hull"
]
},
{
"cell_type": "code",
"execution_count": 316,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(0.0, 0.0), (2.0, 0.0), (2.5, 1.75), (1.75, 2.5), (0.0, 2.0), (0.0, 0.0)]"
]
},
"execution_count": 316,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"list(orient(spike.convex_hull).exterior.coords)"
]
},
{
"cell_type": "code",
"execution_count": 53,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"3.88 0.88 3.24 3.24\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,5.0)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.0648\" opacity=\"0.6\" d=\"M 5.0,1.0 L 4.0,2.0 L 4.0,3.0 L 5.0,4.0 L 6.0,4.0 L 7.0,3.0 L 7.0,2.0 L 6.0,1.0 L 5.0,1.0 z M 5.0,1.3 L 5.5,2.0 L 6.0,1.3 L 5.0,1.3 z M 5.0,2.3 L 5.5,3.0 L 6.0,2.3 L 5.0,2.3 z\" /></g></svg>"
],
"text/plain": [
"<shapely.geometry.polygon.Polygon at 0x105039d50>"
]
},
"execution_count": 53,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"rotate_ = Polygon(\n",
" [(5., 1.), (4., 2.), (4., 3.), (5., 4.), (6., 4.), (7., 3.),(7., 2.), (6., 1.), (5., 1.)],\n",
" holes=[\n",
" [(5., 1.3), (5.5, 2.0), (6.0, 1.3), (5., 1.3)],\n",
" [(5., 2.3), (5.5, 3.0), (6., 2.3), (5., 2.3)]\n",
" ]\n",
")\n",
"rotate_"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"-0.08 -0.08 2.16 2.16\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,2.0)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.0432\" opacity=\"0.6\" d=\"M 0.0,0.0 L 2.0,0.0 L 1.0,1.0 L 2.0,2.0 L 0.0,2.0 L 0.0,0.0 z\" /></g></svg>"
],
"text/plain": [
"<shapely.geometry.polygon.Polygon at 0x106c4b4d0>"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"p = Polygon(\n",
" [(0., 0.), (2.,0), (1.0, 1.0), (2., 2.), (0., 2.), (0., 0.)]\n",
")\n",
"p"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"scrolled": true
},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"1.068 -0.132 3.564 2.264\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,2.0)\"><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.07128\" opacity=\"0.6\" d=\"M 4.5,2.0 L 4.5,0.0 L 2.5,0.0 L 2.5,0.8 L 1.2,1.0 L 2.5,1.2 L 2.5,2.0 L 4.5,2.0 z\" /></g></svg>"
],
"text/plain": [
"<shapely.geometry.polygon.Polygon at 0x106c4b6d0>"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"q = Polygon([(4.5, 2.), (4.5, 0.), (2.5, 0.), (2.5, 0.8), (1.2, 1.0), (2.5, 1.2), (2.5, 2.), (4.5, 2.)])\n",
"q"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"-0.18 -0.18 4.86 2.36\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,2.0)\"><g><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.0972\" opacity=\"0.6\" d=\"M 0.0,0.0 L 2.0,0.0 L 1.0,1.0 L 2.0,2.0 L 0.0,2.0 L 0.0,0.0 z\" /><path fill-rule=\"evenodd\" fill=\"#66cc99\" stroke=\"#555555\" stroke-width=\"0.0972\" opacity=\"0.6\" d=\"M 4.5,2.0 L 4.5,0.0 L 2.5,0.0 L 2.5,0.8 L 1.2,1.0 L 2.5,1.2 L 2.5,2.0 L 4.5,2.0 z\" /></g></g></svg>"
],
"text/plain": [
"<shapely.geometry.collection.GeometryCollection at 0x103afd750>"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"gc = GeometryCollection([p, q])\n"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"data": {
"image/svg+xml": [
"<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"100.0\" height=\"100.0\" viewBox=\"0.94 0.94 1.62 1.12\" preserveAspectRatio=\"xMinYMin meet\"><g transform=\"matrix(1,0,0,-1,0,3.0)\"><g><polyline fill=\"none\" stroke=\"#66cc99\" stroke-width=\"0.0324\" points=\"1.0,1.0 2.0,2.0\" opacity=\"0.8\" /><polyline fill=\"none\" stroke=\"#66cc99\" stroke-width=\"0.0324\" points=\"1.2,1.0 2.5,1.2\" opacity=\"0.8\" /></g></g></svg>"
],
"text/plain": [
"<shapely.geometry.collection.GeometryCollection at 0x106c4b7d0>"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# the minimum distance involves these two edges\n",
"# however, the minimum distance is not between the vertices comprising these edges\n",
"# however, it can be proven that the minimum distance must involve one vertex\n",
"lsa = LineString([(1., 1.), (2., 2.)])\n",
"lsb = LineString([(1.2, 1.0), (2.5, 1.2)])\n",
"\n",
"mls = GeometryCollection([\n",
" lsa,\n",
" lsb\n",
"])\n",
"mls"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(True, 0.14142135623730948)"
]
},
"execution_count": 7,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# minimum distance\n",
"lsa.distance(lsb) == q.distance(p), lsa.distance(lsb)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.14142135623730948"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# minimum distance, involves a vertex\n",
"Point(1.2, 1.).distance(lsa)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([[ 0. , 0. ],\n",
" [ 2. , 0. ],\n",
" [ 1. , 1. ],\n",
" [ 2. , 2. ],\n",
" [ 0. , 2. ],\n",
" [ 0. , 0. ],\n",
" [ 4.5, 2. ],\n",
" [ 4.5, 0. ],\n",
" [ 2.5, 0. ],\n",
" [ 2.5, 0.8],\n",
" [ 1.2, 1. ],\n",
" [ 2.5, 1.2],\n",
" [ 2.5, 2. ],\n",
" [ 4.5, 2. ]])"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"u = []\n",
"u.extend(p.exterior.coords)\n",
"u.extend(q.exterior.coords)\n",
"foo = np.array([np.array(tup) for tup in u])\n",
"foo"
]
},
{
"cell_type": "code",
"execution_count": 10,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"d = Delaunay(foo)"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAXQAAAD3CAYAAAANMK+RAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzsnXd4VGX6hu9J772HJJBGEop0QaoQRaQXj+vquq4ggvtz\ndS247rq66xYFsa0dsW3VkS4qICBFUVookkIapPdCep3z+2NmQghJJmUyLd99XVyZOSXzATPPnPN+\nz/c+ClmWEQgEAoH5Y2XsAQgEAoFAPwhBFwgEAgtBCLpAIBBYCELQBQKBwEIQgi4QCAQWghB0gUAg\nsBBsjPniBw4cEJ5JgUAg6ANz5sxRdNxmVEEHGDdunLGHIBAIBGZFQkJCp9tFyUUgEAgsBCHoAoFA\nYCEIQRcIBAILQQi6QCAQWAg6J0UlSVqteRihVCqf6mT/CqASCFcqlZu62iYQCASCgaXbK3RJkuKB\n/RpRDtc8b79/HIBSqdyvfd7ZNn0OOH/rXg5NWMqewKkcmrCU/K179fnrBWaMqbw3TGUcAtMj8amN\n7Amexp6Am9gTPI3Epzbq9ffrKrmEA1oRz9Q8b8+dqK/Etfvju9imF/K37uXCEy/SkFsEskxDbhEX\nnnhRfGAEJvPeMJVxCEyPxKc2kvPJNmhVqTe0qsj5ZJteRb3bkkuHcsk44LMOh3gA5e2ee3exTS+k\nvvAuqvrGa7ap6hs58+e3ORxxg75eRmCGuP35baxN4L1hKuMQmB4e/9rBdSuBgJx/72DE+if08ho9\nWlikKZskKJXKzt3sBqIhr7jT7VYlpdQ3qww8GoEp4VFS2ul2Q783TGUcAtPDQ9XF/3+r/t4XPV0p\nGt/ZhCjq0oqX5rEHUKZ53Nm2fuMQ7Ke+le2AY7Af908M0tfLCMyQQyby3jCVcQhMi8TCGrIUVijk\nTsTbWn9mQ52/SZKk1UqlcoPmcbzmp4dm92dcrauHA/u72KYXop9eg5Wj/TXbZHt7op9eo6+XEJgp\nQ9etptnW9pptVo6Gf2909h41xjgEpkFpbRMvfnuZ3+5O49zEqXTWvCrkniV6e72euFzWS5KUIUlS\nRbtdBwC0JRjNcZVKpTKhs236GmzQ8rmM3Pg78PdFViiwDfLj22U/p2XOTH29hMBM+dAjmn2Lf45d\nkD8oFDT6+NDw6EMELZ9r0HFo36NWAX7IgMMQf0Zu/J3BxyEwLk0tKv53tpAHt6WQXdmAvbWCaa8/\nTegvl4G1lVrYra0I+eUyvdXPARTGDIk+cOCA3JfmXPtSyzhbUMO6mWHsSirhm7RyXlsYjbVVZ1MO\nAkvnVG4Vv9+TwcJYHx6eGgKob3FfOpLNh3fEYqUw/PviZE4V2xOL+fttkQZ/bYHxkGWZH7OreO94\nLmGejoR6OLAvtYxn44cxwt8FAJUsM++Ds+xdNbbPr5OQkNBpt0WzXym6INYHJ1trPj13fd1SYPlU\nN7bw+z0ZANfUqOP8nXGyteJUbpWxhiYYZGRXNvCHvRlsPpHH/90UwlBPB45equCVBVFtYj7QmL2g\nWykUPD4jlB2JJaSX1hl7OAID8/YPuQA8NGUIznbWbdsVCgVLRviyI7HEWEMTDBJqm1rZdDyPx3en\nMT7YjTeXDOdAejln8qp5dWE0we4OBhuL2Qs6gJ+LHQ/eGMz6w1k0tQhr2GDh6KVKDqRX4OVkw/yY\n65c7zAr3JL20ntwrDUYYncDSUckye1PLWPl5EjWNrWxaFsPcaC+e3ZdJXbOKDfOj8HS01f2L9IhF\nCDrAnEhPhrjZ88npAmMPRWAAKuqa+cf3OQA8NHkItp1Yv+xsrJg33JudiZ17wwWCvpJcXMsju1L5\nKqWUP98azmMzQmlWyfx2dxpDPR14ds4wHGwML68WI+gKhYJHpoVwIL2cC4U1xh6OYACRZZnXvsvB\nzlpBjK8T04d5dHnsgjgfDmaUU9vUasARCiyVsrpmXjqcxfP7L7E4zpdXF0Yz3NeZjLI6Ht2Vytwo\nLx6aMsRoBg2LEXQAD0dbHp4awkuHs6hvFh9gS+WbtHJyrjTQqpJ54MZgFN24WHyd7Rgb5Mo3aeVd\nHiMQ6KK5VYXyfBEPbk3Gy9GGD1bEEh/lhZVCwancKn73dQZrJgezYrR/t+/HgcaiBB1g6lAPRgS4\n8P7xfGMPRTAAFFU38f6JfGJ8nRju58yoAN3ugcUjfNmVVILKiBZdgflyIucKD25L4aeCGl5fFM3K\nScE4aSbg91ws46XDWTwXP4wZ4Z5GHqkJhEQPBA9NDmbN9hRO5bozYYibsYcj0BMqWWbjkSxujfJi\nX1o5Ly+I6tF5I/2dsbex4nRuNRNDxPtB0DPyrjTw7o955F5pZO2UYCaFuLftk2WZfyUUsj+9nI3z\nowjxMJyTpTss7godwMXehsenh/HKkWyqG1uMPRyBntiZWEJzq0yLSmbaUHdCe/ghUigULI7zZWeS\nsDAKdFPX1MrmE3k8siuVUYEubFoec42YN7eq2HgkmxM5Vby+MNpkxBwsVNABxga7MnWoO28eyzX2\nUAR6IKeygf+cKeQX4wLYn17OL8YF9ur8myM8uVhSR56wMAq6QCXLfJNWxsotyVTUt/De8lik0f7X\nOKhqm1p5Zm8mVQ0tvDQ/Ek8nw9oSdWGxgg6wclIwqSV1HLlUoftggcnSqpLZcDiLe8cHsi+tnMVx\nvnj18oNkb2PFbcO92ZUkLIyC67lYUstvv0hlV1Ipz8YP48mZYXh3eI+V1Dbx+O5Ugt3t+dMt4Tja\nWnfx24yHRQu6g40V62aF8daxXMrrmo09HEEf+excEU621sT4OnOuoJo7Rvv16fcsjPVhf3o5dcLC\nKNBQUdfMy0eyeO6bTG6P8eH1RdHE+jlfd1xmWT2P7kpldoQXD99kPFuiLixa0AFi/ZyZG+3Na99l\nY8xGZIK+kV5ax/bEEh6fEcr7J/K4Z2xgn6+M/FzsuCHQlf3pwsI42GlRyWz9qZjV21JwtbfhgxVx\nzI327rSRW0JeFU99nc6qSUFINxjXlqgLixd0gF+MC6C4ppm9qeKDbE40tarYcDiLB28M5nJFPWV1\nzcwb3r9EQ21/F2FhHLycyq3iwa3JnM6r4uUFUay+MfiaPkDt2ZdaxovfZvHHOUO5OcKr02NMiR4J\nuiRJ67vYPk6SJFnTLz1DkqT32h8vSdJq/Q2179haW7FuZhgfnMynsLpR9wkCk+CfpwsIdrPn5ghP\nNp/IZ9WkoH7f6o4KcMbOWkFCXrWeRikwF/KrGnluXyZvHsth1aRg/jY3okunlCzL/PtMIf9KKGTj\n/ChGB7oaeLR9o0eJRcCKLnZ7KZVKhVKpjADuALTCv1qSpAwgUz/D7D/h3o4sH+XLy0eyxdWZGZBY\nWMP+tHIemRbCN2nluNhZMyXUXfeJOlAoFCwe4cdO0YVx0FDf3MpHJ/P5zc6LxPo7sWl5LFPC3Lss\nnbSo1K0ljl2u5LVF0YR6mo4tURc6BV2pVG6iC2FWKpXt4+UmKJVK7XEPKJXKiA77jc4do/xpbpXF\nh9nEqW9u5aUjWTw8NQQHW2v+ebpA5xL/3jA7wpOUkjryroi7NUtGlmUOppez8vNkimubeHdZDD+7\nIQC7bjI865paeXZfBmV1zby8IOo6p4upo5cauiZuTtluk5ckSfGSJK3Tx+/XF9ZWCp6cGcp/zhSS\nXSn8yKbK+8fzifN3YepQD7ZfKCbW37lT50Ffsbex4rZoL3Yliy92SyW9tI7Hdqex5adi/jB7KE/N\nGoqPs12355TVNvP4l2n4OtvxZxO1JepCX5OityiVykrtE6VSuUlzde6tDZY2FYLdHbh3fCAvHc6i\nVSVKL6bGqdwqTuRe4aHJwVTWN7P1p2LunxCk+8ResiDWl/1p5aKJm4VRWd/Ma99l84e9Gdwa5cUb\ni4czogf9fi5X1PPoF6nMGObBo9NCTNaWqAt9CXpbMKgkSaslSdLW3MuAcD29ht5YGOuDs501/xOx\ndSZFdWMLrxzN5vHpYbjY2/CfM0XcHOFFsLu93l/L39WOGwJdRBdGC6FFJbP9QjEPbE3B3tqKzSti\nmRfj0yNhPptfzZNfpvPL8YHcNSbApG2JuuiToEuS5NHucUfBzgS0tXNv4FTfhjZwKDSxdTsTS0gT\nsXUmw1vHcpka5s7YYFfyrjTybUY5d4/1H7DXWxzny87EErE+wcw5k1fN2u0p/Jh9hZfmR7J2yhBc\n7XvWd/Bgejl/O3iZ388eSnyU6dsSddETl8sKYEIHC+KBDoe1TZpqSi3xmvPKlEplgl5Gqmd8ndWx\ndRtEbJ1JcPRSJRdL6lg5KRiAD0/ls3yUHx4DGOE1OtAFGythYTRXCqsbeX5/Jq8czeaX4wN5cV4k\nQz0de3SuLMv872whH57KZ8PtkYwNMg9boi50fo0plcotwJYO28a3e5wJPNjJOSbPnEhPvr9cySca\nF4XAOJTXNfPmsRz+dEs4DjZWJBfXklxUy5Mzwwb0ddUWRnUXxvGizbLZ0NCi4rNzRexKKmHZSD+e\nmjUU+17EvbWqZN48lkNycR2vLYzWOVlqTgyKlaJdIWLrjI86Ti6b26K9ifVzRpZl3j+ex73jAw2S\nyTg70ovk4joKqoSF0dSRZZlDGRWs/DyJvCsNvLM0hrvHBvRKzOubW3num0wKq5t4eUGURYk5DHJB\nB3Vs3W+midg6Y7EvrZzimmbuGRcAwA/ZV6hpauUWA9UzHWysuDXKi12iV7pJk1FWxxNfpvPpuSKe\nmjWU388ehp9L78S4vK6ZJ75Mw9PRhr/Mjehyub85M+gFHeCmMA9GBriw6XiesYcyqCiqbmLziXzW\nzQzD1tqKVpWstyX+vWFhnA/7hIXRJKlqaOEf3+fw9NcZ3BzhyVtLhjM6ULcNsSPZFQ08siuVKaHu\nPDY9FBsztSXqQgi6hoemDOFkbhUnc6qMPZRBgTZObvkoX8K91RNZX18sw8fZlokGrmcHuNozKsCF\nA+mib76p0KqS2ZVUwsotyVgpYPOKWBbE9syG2JHzBTU88WUavxgXwD3jAs3alqgLIeganO2seXx6\nGK8eFbF1hkAbJ3fHKLUtsb65lX+fKWDVJP0t8e8NS0YIC6OpcC6/moe2p3D0UiXr50XyfzeF4ObQ\nt/jjbzMq+MuBSzw1K4xbo/vXqdMcsMiQ6L6ijq3z4M1juTx981BjD8diydbEyb2+KLrtiuvz88Xc\nEOhKtI+TUcZ0Q6ALCgWcza9hbLBlWNjMjeKaJjYdzyOlpJbVNwYzfahHn7/cZVnm85+K2ZFYwvp5\nkW13gZaOuELvwMpJQaSV1nEkU9x+DwStKpmXNHFywe7qLnZldc3sTCrhvgm9ywnVJ1oL4w4xOWpw\nGltU/DuhgLXbUwj1cGDzijhmDPPss5irbYm5HEgr5/VF0YNGzEEI+nU42Fjx5Mww3hSxdQPCp+eK\ncLazZmGsT9u2fycUcGuUF4Gu+l/i3xtmR3iSWFhDgeiZbxBkWebopUpWbUnmUkUDby+J6bddtb65\nlT/vzyT3SgOvLIzG18JsiboQgt4JsX7OzBvuzatHRWydPkkvrWOHJk5Oe/WVXdHAd5evcNeYACOP\nDhxtrbk12psvRJD0gHOpvJ6nvk7nXwkFPD4jlD/OGYa/a//Et6KumXVfpeNib8NfLdSWqAsh6F1w\nz7gASmpFbJ2+aGq5GifX/qrpg1P5SKP9+jzppW8WxvmwL7VMWBgHiOrGFt46lsu6r9KZGubBO0tj\nGKOHZfc5lQ08+kUqE4e48eSMUGy76XluyQzOv3UPELF1+uWT0wUMcbdnTqRn27afCmvIKKtjcZyv\nEUd2LYGu9owIcOFghphD0SetKpkvU0pZ+Xmyer3BilgWj/DVy3qDxEK1LfFnYwK4d7xl2xJ1IQS9\nG8K9HVkxyk/E1vWTC4U1HEgv5zdTQ9o+bNol/veND8LOAEv8e8OSOHWQtCi36YcLhTU8vPMiB9LL\neWFeBL+ZFoK7nu7Ijlyq4E/7L/HkzLB+B4hbAqZxn2vCrBjlxw9ZV9iRqG4EJOgd9c2tvHQ4i99M\nC7mmc+LRS5U0q2Rmt7tiNxXGBLmADOcKavRSDhislNSqVwL/VFjDA5OCmRXedxtiR2RZZuuFErb9\nVMwLt0UQaSS7q6lhWpdGJog6ti6M/4rYuj7x/vF8Rga4cFNYWwt9mltVfHgqnwcmBWFlgrfHbRZG\nkT3bJ5paVPzvbCFrt6UQ6GrHBytiuTmi7zbEjrSqZN75MY+9qWW8tihaiHk7hKD3gGB3exFb1wfa\n4uSmDLlm+5cpZQS52TMu2HRb1s6J9ORCYY2YP+kFsixzLKuSB7Ymk1pSxxuLh3PfhCC9ZnM2tKj4\n64FLXCqv59UFUb1u0GXpCEHvISK2rndUN7bwyhF1nFx7+1htUyv/PVPIqomm3X/e0daaW6K8hIWx\nh2RXNPD7PRl8eLKA30wN4blbwgl00++6gsr6Zp76Kg17Gyv+dlsELj1MJRpM9EjQJUlar2tf+0Qj\nSZJWSJIU3yHlyKwRsXW9481juUwd6nHdMnrluSImhbiZxeq9RXG+7Esrp0EkWnVJbVMr7/6Yy+Nf\npjEpxI13l8UMSFhI3pUGHv0ijTGBrjw1Kwy7QWpL1EVPIuhWAyu6OWS1JEkZaGLoJEkaB21RdG3P\nLYG22LpDIrauO45cqiCttI6Vk4Ku2V5S28TulFLuHW+8Jf69IdDNnlg/Jw6mi7UIHVHJMl9fLGPl\n50nUN6vYtDyGpSP9BqQtbVJRLY/vTuOO0X78amLQoLYl6kKnoCuVyk20ywzthAeUSmWEVsCBO4FK\nzeNMIL5/QzQt5kR6EuJhz8enC4w9FJOkvK6Zt47l8uTMsOuWcP/zdAG3x/iYVd1TdGG8nqSiWn6z\nM5W9F8t4fm4Ev50eiucAZb9+d7mS577J5LEZocyP8dF9wiBHH/ctXpryyjrNcw+g/SWNRZlDFQoF\nv5kawsH0cn4SsXXX0DFOrj2Xyus5nl3Fz27wN9Lo+sbYIFdaZXVP7cFOWW0zGw5d5i8HLrFkhC+v\nLowa0O6Y2y8U89axXP52WwSTQtwH7HUsiX4LulKp3KS5OveWJMmirsa7Qhtbt1HE1l3D3tRr4+Ta\ns/lEPneN8Te7/hoKhYLFcT7sHMRdGJta1aHMD25LxttZbUOMj/IasNKHSpZ598dcdieXDviXhqXR\nL0GXJGm1JEna+noZEI663KINhPTQbLc4bgrzYJSIrWujsLqRD07m89SssOv6aJzJqyb3SgMLYs3z\nljk+yotzBTUUVTcZeygG53j2FVZvTeFCYQ2vL4pm5cQgnAbwS7mxRcVfD1wmrbSe1xZFE2DkDpzm\nRp8EXZIk7SqRTEBbO/cGTgGfoRZ2ND/3Y6Gs1cTWnci5YuyhGBWVLPPykWxWjPJjmJfjdfveP5HH\n/RODzLZhktbCuDt58Fyl51Q28Ic9Gbx3PI+HpgTzl7kRbf3rB4orDS089VU6NlbwwrwIXIUtsdf0\nxOWyApjQwYJ4ANqcLPGaY8qUSmWCUqlM0JwXD1Rqn1siznbWPD4jjNeO5lDVMHhj67RxcitGXd8a\n4VBGBdZWCmYM8+jkTPNhUZwve1LLabRwd1NtUyubjufx2y9SGRvkwnvLYgxSv86vauS3X6QyKsCZ\n3908VNgS+4jOr0ClUrkF2NJh2/gO+zues0kvozMDxgapY+ve+mFwxtZdjZMbfl3nvKZWFR+dKuDJ\nmaFmbzULcrMnxteJgxkVFtkESiXL7E8r58NT+UwIdmPT8li8nAbGudKRlOJa/vRNJj8fG8AiE+q8\naY6Ir0E9MFhj67Rxcr8cH0iw+/W1zl2JJQzzcmB0oGU0uFo8wpedicUWZ2FMKa7lkV2pfJFcynPx\n4TwxM8xgYv5D1hX+uC+TR6aFCjHXA6JIpQe0sXXP7ctkZICLwT4MxuZ/54pwsbPudLKzqqGFz84X\ns3F+pBFGNjCMD3blnVaZnwprGR3oYuzh9JvyumY+OpXPydwq7p8QRHyUl0Gbpe1KKuG/Zwv569xw\nhvs66z5BoBNxha4nYv2cmRczeGLr0krr2JlYwmMzOi+nfHquiJvC3AnzNP0l/j3FUrowNreq2HK+\niNVbk3G1t+GDFXHcGu1tMDFXyTKbT+SxI7GEVxdECzHXI0LQ9cg9YwMorWtmj4XH1nUVJ6elsLqR\nvallZrPEvzfER3pxrqCa4hrztDCezKniwW0pJORX8+rCaFbfGGzQtQFNLSpe+PYyiUW1vLYwWu8N\nvAY7ouSiR7Sxdeu+SmdskIvFemg/OV1ASIc4uY77F8f54m2BpScnO2viI734IrmUlRODdJ9gIuRd\naeS947lkVzayZnIwN4a4GXyiuqqhhT/vv4Snow3r50WaXFKVJSD+RfXMMC9H7hjlx8bDlhlb91Nh\nDQcyro2Ta096aR1n8qo7tTBaCovifNlzscwsLIz1za18cDKfR3ZdZIS/C5uWxzA51N3gYl5YrbYl\nDvd14vezhwoxHyDEv+oAsHyUH62ybPa11o7UN7ey8XAWj0wNvSZOTousWUR099iAAV1NaGyC3e0Z\n7uvEtyYcJC1rbIgrP0+mrLaJ95bFcucN/kbxd6eW1vHbL9JYGOfL6huDTTKlylIQJZcBwNpKwRMz\nwnhk10UmBLsR6jmwK+wMxabjeYwKcGFKWOcLTU7lVlNS28y8QdAVb8kIXz44mc/c6IHradJXUkvr\nePtYLs0qFc/MGUacv/EmHY9nX2HjkWwenRbC1KHmvbjMHBBX6ANEsLs9vxwfyIbDWbRYQGzdyZwq\nTuZWsbZDnJyWVpXauXD/xKAB6YltaowLdqWxRcWFolpjD6WNivpmXj2azR/3ZjB3uDdvLB5uVDH/\nMqWUV49m8/yt4ULMDYQQ9AFkQawPrvbWfHq20NhD6RdVDS28ejSbx2eEdemIOJBejpOdNVO7uHq3\nNKwUChbHqXulG5sWlcy2C8Ws3pqCo60VH6yIZd5ww9kQO6KSZT48mc/n54t5eUH0da2UBQOHEPQB\nRKFQ8NiMUHYmlZJqxrF1b/2giZML6nzFZ2OLio9PF/DApGCTKz8MJLdEeXEm37gWxtO5VazZlsKJ\nnCo2zo9kzeQhRs3abGpVsf5QFucL1N0ZO1tBLBg4hKAPML7OdqyZHMxLZhpbdySz8zi59mxPLCbG\n19mot/fGwMnOmjmRXnyZbPgg6YKqRv70TSavf5/D/RMDeeG2CKMv4qppbOEPezJoalGx/vZI3B3E\nFJ2hEYJuAGZHeBLi4WB2sXXldc282UWcnJYrDS1sOV/M/RMtbxFRT1gU58NXF8sM9mVd39zKR6fy\n+b+dFxnu68Tm5bHcFOZh9Duj4pomfvtFGuFejjwzZxj2wpZoFMS/ugFQx9YN4WCG+cTWybLMq0ez\nmRdzfZxce/57ppBZEZ4MGeBe2abKEHcHonwcOTTAjdlkWebbjApWbkmmsLqJd5fFcNeYAJPwc6eX\n1vHorlTmxXizdsqQ67puCgyH8d8NgwQPR1semRrKS4ezqGsy/di6vanllNY1c8/Y6+PktORXNXIg\nvZy7uzlmMLBE099loHr4ZJTV8fiXaSjPF/H0zUN5+uahnbZcMAYnc6p4ek8Ga6cMYdlIy11MZi4I\nQTcgU8LcGR3gwqYTph1bp42TWzfz+ji59nx0Mp+lI/0GLPHdXJgwxI36ZhVJerYwXmlo4R/f5fD0\n1xnMjvDizcXDGRVgOl0ev75YxsYjWfzplmFMN/MAE0uhR4IuSdL6bvat1vxZ3/H4DilHAtSxdadz\nq002tk4ly2w8nM0dncTJtSe5uJYLRbUsGyl6WFspFCyK89HbyuBWlczOxBJWbUnG2krB5hWxLIj1\nMZlShizLfHK6gM/OFfLygihG+JvOl8xgpycRdKuBFV3siwf2axKKwjXPAVZLkpSBOnNU0A51bF2o\nycbW7UgsoVWWWd5NLxZZltl8Ip97xwfiaGu5S/x7w63R3iTkV1NS2z8L49n8atZuT+G7y5VsuD2S\nX980BDcTcos0t6p46XAWp3KreHVh9KCdOzFVdAq6Rqy7EuZwQCvimVwNh35AqVRGaDJHBR0YE+TK\ntGHq2DpTIruygf+eKeSJGWHdXg3+mF1FVWMLt0Z5GXB0po2znTWzIzzZ3UcLY1F1E385cImXj2Tz\ni3GBbLg9sts7JGNQ29TKM3szqG1W8dL8qEFfajNF+lVDVyqVm9rlh44DTmkee0mSFC9J0rp+jc6C\nuX+iOrbusInE1umKk2t/3Acn81k1MchkSgCmwqI4X75O6Z2FsaFFxT9PF/DQjhSGejrw/opYpg8z\nvg2xI2pbYiohHg48O2dYlzZWgXHRy/+KJEnjgASlUpkAbUK/H/BuV4YRtEMbW/fWsVzK6pqNPZxu\n4+Tasye1DE9HGyaFuBloZOZDiIcDkT20MMqyzJFLFTywJZnsygbeXhLDL8YFmqRQZpTV8egXqdwS\n5cWvhS3RpNHXuydeqVQ+BW2TpNqaexlXyzCCDsT6OXN7jDevGTm2LlVHnJyW+uZW/pVQwKpJQSZ3\nBWkqLI7zZWdSCTJd/39eKq9n3Vfp/CehkCdmhPLMnGH4u5qGDbEjp3Or+N3XGayeFMwdo/3F/7uJ\n0ydBlyTJo93j1UqlcoPmcTzqWrq2du7N1TKMoBPuHhtAmRFj65paVLx0KIs1kzuPk2vP1p+KGR3g\nIjIgu2FiiBu1Ta0kF1/fu6eqoYW3juWw7qt0pg/z4O2lMdzQRX8cU2BfahnrD2XxbPwwZkV0nk4l\nMC164nJZAUzoYEE8oNkXD6yXJClDkqQKAE2pJV5zXpm2DCPoHFtrdenlw5P5FFY3Gvz1Pz5dQIiH\nA7N1fGAr6prZnljCr8wods0YWCkULC1IwunuB5h+370cmrCU3C172Z1cyqotybTK8MGKWBbF+Zps\n6UKWZf6VUMC/EgrZOD/KpLzvgu5RGPNW/8CBA/K4ceN6fd6+1DLOFtSwbmbYAIzKOCjPFXEip4oN\n8yMN1vb0p8Ia/nbwEu8ujek0gag9//g+BztrBWsmd94PXaAmf+teLjzxIqr6q1/OLXZ2JN/7K5b9\n9g4ivJ2WBcVPAAAgAElEQVSMODrdtKhkXv8um8zyev5yawReFpgLa2xUssy8D86yd9XYPv+OhIQE\n5syZc51QmN4MzCBFG1u3/YJh+mvXNXUfJ9eenMoGjl6q5OdjBvcS/56Q+sK714g5gE1TExP37DB5\nMdfaEivrW9g4P0qIuRkiBN1EsLZS8OTMMP53tpDsioYBf71NJ/IYHdh1nFx7PjyZzx2j/ExqgYup\nIMsy+VWN7E8r5x/f51CfW9TpcQ15xQYeWe8orW3i8d1pBLra8adbwsWCMTNFfEJNiCA3e+6bEMSG\nw1m8tih6wKLcTuRc4XRuNe8ui9F57IXCGlJL6/jdzUMHZCzmRmOLitTSOpKLakksriW5qBYbKwVx\n/up+8DaBfrQWXC/eDsGm27jqUnk9z+zNYGGcD3cKJ4tZIwTdxJgf482xrEo+PVvIPeP032O8qqGF\n147msG5W13FyWmRZ5v0Tedw3IXDQ9rcurmkiqaiW5OJakopruVzRwFBPB+L8nJkd4cmvpwzBz+Wq\nOyj/mbXX1dCtHO2JfnqNMYavkzP51fz94GXWTg5mdqRY+WvuCEE3MRQKBY9ND2Xt9otMCnUn2ke/\ndde3fshl2jAPxvTALvfd5Ss0tsjMjhgcH/TmVhXpZfVq8S5S/2lRycT6OzPCz5kHbwwmysep2y+3\noOVzAbjwl3doLSzGcYg/0U+vadtuSuxPK+e943k8M3uoSdsnBT1HCLoJ4tMutu6tJcP1FmJwWBMn\n9/ZS3aWWFs0S/4dvstyVgeV1zSRpyiZJxbVklNUT7G5PrJ8zk0PduX9iEIGudr0uQQQtn0vepCls\nTyzm77dFDtDo+44sy/zvbBFfXyzjpfmRDDVydJ1AfwhBN1FmR3hyLOsKH58uYPWNwf3+fWV1zbx1\nLJfnbw3v0fLyr1JKCXS1Y/wQy1ji36qSuVReT5L26ru4ltqm1rYs1HvHBTLc1wknHWUoc6dFJfPG\n9zmkldbx2sJovJ2Fk8WSEIJuoqhj60J4cFsyk0PdGR3Y98Udsizz2tFsbo/xJqabODkttU2t/OdM\nIX+/LaLPr2lsqhpa2ureSUW1pJXW4etsR6yfM2OCXPn5mACGeNgbzPNvCtQ1tfLXg5cA2Dg/yuK/\nvAYjQtBNGHcHGx6ZGsrGI1m8uzSmzx/APanllNU182z8sB4d//n5IsYPcTN537QWlSyTXdnQNnmZ\nWFRLeV0zw32diPN34Y7RfsT6OeNqP3jf7mV1zfxxbwZRPk48PDVkwBxUAuMyeN/hZsKUMHeOZVWy\n6UQej04L7fX5hdWNfHgynw23R3YbJ6eltLaJL5JLeacHdXZjUdvUSkrxVedJSnEdbg42xPmpBXzJ\nCF+GejpabO2/t2RV1PPM3kzmDffmrjHClmjJCEE3A9ZMHsKabSmcyLnCpBDdC4G09DROrj3/PF3I\nvOHe11jxjIl24U6i1jpYVEtBdRORPo6M8HNmQawPT850FmELXXC+oJq/HrjM6huDiReBJBaPEHQz\nQBtbt+FQFu8uc+7xis3tF3THybXnUnk9P2Rf4aM7Yvsz3H7R0KIitaS2TcCTi+uwt1EQ6+dMnJ8z\ntw33JtzLsUd3G4OdbzPKefuHPH5/81DGBgtb4mBACLqZMCbIlenDPHjzWA6/n627Fp5d0cCn54p4\nfVF0j0sPH57M564x/rgYqNYsyzLFNc0kFdeQVFRHUnEN2ZWNDPN0IM7fmfhILx6eGqKzra/gWmRZ\nRnm+mF1JJSYZZScYOISgmxH3Twxi7fYUDmdWMDO863a3LSqZDZo4uSC3ruPk2nM2v5qsygb+2MOJ\n077Q1KoivbS9dbAGWYY4P7V1cFb4EKJ8nPTmux+MtKpk3vohl6SiGl5fFI2P+DIcVAhBNyPsbaxY\nNzOMZ/dlMjLABe8uuuF9erYQNwdr5sd49+j3qmSZzSfy+dWEIOz0WMooq2u+umy+qJaM8npC3O2J\n83dm6lB3HrgxiACX3i/cEXROfXMrfz94mWaVzMsLonW2dhBYHj0SdEmS1msj5jrZtwKoBMK1gdGd\nbRPoh5h2sXXP3xp+nRimltaxM6mUd5YO77FQaoOqZ4Z76Diya1pUMpnl9dcIeF1za9vV930T1At3\nRBe/gaGirpk/7stkmJcDj0wLFbbEQYpOQdckFa0ArhN0TTg0SqVyvyZLtC2tov02kVqkX+4eG8Aj\nu1LZc7GMeTFXQ521cXJrJwf3+Fa7qVXFhycLeHxGaK8W2VxpaLlGvNPK6vBzsSPOz5lxwa7cMzaA\nIe724urbAGRXNvDM3gxuifLinrEB4t98EKNT0JVK5SZJku7oYvedwDeax5lAPOoc0Y7bhKDrEW1s\n3bqv0hkT7Eqgq7pO/vHpAkI9Hbi5F/mPXySVMtTTodtmXa0q9cKd9tbBivpmYjTOk5+N8SfG18lg\nk6mCq1worOEvBy6xcmIQt0b3rMQmsFz6+wn0ANqnG3t3sU2gZ4Z5OXLHaD/+vf5TJu7ZQUNeMV4e\nnsx+7tcoFN1PbOZv3UvqC+/SkFeMyt2TFb9/ELi6zL+msYWUkrq2nicpxbV4OtoS5+9MrJ8zK0b5\nEerhIBbuGJnDmRW8eSyXp2aFMcFCeu4I+oe4pDJjbko9i/M/P6KhqQkAl4pyMp/egJOtVZftWjtm\nXrpWllP47CsUVDeRPHoiScW1FFU3Ee3jRJy/M4vjfPndrDCdMXUCwyHLMlt+KmZ7YgkvzoswmxYN\ngoGnv4JeCWiXn3kAZZrHnW0T6Jn0F9/FWiPmWlT1jZx67i2SvIZ3ek7cc29h1yHzUm5opPGdTxj2\n2Qzmx/oQ7uUoJtVMlFaVzLs/5nKuoIbXFkabzIpegWnQJ0GXJMlDqVRWAp8BEzSbw4H9msedbRPo\nma5yKu3Kyrq8BW8p6/z71a60lO9yqqhtaqW2sXVQtJI1NxpaVLzw7WUamlt5daGwJQqupyculxXA\nBEmSVrezIB4AxiuVygRJkiZIkhQPVGrdLJ1tE+gf+yA/GvOuDyV2CPZjVhd9Ow4F+9HQSZCxfZA/\n82K8SSqq5Z8JBaSX1TNEE/agtR72JexBoB8q6pt5dl8mIR4OPDN7qGh9IOiUnrhctgBbOmwb3+7x\ndT5z4T03DBeXLCd082asGq+WXRQO3edXRj+95rrMSxzsifnDGoKGejBtqNqL3tSqIqNM7Sv/IfsK\nH5zMp7VdHFusvzPROuLYBPoh94ralnhzhBf3jhO2REHXiElRM+VwZgUnYsYxb+PvuLT+PXX5xc+H\nH29bzM2Lb+nyPO1kqdblYuXvy/e3LuKWpbdec5ydtRWxfmpXy3LUE3Eltc1tzpdNx/OuCUzWOmBE\nTVe/JBbV8Pz+S9w3PvCaNQcCQWcIQTdD2sfJhfnFEXbHbYBadE8evKwzti5o+dw2YZdlmf1fp/P1\nxTIWxHYtGAqFAj8XO/xc7Jil8bmrOyPWkVxcy8F0tYXO1lrRJvBxfs5EeIvOiH3l6KVK/vF9Dutm\nhjExRNgSBboRgm5mdBcn15fYOoVCwapJwTy7L4M5kZ69WprvYGPF6ECXttdR9y5valt8tC+1nPyq\nRiK9HdW1eI3Ie3bRg0ZwlW0XitlyvpgXbosg0kfYEgU9Qwi6maErTq4vsXXRPk7cEOjK5+eLuXd8\nYJ/HplAoCHa3J9jdvi1Moa6plYsldSQW1/JVShkvH8nG1d66TeBH+DuLdKF2tKpkNh3PIyGvmlcX\nRuPvKkpYgp4jBN2M6GmcXF9i6+6bEMj/7bjI/FifLrs49gUnO2vGBru2BSyoZJmcygaSiutIKqph\nV1IppbVNRPs6EeunFvgY356HeFgSjS0q1h+6THVjK68sjBrUGaiCviHeMWZCb+PkehtbF+hqz61R\nXvw7oYBH+pBd2lOsFArCPB0J83Rk3nB1V4iqhhZSStRlmq0/FXOxpA5vJ9u2Ek2svzOhHg69ah5m\nblxpaOG5fZn4u9rxt9uG6rWNsWDwIATdTOhtnFxfYuvuGhPAyi3JLB3RQKinQ3+H3GPcHGyYFOLe\n9sXTqpK5XKG2TP5UWMNn54uoamglxs+pbcJ1uK+zxSysybvSyDN7M5g+zIP7JgRa9BeXYGARgm4G\n9CVODnofW+fmYIM02o8PTuXz51vC+zPkfmFtpSDC24kIbycWxvkC6oU12snWf58pJL20niA3u3aT\nrS4EuZnfwqfk4lr+/E0m94wL7NZlJBD0BCHoJk5f4uTa09PYOi2L43zZmVTCT4U1jArQ7ZIxFJ6O\nttwU5sFNYeqFT82tqrZAjRPZVXx8qoCmVllTonEizs+FaF8nHEx44dP3lyt57bscnpgRyo2husti\nAoEuhKCbOL2Nk+tIT2PrtNjZWHHf+CDeP57H64uiTfaK19baiuG+6tLL0pHqbSW1TSQX1ZJYXMvm\nE3lcqmggzMPhGkeNr7OtSfyddiSW8Nm5Iv42N4JoX2FLFOgHIegmTF/i5DpDV2xdR2ZHerL1QjFH\nL1UyowdX9aaCr7MdvuF2bWNubFGRXqq2TB7JrODdH3OxUijaVrWO8FcvfDLkBKQ2v/V49hVeWRjV\nFk4iEOgDIegmijZObk0v4uS6o6vYus6wUih4YFIQ//g+hylh7ma70tPexooRAS6MCLi68Kmwpknd\nvqColoPp5eRcaSTCy/EaR40+bZvtaWpRseFwFuX1zby6MHpQWjMFA4t4R5ko2ji52b2Ik+uOrmLr\numJcsBtBbvZ8mVLGkhG+ehmDsVEoFAS62hPoas+cSPXCp/pm9cKnpKJa9qaW8ep32TjZWrcJfJy/\nM+Fe/V/4VNXQwnPfZOLjbMuLt0ViZ8K1fYH5IgTdBDlfUMPBjHLeWxar13qvNrbu5cPZbJgfqdMe\nt2piML/7Op1borwsxiLYEUdba8YEubZlqsqyTO6VRpI0jprdKaUU16gTnGLbNSFz78XVdUFVI3/Y\nm8FNYe7cPzFI2BIFA4YQdBOjrqmVjUeyeGRqaK9Eo6csH+nHj1lX2H6hRKenPdzbkUkhbijPFfGr\niUF6H4spolAoCPFwIMTDgbma0OX2Gas7Ekt48dvLeDnZtpVo4vycCfO8uvApf+teKv7yDtMLi/km\n0I+DsxewZOViFsVZxp2OwHQRgm5ibDqRxw2BLkwJGxgbm7WVgidmhvHIrlQmDHElzLP7Vaf3jg9k\n7fYUFsT54KuHWr454mJvw4Qhbm0pUK0qmezKBhI1tfgt54upbGghxteJsUmncXvjXWhoRAG0FhQz\nc+t/GH1TCMR1nvMqEOgLUcgzIU7kXOF0bjVrJg8Z0NcJcrPnl+MD2XA4ixaV3O2xfi523B7jwz9P\nFwzomMwJaysFw7wcWRDrw5Mzw/hIiuOjO2JZFOeL08f/gYZrM1tpaCT1hXeNM1jBoEKnoEuStEKS\npHhJklZ3sm+cJEmyJEkZmj/vabav1/y87hxB51Q1tPDa0RwenxFqkHr1/Bhv3B1s+N/ZQp3H/uwG\nf45nV3GpvH7Ax2WueDjaMiXMHZvSzjNbu8p/FQj0SbeCLknSOAClUrm//fN2eCmVSoVSqYwA7gDW\na7avliQpA8jU83gtljeP5TB9mEfb5NxAo1AoeGx6KLuSSkktrev2WGc7a+4a48/mE/kGGZs54xDc\n+bxEtbsnn58vorlVZeARCQYTuq7Q7wQqNY8zgfj2O7VCr2GCUqnUCvgDSqUyosN+QRcczqwgvaye\n+w088ejjbMfaycG8dCiLppbuhWZBrA+5Vxo4k1dtoNGZJ9FPr0Flf+1cg5WjPbHPrOFcQQ0Pajpg\nCgQDgS5B9wDK2z3vdP25JEnxgLLdJi9NmWZdP8dn8Wjj5NbNDDNK4PLNEZ6EejrwsY4aua21FfdP\nDOL9E3mo5O7r7oMZz0XxHFp2N7K/LzLgMMSfkRt/x8h7FvDXuRE8eGMw7/yQxx/3ZpB3pcHYwxVY\nGPpSkFuUSqX2Sh6lUrlJc3XurRF7QSd0FydnKLSxdd9mVHC+oKbbY2cM88DaSsGhjAoDjc782J9W\njsv8Ofjs/hdHP/4ns05tb8tvBbgx1J33lscwKsCFR3al8sGJPOqaWo04YoEloUvQKwEvzWMPoPMZ\nH2irrUuStFqSpBWap2WA8fqwmjh7LpZRVtfM3WMDjDoOdwcbHpkWwsYjWd2Ki0LTEuCjUwU0iVrw\ndciyzM6kUhbr8JvbWVsh3eDPe8tjKatvYeWWZPanlYs7H0G/0SXon3FVkMMB7eSoh/YASZI6Cnam\n9jjUJZpT/R+m5VFQ3ciHpwp4cmaYSfRKmRzqzg2BLrx3PK/b40YHujLMy4FdiSUGGpn5cCa/GmsF\nPQrnBvB2slV3wowfxo7EEh77Io3Uku4nqAWC7uhWSZRKZQK01cgrtc+BAx0OzWx3zn4gXnOVXtbu\nHIEGlSzz8uFs7hjdszg5Q7Fm8hAS8qp1TtqtnBjEZ+eLqWpoMdDIzIMdiSUsHuHb63YNsX7O/GNx\nNLcN9+bZfRm8ciSbivrmARqlwJLRuVJUqVRu6mTb+HaPM4EHO+zfopfRWSjbL5SgkmWWj+xZnJyh\n6GlsXZinIzeFufPpuSJW3xhs4FGaJgVVjSQX1/UoGaozrBQKbhvuzfRhHvw7oYAHtiRz15gAFo/w\nxaafjcEEgwfj3+sPMrIq6vn0XBFPzAzrdwe/gWBMkCvTw9Wxdd1x7/hA9qaWUVjd2O1xg4VdSSXc\nGuXV74QkZztrHpw8hFcWRHMqt4o121I4lVulp1EKLB0h6Aakv3FyhuL+CUFklNV362bxdrJlcZwv\nn4iWANQ3t/JNWjkL4/SXCRrq6cDfb4tg5cQg3vg+h+e+yaSgSnx5CrpHCLoB+d/ZQtwdbPocJ2co\n7G2sWDcrjLd/yKWsruta7opRfpzJqyZdx0pTS+dAegUjA1wI0HP6kEKhYEqYO+8vjyXG14n/23mR\nj07mU98sbI6CzhGCbiBSS+vYlVTKY9NDTSLTUhfDfZ2ZH+vDq0ezkbuw0znZWXP32ADeP5HX5TGW\njizL7EwsGdAQEDsbK+4aE8C7y2IorGli5ZZkDqaXD9p/c0HXCEE3ANo4ubV6ipMzFD8f4095XTN7\nLna1/ADmxfhQUtvMqdzB2RLgbH4NCgXc0EOrYn/wdbbj6ZuH8vubh7Llp2Ie35026O+OBNciBN0A\naOPkbtZTnJyhsLVWl14+PFVAQReTnzZWCu6fGMTmE3m06mjFa4nsSOqbVbE/jAxw4Y3Fw4mP8uIP\nezN4/btsrggLqQAh6APO+YJqDmaU85upIWZRaunIUE9HpNF+bDyc3eVKxqlh7jjZWXMgvbzT/ZZK\nQXUjiYU1est97Q3WVgpuj/Fh84pYbK2tWLUlmR2JJYPyS1VwFSHoA4g6Ti57wOLkDMWykX7IyGy7\n0PnqUHVLgGA+Pl1Ao46ujZbEF0ml3BrtjaOt8fJWXe1teGjKEF6aH8kPWZWs3Z7CmfzBWf4SCEEf\nUN47PrBxcobC2krBkzPC+OxcEVkVnYdcxPk7E+PrzPbEwRHkUN/cyr7UMr1aFfvDUE9HXpwXyb3j\nAnnlSDbP778k1ggMQoSgDxAncq6QkDfwcXKGIrAHsXX3Twxky/niQVHPPZhRwYgAFwL1bFXsDwqF\ngmnDPNi8IpZwb0d+veMi/zxdQMMgumsa7AhBHwAMHSdnKHTF1g1xd2BWhCf/PaM71s6ckWWZHYkl\nLNHRVdFY2NtYcc/YAN5ZGkNOZQOrtiRxJLNC2BwHAULQBwBDx8kZCoVCwePTw/giqbTLroB3jw3g\nQHo5+Ra8qvFcQQ3IMCZo4K2K/cHPxY4/zBnGuplh/PdsIU9+mU5mmciFtWSEoOuZQxkVZBghTs5Q\neDvbsnZKMBsOZ3U6AerpaMvSkX58dNJy80f72lXRWIwOdOWtJTHMDPfgqa/TeeP7HNEp00IRgq5H\nyuqaefuHXNbNMk6cnKGYFe7JUE8HPj7VuWgvG+nLhaJakotrDTyygaewupELhTXMiTSvNQXWVgoW\nxvnywYpYAFZuSeaLJGFztDQsV3UMjCzLvHo0m/mxPgz3NU6cnKFQKBQ8PDWEQ5mVnC+43iLnaGvN\nveMD2Xwi3+Lqtl8klXJLlJdRrYr9wc3BhoenhrB+XiSHMyv59Y6UTv8PBeaJEHQ9sediGeV1zfx8\njL+xh2IQrsbWZXcaW3drlBdVjS38mG05rV8bWlTsTS1jkYlOhvaGcG9HXpofyV1jAthwOIu/HbxE\ncU2TsYcl6Cc6BV2SpBWSJMVLkrS6i/3rNT9X9/QcS8PU4uQMxeRQd8YEunYaW2dtpWDVxCA+OJlv\nMbf1B9PLifN3JtCEWx/3BoVCwcxwTzaviCPE3YG121P495nCQbU4zNLoVn0kSRoHbbFybc87sFqS\npAw0MXQ9PMdiUMkyG00wTs5QPDg5mIS8ao5nXx9bNynEDU9HG/amdt3cy1zQdlXUFQBtjjjYWHHv\n+EDeWjKczLJ6Vm1J5rtLlRZXLhsM6LqcvBOo1DzOBOI7OeYBpVIZoRXwHp5jMWy7UIJsgnFyhsLZ\nzponZoTy2nfXOycUCgWrJgXxz4QCs+/hfb6ghlYZxgVblhW1PQGu9jwbP4zHZoTySUIBv/s6nctd\nrAwWmCa6BN0DaN9xqbNkBi9NeWVdL86xCLIq6vnsXBFPmmicnKG4IciVGeEevNFJbN1wX2dGB7iw\n9SfzbgmwM6mERXE+ZmNV7A9jg1x5d2kMU8I8ePLLdN7+IZfqRmFzNAf6XfBVKpWbNFfn3pIkWfTV\neHvax8lZSk21P9w/IYjMLmLrfjUhiO2JJVR0k35kyhTXNHGuoIZboryMPRSDYW2lYMkIX95fHkNz\nq4pVW5L5MqXUYuZDLBVdgl4JaN/FHsA1xVBJklZLkrRC87QMCNd1jqVgLnFyhuKa2Lraa4U70M2e\nW6K8+JeZtgT4IqmEeDO2KvYHD0dbHpkWyt/mRnAgrZyHd14ksbDG2MMSdIEuQf8MtUij+amd6PTQ\nbMvUbkNdWjnV1TmWRGqJecXJGYrhvs4siPXhlU5i634+JoCjlyrJqWww0uj6RmOLij2p5SyKtbzJ\n0N4Q6ePEywuiuGO0H3/79jIvfHuZ0lphczQ1uhV0pVKZAKAppVRqnwMHNPv3A/Gaq/QypVKZ0M05\nFkFji4oNh7N4aIp5xckZip+PDaCivpmvO8TWuTnYcMcoPz40s5YABzMqiPF1IthdlNUUCgU3R3jx\nwYpYAlztWLMthf+dLaRJ2BxNBp2pC0qlclMn28a3e7ylJ+dYCh+fymeopwOzws1r6behsLFSsG5W\nGE9+mc7YYNdr2ssuHuHLzqQSLhTWMDLAtBtbwVWr4qpJltmXp6842lrzqwlBzI325r3jeTywNZk1\nk4cwOdRN3LEamcGzCkYPnC+o5lBmJQ+baZycoegqts7exor7JgTy/ok8s/A4/1RYS1OryqKtiv0h\nyM2eP98SzsNTQ9h8Io/f78kgu8K8SmqWhhD0HtIWJzctxKzj5AxFV7F1syO8aGyR+e7y9QuRTI2d\nSSUsGeGLlfjy7pYJQ9x4b3ksE0PcePzLNN79MZfaTtpBCAYeIeg9RBsnNznUvOPkDEX72Lr2i1Os\nrRQ8MEndEqCr5CNToLimibP51cRHDh6rYn+wsVKwbKQfm5bHUNekYuXnSey5WNZlsLhgYBCC3gOO\nZ1tWnJyhCHSz574JgWw4dG1s3fghbgS62vFVSqkRR9c9u5NLiY/0wsmCEqcMgaejLY/NCOX5WyPY\nc7GMR3alWmQbZVNFCLoOqhpaeO27HJ6wsDg5Q3H7cG88HW2vi6VbNSmI/5wpNMlb88YWFV9fLGOR\niQRAmyPRvk68sjCKxXG+PL//EhsOZ1FmpgvLzAkh6Dp441gOM8I9uMHC4uQMhUKh4LHpoexOvja2\nLsLbifFD3Pj8fJERR9c5hzIrGO7rRLC7g7GHYtZYKRTER6ltjt6ONjy4NRnluSKaWoXNcaAQgt4N\nhzIqyCyr5/4JwrbWH9SxdUOui627b3wgXySXmtQCFW0AtCV2VTQWTnbWrJwUzOuLovmpsIYHt6Zw\nIsf0J8XNESHoXVBWOzji5AzFzRGeDOsQW+fnYse84d7887TptARILKqlsUXF+CHijkzfBLs78Je5\nEaydEsy7P+bxzN4Mcq8Im6M+EUrVCbIs88ogiZMzJJ3F1v3sBn9+yL7CpXLTaNO6I7GERXHCqjiQ\nTApx571lMdwQ6MKju1LZfCKv09QrQe8Rgt4JX18so6J+8MTJGQo3BxsenRbCS4evxta52Ntw1xh/\nk2gJUFLbxJn86kHVVdFY2FpbccdofzYtj6WyvoWVW5L5Jk3YHPuLEPQOFFQ38tGpAtbNGlxxcobi\nxlB3xgZdG1u3INaHrMoGzuYbN6x4d1IpsyO8hJvJgHg52fLEzDCejR/GrqRSHt2VysUSYXPsK0Kx\n2qGNk5NG+zHUc/DFyRmKjrF1dtZW/GpCEJtP5BvtCq1JY1VcPEJYFY1BrJ8zry+KZkGsD899k8nL\nR7LMtn++MRGC3o5tF0qQkVk2SOPkDIWznTVPzrw2tm5muLoj8+HMyu5OHTAOZVYQ6ePIEGFVNBpW\nCgW3RnvzwYo4XO1tWL0thS0/FdMsbI49Rgi6hssV9Xx6tpAnZwzuODlDMTrQlZnhHrzxvTq2zkqT\nP/rRqXyD+5S1VsUlI4RV0RRwtrNm9Y3BvLwgioS8KtZsS+FUbpWxh2UWCEFHEyd3KItfTQwScXIG\n5FcTgrhU0cC3mti6MUGuhHk48EWSYVsCJBXVUt+sYsIQN4O+rqB7Qj0c+NvcCB64MZg3j+Xw3L5M\n8qsajT0sk0YIOvDfM4V4Otpy+3ARJ2dI7G2sWDczjHfaxdatnBTEp+eKDBpKvEMTAC2siqaHQqFg\ncqg7m5bHEuvvxMM7L/LhyXzqm4XNsTN0CrokSSskSYqXJGl1F/tXa/6sb7dtvXaf/oY6MKSW1LE7\nWeJriYUAAAvoSURBVMTJGYtoX6drYuuGejpyU5g7n50zTEuA0tomEvKquTVafJmbMnbWVvzshgDe\nWxZDSW0TKz9P5kB6uVn01Tck3Qq6JEnjoC1qru15u/3xwH5NQlG45jnAakmSMlBnjpos2ji5tVOC\n8Xa2NfZwBi0/HxtAZcPV2Lp7xwXy9cUyimsGviXA7uRSZkd4CquimeDjbMdTs4byh9lD2fpTMY/t\nTiOttE73iYMEXVfodwJa20EmEN9hf3i7bZlcDYd+QKlURmi/CEyVj0ScnElgY6Vg3cwwPjpVQEFV\nI97OtiyM9eHj0wUD+rpNLSq+SiljkejbYnaMCHDhjcXDuTXKi2f2ZvDq0Wwq64XNUZegewDl7Z5f\nc1+qVCo3tcsPHQec0jz20pRp1ulnmPpHHSdXIeLkTIQwT0fuHO3HS0eyaFXJ3DHan9O5VWSUDdzV\n1+FLaqtiiIewKpoj1lYK5sX48MGKWBxsrXhgawrbLxSbdHDKQKOXSVFNKSZBqVQmQJvQ7we825Vh\nTIa6plZeOpzNo9NCRZycCbFU4//ffqEYZztr7h4bwPsnBqYlgOiqaDm42NuwdvIQNs6P5MfsKtZu\nSyEhb3DaHHUJeiWgbWzhAZR1cVy8Uql8CtomSVdotpdxtQxjMrx3PI+xQa4iTs7EaIutO1/M5Yp6\nbo/xoai6aUA8yMnFddQ2tTIxRFgVLYUwT0denBfBfRMCee27HP78TSYF1YPL5qhL0D/jqiCHA9rJ\nUQ/tAZIkrVYqlRs0j+NR19K1tXNvrpZhTAJtnNyDk4ONPRRBJwS62fMrTWwdwMqJ6pYArXq+jd6R\nWCy6KlogCoWCqUM9eH95LJE+Tvzfjot8crpg0NgcuxV0bQlFI9SV2ufAgXbb10uSlCFJUoXmnP1A\nvOYqvazdOUZHxMmZB/PaxdZNHeqOg40VBzPKdZ/YQ8pqmzmdV81cYVW0WOxtrLh7bADvLI0h70oD\nq7YkcyijwuJtjjoLyO0mPdtvG6/5uR+4ziKiVCq36GV0euaN70WcnDmgja1buz2FG0PdeGBSEH//\n9jIzhnnqJWxkd0ops8KFVXEw4Odix+9nD+N8QQ1v/5DLF8mlPDQlmAhvJ2MPbUAYNCtFv82oILNc\nxMmZC22xdYeyiPRxItrHiZ2JJf3+vU2tKr5KKRWToYOM0YEuvLVkODdHePL01xn84/urjeEsiUEh\n6GW1zbzzQy5PzRoq4uTMiJsjPAn3duSjU/ncPzEI5fmifn8Ij2RWMszLkVBPYVUcbFhbKVgQ68Pm\nFbFYK2DllmR2JZXofX7GmFi8umnj5BbE+hDta5m3WZbMwzeFcDizkor6ZmaEe/Kfs33PHxVdFQWg\nTs769U0hbLg9kqOXKnloewrnjByuoi8sXtDb4uTGBhh7KII+4OZgw2+nq2Prlo/0Y39aOQV97LiX\nUlJHdWMLE0VXRQEwzMuRDbdHcve4ADYeyeavBy4ZpN3EQGLRgl5Q1ciHJ/NZNysMG9Hj3GyZFOLO\nuGBXPjtXxNKRfnx0qm+LjbQB0KLfvUCLQqFgxjBP3l8RS5inA2u3p/DvhAIaW8wzVMNiBb1VJfPS\nkSzuvMFfxMlZAA/eGMyZ/GpC3O35qbC217mTZXXNnMqtYm60CIAWXI+DjRW/GBfI20tiuFyhtjke\nvVRpdjZHixX07ReKAUScnIXgpImte/fHPBaP8OH94/m9+rB9mVzKzHBPXOxFqwdB1/i72vHMnGE8\nPiOUfyUU8NTX6Vwqrzf2sHqMRQr65Yp6PjtfLOLkLIzRga7MCvcgtaSeyoYWTuT0rCVAc5tVUQRA\nC3rGmCBX3lkaw7ShHqz7Kp23juUaNHSlr1icoGvj5O6bECji5CyQX00IIruygQhvxx63BDhyqZIw\nT0fCROlN0AusrRQsivNl84pYWmWZlZ8nszu51KRtjhYn6CJOzrKx08TWJeRV06yS2ZfaVb+4q+wU\nVkVBP3B3sOE3U0N4YV4EBzPK+b+dF7lQWGPsYXWKRQn6xZJavhBxchZPtK8TC2N9qGls4ZOE7hsv\npRTXUtnQwiTRVVHQTyK8nXh5fhR3jvbnhW8v88K3lympNS2bo8UIemOLig2HsnhoyhARJzcI+PnY\nAPxd7Siva2Hbha5bAuxMKmFRrI+YSxHoBYVCwawITzaviCXQ1Y6121L475lCmkzE5mgxgv7RqXzC\nvRy5OULEyQ0GtLF1AJ+cLqCik/ix8rpmTuRUMVeU3wR6xtHWmvsmBPHGkuGkldbxwNZkvr9sfJuj\nRQj6+YJqDmdW8vDUEGMPRWBAwjwdWX2juq/9v05f3xLgq5RSZgzzwFVYFQUDRKCrPc/dEs4j00L4\n+FQBT+/JILuiwWjjMXtBr22LkwvBTcTJDTqWjfQlzMOB3Sml5F65+kFqblWxO6WUxWIyVGAAxgW7\n8c6yGG4McePxL9N458dcaoxgc9SpgJqgikogvLPe6J3t13WOPnnvR3Wc3I0iTm5QYqVQ8PzccH75\nWRLP7svkwzviAPjuciWhHg5ilbDAYNhYKVg60o+bIzz56FQBq7Yk88sJQcyN9jJYMla3V+ia8Gdt\nkEXb8+726zpHnxzPvsKZfBEnN9gJdLVn7eRgcq80cr5A3TVPdFUUGAsPR1t+Oz2U5+dGsPdiGQ/v\nvEhikWFsjrpKLneivtIGdVZofA/26zqnXyQ+tRHVrMWMuvMuyibPZ9X3O0XyjIAlI3wZfvYEKbN+\nxp7AqUx/6nFCTx43yljyt+6lYuG9TL/vXg5NWEr+1r1GGYfAuET7OPHqwiiWjfTjbwcus/7QZS7+\n9yuOTFzGo8/8ekDeG7pKLh5A+zDHjnaBzvbrOqfPJD61kZxPtgGgABQqFfWf7ybRyY4R65/Q18sI\nzJCCbftY+OWnqOrVrXVdKspJevJFrBQQtHyuwcaRv3UvF554EVV9IwqgIbeIC0+8CBh2HALTQKFQ\nMCfSi5vC3Nnx2uek/uNdbJubBuy9YVaziDn//v/27tinySCM4/jPEiMwNY1hIWpSI39Aw+DiRN0c\nGPAmZmB1kTAwE4kjJmwOxoGTgT+A7k7v5kIiiYkMMkA3IIbq8F5DgbYEeNv3vbvvZ+J9S9Mnb+59\ner3n7r2drud/fdnRp5dvhhwNiqS+uqHxk8vPSW+dnOn76oZ2S8+iiwPFU//8VQ//Xl6I1Do5097a\n5tASelNS+3mjZUlX11n3er3fe+7uvPvk/VKrpXevnmb2MfDPz+OjrufHj4+G2jaKEgeKp1fbOD04\nzOwzbkroW5Km3d9VSe1CZ9la2+z1eo9z9zdS6p7UR0p68Zjt5WJ2MDmh099/rp0fnZwYatsoShwo\nnn5tIyt9i6LW2kSSjDF1Sc32saRGr9f7vOfenszP3uo84jG1sqTS2OWna5bGHmlqZSnKOFA8w2gb\nD/JcqtpoNP7Vareb1fhj+WM6ln7ekkZKejI/S0EUktKC5N7apk4PDjU6OaGplaVcCpFFiQPFk1Xb\nSJJEMzMz1ya3e5fQASB2vRK690v/AQApEjoABIKEDgCBIKEDQCBI6AAQiNyX/idJZtPUASBquU5b\nBABkhyEXAAgECR0AAkFCD4Ax5kPeMQC+MMa8zzuGQcm9KHoXw9yztOiMMQuS5iQt5x1LEbjrIUnP\nrbXRX5OOe+WttXYx73jy5h4a+FrSet6xDIJ3PfRh7lnqA/eFtp93HEXgbtZdd02q7jha7eTl7pVq\n7PdKDLxL6BrwnqXwWlUX7WHfHUfLWrvb0SuvZPkoax8ZY2rtjmCofBxyGdiepfDbleG3mtINWKJm\njClLWpC0lncsBVC5+V/85mMPHejLDS0ksfdIJcla27TWrktaNMZE+4slht655GdCv2mfU6BOQTRN\nYh3j5onS4nmsqsaYOVc0r4RaT/AxoW/pYmw02z1LPeRmMUx3zO6ImjFmwfVIFXtRVGk9obPzE23x\n3Fq7ba3ddoflXIMZIC+X/rvktS+mLaKDS+DflNZYKkqn6kX7he/Gz407ZBpnBLxM6ACA63wccgEA\ndEFCB4BAkNABIBAkdAAIBAkdAAJBQgeAQJDQASAQJHQACMR/Tpx98qjXM0gAAAAASUVORK5CYII=\n",
"text/plain": [
"<matplotlib.figure.Figure at 0x106c4bb90>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"plt.triplot(foo[:,0], foo[:,1], d.simplices.copy())\n",
"plt.plot(foo[:,0], foo[:,1], 'o')\n",
"plt.show()"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[10 11 3]\n",
"[4 2 3]\n",
"[ 2 10 3]\n",
"[2 4 0]\n",
"[12 11 6]\n",
"[11 12 3]\n",
"[1 2 0]\n",
"[ 2 1 10]\n",
"[7 9 8]\n",
"[9 1 8]\n",
"[ 9 11 10]\n",
"[ 1 9 10]\n",
"[9 7 6]\n",
"[11 9 6]\n"
]
}
],
"source": [
"for triangle in d.simplices:\n",
" print triangle"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# This Only Finds the Closest Point Pair\n",
"## Now What\n",
"- Gabriel graph (optional, but highly desireable)\n",
"- Filter edges containing vertices from only one polygon\n",
" - compute lengths of remaining edges (distance between two points, one from `p`, one from `q`)\n",
"- the shortest length is the minimum distance"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Edge Filtering \n",
"\n",
"Min `p` index: 0 \n",
"Max `p` index: 5\n",
"\n",
"Min `q` index: 6 \n",
"Max `q` index: 13\n",
" \n",
" \n",
" \n",
" For each edge: \n",
" if vertex1 index is less than minimum q index: \n",
" if vertex2 index is greater than or equal to minimum q index: \n",
" keep it \n",
" else (implies vertex1 is part of q): \n",
" if vertex2 is less than or equal to maximum `p` index: \n",
" keep it "
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"array([[ 1, 0],\n",
" [ 2, 0],\n",
" [ 2, 1],\n",
" [ 3, 2],\n",
" [ 4, 0],\n",
" [ 4, 2],\n",
" [ 4, 3],\n",
" [ 7, 6],\n",
" [ 8, 1],\n",
" [ 8, 7],\n",
" [ 9, 1],\n",
" [ 9, 6],\n",
" [ 9, 7],\n",
" [ 9, 8],\n",
" [10, 1],\n",
" [10, 2],\n",
" [10, 3],\n",
" [10, 9],\n",
" [11, 3],\n",
" [11, 6],\n",
" [11, 9],\n",
" [11, 10],\n",
" [12, 3],\n",
" [12, 6],\n",
" [12, 11]], dtype=int32)"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"t = Triangulation(foo[:,0], foo[:,1],)\n",
"# all edges\n",
"t.edges"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[array([8, 1], dtype=int32),\n",
" array([9, 1], dtype=int32),\n",
" array([10, 1], dtype=int32),\n",
" array([10, 2], dtype=int32),\n",
" array([10, 3], dtype=int32),\n",
" array([11, 3], dtype=int32),\n",
" array([12, 3], dtype=int32)]"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"to_keep = []\n",
"for edge in t.edges:\n",
" if edge[0] < 6:\n",
" if edge[1] >= 6:\n",
" to_keep.append(edge)\n",
" else:\n",
" if edge[1] <= 5:\n",
" to_keep.append(edge)\n",
"\n",
"# edges with vertices in p and q\n",
"to_keep"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# all vertex-pair distances\n",
"distances = [Point(foo[edge[0]]).distance(Point(foo[edge[1]])) for edge in t.edges]"
]
},
{
"cell_type": "code",
"execution_count": 19,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[(array([8, 1], dtype=int32), 0.5),\n",
" (array([9, 1], dtype=int32), 0.9433981132056605),\n",
" (array([10, 1], dtype=int32), 1.2806248474865698),\n",
" (array([10, 2], dtype=int32), 0.19999999999999996),\n",
" (array([10, 3], dtype=int32), 1.2806248474865698),\n",
" (array([11, 3], dtype=int32), 0.9433981132056605),\n",
" (array([12, 3], dtype=int32), 0.5)]"
]
},
"execution_count": 19,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# candidate distances\n",
"c_distances = [(edge, Point(foo[edge[0]]).distance(Point(foo[edge[1]]))) for edge in to_keep]\n",
"c_distances"
]
},
{
"cell_type": "code",
"execution_count": 20,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"# which triangles contain edge (10, 2)\n",
"# one: (10, 2, 3)\n",
"# the edge must belong to p or q\n",
"# only one possibility:\n",
"# (2, 3)"
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.14142135623730948"
]
},
"execution_count": 25,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Point(foo[10]).distance(LineString([Point(foo[2]), Point(foo[3])]))"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.14142135623730948"
]
},
"execution_count": 29,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Alternatively, find distance between foo[9, 10, 11] and foo[1, 2, 3]\n",
"LineString([Point(foo[9]), Point(foo[10]), Point(foo[11])]).distance(\n",
" LineString([Point(foo[1]), Point(foo[2]), Point(foo[3])])\n",
")"
]
},
{
"cell_type": "code",
"execution_count": 30,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.19999999999999996"
]
},
"execution_count": 30,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# alternatively, find distance between the candidate points and two surrounding line segments\n",
"Point(foo[2]).distance(LineString([Point(foo[9]), Point(foo[10]), Point(foo[11])]))"
]
},
{
"cell_type": "code",
"execution_count": 31,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0.14142135623730948"
]
},
"execution_count": 31,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"Point(foo[10]).distance(LineString([Point(foo[1]), Point(foo[2]), Point(foo[3])]))"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 2",
"language": "python",
"name": "python2"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 2
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython2",
"version": "2.7.15"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
