Jump to content

Bézier curves/Intersections: Difference between revisions

Bézier curves/Intersections (view source)

Revision as of 10:30, 7 June 2023

24,054 bytes added ,  1 year ago
→‎{{header|Phix}}
(Added Wren)
Line 967:
(-0.6810249, 2.68102500)
(-0.8549834, 1.34501657)</pre>
 
=={{header|Phix}}==
{{trans|D}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">enum</span> <span style="color: #000000;">X</span><span style="color: #0000FF;">,</span><span style="color: #000000;">Y</span>
<span style="color: #008080;">type</span> <span style="color: #000000;">quadratic_spline</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- return apply(c,sq_atom)={1,1,1} -- oops, requires 1.0.3...</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span> <span style="color: #000080;font-style:italic;">-- this will do instead for 1.0.2 and earlier</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">type</span>
<span style="color: #008080;">type</span> <span style="color: #000000;">quadratic_curve</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- return apply(c,sq_atom)=<nowiki>{{</nowiki>1,1,1},{1,1,1<nowiki>}}</nowiki> -- ditto</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">type</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">subdivide_quadratic_spline</span><span style="color: #0000FF;">(</span><span style="color: #000000;">quadratic_spline</span> <span style="color: #000000;">q</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">// Subdivision by de Casteljau's algorithm.</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">c0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">q</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> <span style="color: #0000FF;">-</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">u1</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">s</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">c0</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">+</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">t</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">c1</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">v1</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">s</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">c1</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">+</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">t</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">c2</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">s</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">u1</span><span style="color: #0000FF;">)</span> <span style="color: #0000FF;">+</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">t</span> <span style="color: #0000FF;">*</span> <span style="color: #000000;">v1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">c0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">u1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c2</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">subdivide_quadratic_curve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">quadratic_curve</span> <span style="color: #000000;">q</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">px</span><span style="color: #0000FF;">,</span><span style="color: #000000;">qx</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">subdivide_quadratic_spline</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">),</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">py</span><span style="color: #0000FF;">,</span><span style="color: #000000;">qy</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">subdivide_quadratic_spline</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">px</span><span style="color: #0000FF;">,</span><span style="color: #000000;">py</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">qx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">qy</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">rectangles_overlap</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">xa0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ya0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">xa1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ya1</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">xb0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">yb0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">xb1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">yb1</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">// It is assumed that xa0&lt;=xa1, ya0&lt;=ya1, xb0&lt;=xb1, and yb0&lt;=yb1.</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">xb0</span> <span style="color: #0000FF;"><=</span> <span style="color: #000000;">xa1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">xa0</span> <span style="color: #0000FF;"><=</span> <span style="color: #000000;">xb1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">yb0</span> <span style="color: #0000FF;"><=</span> <span style="color: #000000;">ya1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">ya0</span> <span style="color: #0000FF;"><=</span> <span style="color: #000000;">yb1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">test_intersection</span><span style="color: #0000FF;">(</span><span style="color: #000000;">quadratic_curve</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">q</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">tolerance</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">pxmin</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]),</span>
<span style="color: #000000;">pymin</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">]),</span>
<span style="color: #000000;">pxmax</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]),</span>
<span style="color: #000000;">pymax</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">]),</span>
<span style="color: #000000;">qxmin</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]),</span>
<span style="color: #000000;">qymin</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">]),</span>
<span style="color: #000000;">qxmax</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]),</span>
<span style="color: #000000;">qymax</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">rectangles_overlap</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pxmin</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pymin</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pxmax</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pymax</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">qxmin</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">qymin</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">qxmax</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">qymax</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">xmin</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pxmin</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">qxmin</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">xmax</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pxmax</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">qxmax</span><span style="color: #0000FF;">);</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xmax</span> <span style="color: #0000FF;">>=</span> <span style="color: #000000;">xmin</span><span style="color: #0000FF;">);</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">xmax</span><span style="color: #0000FF;">-</span><span style="color: #000000;">xmin</span> <span style="color: #0000FF;"><=</span> <span style="color: #000000;">tolerance</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">ymin</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pymin</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">qymin</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">ymax</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">pymax</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">qymax</span><span style="color: #0000FF;">);</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ymax</span> <span style="color: #0000FF;">>=</span> <span style="color: #000000;">ymin</span><span style="color: #0000FF;">);</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ymax</span><span style="color: #0000FF;">-</span><span style="color: #000000;">ymin</span> <span style="color: #0000FF;"><=</span> <span style="color: #000000;">tolerance</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- we found a suitable intersection!</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{(</span><span style="color: #000000;">xmin</span><span style="color: #0000FF;">+</span><span style="color: #000000;">xmax</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,(</span><span style="color: #000000;">ymin</span><span style="color: #0000FF;">+</span><span style="color: #000000;">ymax</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span> <span style="color: #000080;font-style:italic;">-- accept/further subdivide</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #000080;font-style:italic;">-- exclude</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">find_intersections</span><span style="color: #0000FF;">(</span><span style="color: #000000;">quadratic_curve</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">q</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">tolerance</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">intersections</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span>
<span style="color: #000000;">todo</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">}}</span>
<span style="color: #000080;font-style:italic;">-- while length(intersections)!=4 and length(todo) do</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">todo</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- (we may as well be thorough)</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q</span><span style="color: #0000FF;">},</span><span style="color: #000000;">todo</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">todo</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">todo</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..$]}</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">insect</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">test_intersection</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">q</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tolerance</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #004080;">sequence</span><span style="color: #0000FF;">(</span><span style="color: #000000;">insect</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">intersections</span> <span style="color: #0000FF;">&=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">insect</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">insect</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">sequence</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">subdivide_quadratic_curve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0.5</span><span style="color: #0000FF;">),</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">q1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">subdivide_quadratic_curve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">q</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0.5</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">todo</span> <span style="color: #0000FF;">&=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">q1</span><span style="color: #0000FF;">}}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">intersections</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #000000;">quadratic_curve</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}},</span>
<span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">}}</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">intersections</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">find_intersections</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">q</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0.000001</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">pp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">intersections</span><span style="color: #0000FF;">,{</span><span style="color: #004600;">pp_Nest</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
{{0.6549830437,2.854983807},
{0.8810248375,1.118975163},
{-0.6810250282,2.681025028},
{-0.8549838066,1.345016956}}
</pre>
 
=={{header|Wren}}==
Petelomax
7,830

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/344253"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information