Re: Intersection of polygons and more
- To: mathgroup at smc.vnet.net
- Subject: [mg30403] Re: Intersection of polygons and more
- From: "Alan Mason" <amason2 at austin.rr.com>
- Date: Wed, 15 Aug 2001 01:04:10 -0400 (EDT)
- References: <9lal4i$cc6$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Hello.
Either those aren't polygons, or I'm ready to give up mathematics and enter
a convent.
Anyhow, I have an n-dimensional Voronoi code that treats some related
problems. By keeping a list of the (affine, hyper) planes that determine
the faces of the polyhedron (or a polygon in 2D), one can find the
intersection of two such polyhedra as the set of points for which all the
planes in both lists evaluate to <= 0. The built-in function LinearSolve[]
is useful for converting from "canonical" form (lists of planes) to
"standard" form ({set of vectors spanning the intersection}, Pt}, where Pt
lies in the intersection). The faces of the intersection can be found
combinatorially from the plane lists. It's a good exercise in linear
algebra.
Alan
<WizardPaul at aol.com> wrote in message news:9lal4i$cc6$1 at smc.vnet.net...
> I'm trying to devise a fast way to intersect polygons. For example, if I
> have:
>
> poly1 = Table[{0.6 + Cos[2 + Cos[t]]*Sin[t/3], Sin[t/3]*Sin[2 + Cos[t]] -
> 0.2}, {t, Pi/2, (5/2)*Pi, 0.2}]
>
> poly2 = Table[{0.8 Cos[t], 0.8 Sin[t]}, {t, 4, 4 + 2Pi, 0.2}]
>
> What's the fastest way to get something like this?:
>
> {{0.391927, 0.254649}, {0.472822, 0.341857}, {0.57571, 0.410207},
> {0.664196, 0.445919}, {0.603122, 0.525589}, {0.486681, 0.634934},
> {0.350838, 0.718966}, {0.288021, 0.746354}, {0.131601, 0.683303},
> {-0.0301305, 0.571709}, {-0.156521, 0.43601}, {-0.242242, 0.293184},
> {-0.289192, 0.160103}, {-0.304406, 0.0503182}, {-0.296871, -0.0275226},
> {-0.274492, -0.0697097}, {-0.242073, -0.0766683},
{-0.200641, -0.0520995},
> {-0.148065, -0.00248934}, {-0.0806987, 0.0631007}, {0.00436518,
0.133429},
> {0.107061, 0.196173}, {0.222934, 0.239917}, {0.343236, 0.256572}}
>
> Notice the addition of points {0.288021, 0.746354} and {0.664196,
0.445919}.
>
>
> Since they are very closely related functions, how about for subtraction:
>
> {{0.664196, 0.445919}, {0.57571, 0.410207}, {0.472822, 0.341857},
> {0.391927, 0.254649}, {0.343236, 0.256572}, {0.222934, 0.239917},
> {0.107061, 0.196173}, {0.00436518, 0.133429}, {-0.0806987, 0.0631007},
> {-0.148065, -0.00248934}, {-0.200641, -0.0520995},
> {-0.242073, -0.0766683}, {-0.274492, -0.0697097},
{-0.296871, -0.0275226},
> {-0.304406, 0.0503182}, {-0.289192, 0.160103}, {-0.242242, 0.293184},
> {-0.156521, 0.43601}, {-0.0301305, 0.571709}, {0.131601, 0.683303},
> {0.288021, 0.746354}, {0.201008, 0.774336}, {0.0431643, 0.798835},
> {-0.1164, 0.791487}, {-0.271324, 0.752584}, {-0.415431, 0.683679},
> {-0.542976, 0.587518}, {-0.648874, 0.467934}, {-0.728904, 0.329695},
> {-0.779875, 0.178312}, {-0.799754, 0.0198203}, {-0.78775, -0.139461},
> {-0.744341, -0.293183}, {-0.671257, -0.435217}, {-0.571413, -0.5599},
> {-0.522915, -0.605442}, {-0.392209, -0.697261}, {-0.245866, -0.761282},
> {-0.089722, -0.794953}, {0.0699992, -0.796932}, {0.22693, -0.767139},
> {0.374813, -0.706764}, {0.507754, -0.618212}, {0.620453, -0.505013},
> {0.708416, -0.371682}, {0.768136, -0.223532}, {0.797234, -0.0664715},
> {0.794548, 0.0932394}, {0.760186, 0.249233}, {0.695518, 0.395291}}
>
> and addition (union):
>
> {{0.664196, 0.445919}, {0.689398, 0.456023}, {0.801922, 0.481245},
> {0.902855, 0.492509}, {0.984458, 0.499028}, {1.0415, 0.510113},
> {1.07021, 0.532997}, {1.06716, 0.571203}, {1.02882, 0.623506},
> {0.952175, 0.683546}, {0.836368, 0.74035}, {0.68479, 0.780088},
> {0.506533, 0.789118}, {0.316201, 0.757722}, {0.288021, 0.746354},
> {0.201008, 0.774336}, {0.0431643, 0.798835}, {-0.1164, 0.791487},
> {-0.271324, 0.752584}, {-0.415431, 0.683679}, {-0.542976, 0.587518},
> {-0.648874, 0.467934}, {-0.728904, 0.329695}, {-0.779875, 0.178312},
> {-0.799754, 0.0198203}, {-0.78775, -0.139461}, {-0.744341, -0.293183},
> {-0.671257, -0.435217}, {-0.571413, -0.5599}, {-0.522915, -0.605442},
> {-0.392209, -0.697261}, {-0.245866, -0.761282}, {-0.089722, -0.794953},
> {0.0699992, -0.796932}, {0.22693, -0.767139}, {0.374813, -0.706764},
> {0.507754, -0.618212}, {0.620453, -0.505013}, {0.708416, -0.371682},
> {0.768136, -0.223532}, {0.797234, -0.0664715}, {0.794548, 0.0932394},
> {0.760186, 0.249233}, {0.695518, 0.395291}}
>
> Again with the additional points {0.288021, 0.746354} and {0.664196,
> 0.445919}.
>
> Exclusion would also be useful.
>
> Those two added points in each case are simply "eyeballed" points of
> intersection.
>
> Lastly, is it possible to do similar (boolean) operations on
parametrically
> described shapes?
>
> Thanks,
>
> Paul
>