Polygon Partitioning and Convex Hull Construction
2020-04-15 07:51
This GeoGebra applet demonstrates the partitioning of polygons and the construction of convex hulls. By defining various points, lines, and polygon objects, combined with geometric transformations and function graphs, it dynamically illustrates the methods of subdividing polygonal regions. This interactive tool helps visualize convex hull algorithms, polygon triangulation principles, and their geo
<?xml version="1.0" encoding="utf-8"?>
<geogebra format="5.0" version="5.0.574.0" app="classic" platform="d" id="e6da1c51-1c50-44a6-8c89-d81581546407" xsi:noNamespaceSchemaLocation="http://www.geogebra.org/apps/xsd/ggb.xsd" xmlns="" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" >
<gui>
<window width="800" height="600" />
<perspectives>
<perspective id="tmp">
<panes>
<pane location="" divider="0.25" orientation="1" />
</panes>
<views>
<view id="512" toolbar="0 | 1 501 5 19 , 67 | 2 15 45 18 , 7 37 | 514 3 9 , 13 44 , 47 | 16 51 | 551 550 11 , 20 22 21 23 , 55 56 57 , 12 | 69 | 510 511 , 512 513 | 533 531 , 534 532 , 522 523 , 537 536 , 535 | 521 520 | 36 , 38 49 560 | 571 30 29 570 31 33 | 17 | 540 40 41 42 , 27 28 35 , 6 , 502" visible="false" inframe="false" stylebar="false" location="1,1,1" size="500" window="100,100,600,400" />
<view id="4" toolbar="0 || 2020 , 2021 , 2022 , 66 || 2001 , 2003 , 2002 , 2004 , 2005 || 2040 , 2041 , 2042 , 2044 , 2043" visible="false" inframe="false" stylebar="false" location="1,1" size="300" window="100,100,600,400" />
<view id="8" toolbar="1001 | 1002 | 1003 || 1005 | 1004 || 1006 | 1007 | 1010 || 1008 1009 || 66 68 || 6" visible="false" inframe="false" stylebar="false" location="1,3" size="300" window="100,100,600,400" />
<view id="4097" visible="false" inframe="true" stylebar="true" location="1,1" size="395" window="642,398,944,550" />
<view id="1" visible="true" inframe="false" stylebar="true" location="1" size="568" window="100,100,600,400" />
<view id="2" visible="true" inframe="false" stylebar="false" location="3" size="200" window="100,100,600,400" />
<view id="16" visible="false" inframe="false" stylebar="false" location="1" size="150" window="50,50,500,500" />
<view id="32" visible="false" inframe="false" stylebar="true" location="1" size="150" window="50,50,500,500" />
<view id="64" visible="false" inframe="false" stylebar="false" location="1" size="150" window="50,50,500,500" />
<view id="70" visible="false" inframe="false" stylebar="true" location="1" size="150" window="50,50,500,500" />
</views>
<toolbar show="true" items="0 39 73 62 | 1 501 67 , 5 19 , 72 75 76 | 2 15 45 , 18 65 , 7 37 | 4 3 8 9 , 13 44 , 58 , 47 | 16 51 64 , 70 | 10 34 53 11 , 24 20 22 , 21 23 | 55 56 57 , 12 | 36 46 , 38 49 50 , 71 14 68 | 30 29 54 32 31 33 | 25 17 26 60 52 61 | 40 41 42 , 27 28 35 , 6" position="1" help="false" />
<input show="true" cmd="true" top="algebra" />
<dockBar show="true" east="true" />
</perspective>
</perspectives>
<labelingStyle val="0"/>
<font size="12"/>
</gui>
<euclidianView>
<viewNumber viewNo="1"/>
<size width="568" height="407"/>
<coordSystem xZero="215.0" yZero="315.00000000000006" scale="50.0" yscale="50.00000000000003"/>
<evSettings axes="false" grid="false" gridIsBold="false" pointCapturing="3" rightAngleStyle="1" checkboxSize="26" gridType="3"/>
<bgColor r="255" g="255" b="255"/>
<axesColor r="0" g="0" b="0"/>
<gridColor r="192" g="192" b="192"/>
<lineStyle axes="1" grid="0"/>
<axis id="0" show="false" label="" unitLabel="" tickStyle="1" showNumbers="true"/>
<axis id="1" show="false" label="" unitLabel="" tickStyle="1" showNumbers="true"/>
</euclidianView>
<algebraView>
<mode val="3"/>
</algebraView>
<kernel>
<continuous val="false"/>
<usePathAndRegionParameters val="true"/>
<decimals val="2"/>
<angleUnit val="degree"/>
<algebraStyle val="0" spreadsheet="0"/>
<coordStyle val="0"/>
</kernel>
<tableview min="-2.0" max="2.0" step="1.0"/>
<scripting blocked="false" disabled="false"/>
<construction title="" author="" date="">
<element type="point" label="A">
<show object="false" label="true" ev="4"/>
<objColor r="77" g="77" b="255" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<animation step="0.1" speed="1" type="1" playing="false"/>
<coords x="-1.24" y="0.54" z="1.0"/>
<pointSize val="5"/>
<pointStyle val="0"/>
</element>
<element type="point" label="B">
<show object="false" label="true" ev="4"/>
<objColor r="77" g="77" b="255" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<animation step="0.1" speed="1" type="1" playing="false"/>
<coords x="1.68" y="0.56" z="1.0"/>
<pointSize val="5"/>
<pointStyle val="0"/>
</element>
<element type="numeric" label="n">
<value val="4.0"/>
<show object="true" label="true"/>
<objColor r="0" g="0" b="0" alpha="0.10000000149011612"/>
<layer val="0"/>
<labelMode val="1"/>
<slider min="3" max="8" absoluteScreenLocation="true" width="200.0" x="378.0" y="109.0" fixed="false" horizontal="true" showAlgebra="true"/>
<lineStyle thickness="10" type="0" typeHidden="1"/>
<animation step="1" speed="1" type="0" playing="false"/>
</element>
<command name="Polygon">
<input a0="A" a1="B" a2="n"/>
<output a0="poly1" a1="f" a2="g" a3="h" a4="m" a5="q" a6="s" a7="j" a8="k" a9="C" a10="G" a11="I" a12="K" a13="F" a14="H"/>
</command>
<element type="polygon" label="poly1">
<lineStyle thickness="5" type="0" typeHidden="1" opacity="178"/>
<show object="false" label="true"/>
<objColor r="153" g="51" b="0" alpha="0.10000000149011612"/>
<layer val="0"/>
<labelMode val="0"/>
</element>
<element type="segment" label="f">
<show object="false" label="false" ev="4"/>
<objColor r="153" g="51" b="0" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<auxiliary val="false"/>
<coords x="-0.020000000000000018" y="2.92" z="-1.6016"/>
<lineStyle thickness="5" type="0" typeHidden="1" opacity="178"/>
<outlyingIntersections val="false"/>
<keepTypeOnTransform val="true"/>
</element>
<element type="segment" label="g">
<show object="false" label="false" ev="4"/>
<objColor r="153" g="51" b="0" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<auxiliary val="true"/>
<coords x="-2.9199999999999995" y="-0.019999999999999796" z="4.9167999999999985"/>
<lineStyle thickness="5" type="0" typeHidden="1" opacity="178"/>
<outlyingIntersections val="false"/>
<keepTypeOnTransform val="true"/>
</element>
<element type="segment" label="h">
<show object="false" label="false" ev="4"/>
<objColor r="153" g="51" b="0" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<auxiliary val="true"/>
<coords x="0.019999999999999574" y="-2.92" z="10.1284"/>
<lineStyle thickness="5" type="0" typeHidden="1" opacity="178"/>
<outlyingIntersections val="false"/>
<keepTypeOnTransform val="true"/>
</element>
<element type="segment" label="m">
<show object="false" label="false" ev="4"/>
<objColor r="153" g="51" b="0" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<auxiliary val="true"/>
<coords x="2.92" y="0.019999999999999574" z="3.6100000000000003"/>
<lineStyle thickness="5" type="0" typeHidden="1" opacity="178"/>
<outlyingIntersections val="false"/>
<keepTypeOnTransform val="true"/>
</element>
<element type="segment" label="q">
<show object="false" label="false" ev="4"/>
<objColor r="153" g="51" b="0" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<auxiliary val="true"/>
<coords x="NaN" y="NaN" z="NaN"/>
<lineStyle thickness="5" type="0" typeHidden="1" opacity="178"/>
<outlyingIntersections val="false"/>
<keepTypeOnTransform val="true"/>
</element>
<element type="segment" label="s">
<show object="true" label="false" ev="4"/>
<objColor r="153" g="51" b="0" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<auxiliary val="true"/>
<coords x="NaN" y="NaN" z="NaN"/>
<lineStyle thickness="5" type="0" typeHidden="1" opacity="178"/>
<outlyingIntersections val="false"/>
<keepTypeOnTransform val="true"/>
</element>
<element type="segment" label="j">
<show object="true" label="false" ev="4"/>
<objColor r="153" g="51" b="0" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<auxiliary val="true"/>
<coords x="NaN" y="NaN" z="NaN"/>
<lineStyle thickness="5" type="0" typeHidden="1" opacity="178"/>
<outlyingIntersections val="false"/>
<keepTypeOnTransform val="true"/>
</element>
<element type="segment" label="k">
<show object="true" label="false" ev="4"/>
<objColor r="153" g="51" b="0" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<auxiliary val="true"/>
<coords x="NaN" y="NaN" z="NaN"/>
<lineStyle thickness="5" type="0" typeHidden="1" opacity="178"/>
<outlyingIntersections val="false"/>
<keepTypeOnTransform val="true"/>
</element>
<element type="point" label="C">
<show object="false" label="true" ev="4"/>
<objColor r="68" g="68" b="68" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<auxiliary val="true"/>
<coords x="1.6600000000000001" y="3.4799999999999995" z="1.0"/>
<pointSize val="5"/>
<pointStyle val="0"/>
</element>
<element type="point" label="G">
<show object="false" label="true" ev="4"/>
<objColor r="68" g="68" b="68" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<auxiliary val="true"/>
<coords x="-1.2599999999999996" y="3.46" z="1.0"/>
<pointSize val="5"/>
<pointStyle val="0"/>
</element>
<element type="point" label="I">
<show object="false" label="true" ev="4"/>
<objColor r="68" g="68" b="68" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<auxiliary val="true"/>
<coords x="NaN" y="NaN" z="NaN"/>
<pointSize val="5"/>
<pointStyle val="0"/>
</element>
<element type="point" label="K">
<show object="false" label="true" ev="4"/>
<objColor r="68" g="68" b="68" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<auxiliary val="true"/>
<coords x="NaN" y="NaN" z="NaN"/>
<pointSize val="5"/>
<pointStyle val="0"/>
</element>
<element type="point" label="F">
<show object="false" label="true" ev="4"/>
<objColor r="68" g="68" b="68" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<auxiliary val="true"/>
<coords x="NaN" y="NaN" z="NaN"/>
<pointSize val="5"/>
<pointStyle val="0"/>
</element>
<element type="point" label="H">
<show object="false" label="true" ev="4"/>
<objColor r="68" g="68" b="68" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<auxiliary val="true"/>
<coords x="NaN" y="NaN" z="NaN"/>
<pointSize val="5"/>
<pointStyle val="0"/>
</element>
<expression label="D" exp="(A + B) / 2 + ((f / 2 * cot(π / n)) * UnitOrthogonalVector[Line[A, B]])" type="point" />
<element type="point" label="D">
<show object="false" label="true" ev="4"/>
<objColor r="68" g="68" b="68" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<coords x="0.20999999999999996" y="2.0100000000000002" z="1.0"/>
<pointSize val="4"/>
<pointStyle val="0"/>
</element>
<command name="Point">
<input a0="poly1"/>
<output a0="L"/>
</command>
<element type="point" label="L">
<show object="true" label="true" ev="4"/>
<objColor r="125" g="125" b="255" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<animation step="0.1" speed="1" type="1" playing="false"/>
<coords x="1.6691927792603347" y="2.1378542279911548" z="1.0"/>
<pointSize val="5"/>
<pointStyle val="0"/>
</element>
<command name="Point">
<input a0="OrthogonalLine[D, Line[D, L]]"/>
<output a0="E"/>
</command>
<element type="point" label="E">
<show object="true" label="true" ev="4"/>
<objColor r="125" g="125" b="255" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<animation step="0.1" speed="1" type="1" playing="false"/>
<coords x="0.2504118929307009" y="1.5487814444055759" z="1.0"/>
<pointSize val="5"/>
<pointStyle val="0"/>
</element>
<command name="Line">
<input a0="E" a1="Vector[D, L]"/>
<output a0="i"/>
</command>
<element type="line" label="i">
<show object="true" label="true"/>
<objColor r="0" g="0" b="0" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<coords x="-0.12785422799115453" y="1.4591927792603347" z="-2.2279544810785494"/>
<lineStyle thickness="5" type="0" typeHidden="1" opacity="178"/>
<eqnStyle style="implicit"/>
</element>
<expression label="a" exp="a(x, y) = LeftSide[i] - RightSide[i]" />
<element type="functionNVar" label="a">
<show object="true" label="true"/>
<objColor r="219" g="97" b="20" alpha="0.75"/>
<layer val="0"/>
<labelMode val="0"/>
<lineStyle thickness="1" type="0" typeHidden="1"/>
</element>
<expression label="l1" exp="{}"/>
<element type="list" label="l1">
<show object="false" label="true"/>
<objColor r="0" g="100" b="0" alpha="-1.0"/>
<layer val="0"/>
<labelMode val="0"/>
<animation step="0.1" speed="1" type="0" playing="false"/>
<lineStyle thickness="5" type="0" typeHidden="1"/>
<pointSize val="5"/>
<angleStyle val="0"/>
</element>
<command name="Element" type="point">
<input a0="{Intersect[i, poly1]}" a1="1"/>
<output a0="M"/>
</command>
<element type="point" label="M">
<show object="false" label="true" ev="4"/>
<objColor r="68" g="68" b="68" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<coords x="-1.2460114046890696" y="1.4176650846041412" z="1.0"/>
<pointSize val="4"/>
<pointStyle val="0"/>
</element>
<command name="Point">
<input a0="OrthogonalLine[M, i]"/>
<output a0="J"/>
</command>
<element type="point" label="J">
<show object="true" label="true" ev="4"/>
<objColor r="125" g="125" b="255" alpha="0.0"/>
<layer val="0"/>
<labelMode val="0"/>
<animation step="0.1" speed="1" type="1" playing="false"/>
<coords x="-1.2475970291811542" y="1.435761723611092" z="1.0"/>
<pointSize val="5"/>
<pointStyle val="0"/>
</element>
<command name="ConvexHull">
<input a0="Flatten[Join[{RemoveUndefined[Zip[If[a(x(p), y(p)) ≤ 0, Append[l1, p]], p, {Vertex[poly1]}]], {Intersect[i, poly1]}}]]"/>
<output a0="graph1"/>
</command>
<element type="locus" label="graph1">
<show object="true" label="false" ev="4"/>
<objColor r="255" g="127" b="0" alpha="0.550000011920929"/>
<layer val="0"/>
<labelMode val="0"/>
<auxiliary val="false"/>
<lineStyle thickness="5" type="0" typeHidden="1" opacity="178"/>
</element>
<command name="ConvexHull">
<input a0="Flatten[Join[{RemoveUndefined[Zip[If[a(x(p), y(p)) > 0, Append[l1, p]], p, {Vertex[poly1]}]], {Intersect[i, poly1]}}]] + Vector[M, J]"/>
<output a0="graph2"/>
</command>
<element type="locus" label="graph2">
<show object="true" label="false" ev="4"/>
<objColor r="0" g="100" b="0" alpha="0.6800000071525574"/>
<layer val="0"/>
<labelMode val="0"/>
<auxiliary val="false"/>
<lineStyle thickness="5" type="0" typeHidden="1"/>
</element>
</construction>
</geogebra>