> > Won't this also pass sometimes if the polygon is inside the circle? > No, because random points are taken from circle not disk, so if polygon is inside the circle, border of circle is outside of polygon.
if the circle circumscribes > We check this in intersection method. If they have any common point, we know that circle is not wholly in polygon. And you also have to handle the case where neither is inside the other > (this random points method won't help you here). > Yes, I should wrote also that, but for my solution it doesn't matter. We need only know if every point from circle is inside polygon or outside. We can get it using intersection. W dniu środa, 5 kwietnia 2017 01:03:40 UTC+2 użytkownik Aaron Meurer napisał: > > On Tue, Apr 4, 2017 at 6:48 PM, Aaron Meurer <[email protected] > <javascript:>> wrote: > > > > On Tue, Apr 4, 2017 at 6:45 PM Aaron Meurer <[email protected] > <javascript:>> wrote: > >> > >> On Tue, Apr 4, 2017 at 5:12 AM <[email protected] <javascript:>> > wrote: > >>>> > >>>> geometry.intersection doesn't work in this scenario > >>> > >>> In what sense in doesn't work? Is it broken? > >>> > >>> You can find if a circle is wholly inside a polygon in two steps: > >>> 1) find if they intersect each other: > >>> your_polygon = Polygon(Point(a, b), ...) > >>> your_circle = Circle(Point(c, d), radius) > >>> your_polygon.intersection(your_circle) > >>> If you get empty list you know that circle is inside the polygon or > >>> polygon is inside the circle. > >>> > >>> 2)Now you should check if random point from circle is enclosed by > >>> polygon: > >>> your_ polygon.encloses_point(your_circle.random_point()) > >>> If you get True, you know that circle is inside polygon. > >> > >> > >> Won't this also pass sometimes if the polygon is inside the circle? > >> > >> I think you would need to pick random points in each until you find one > >> that is in one and not the other. However, if the circle circumscribes > the > >> polygon and it is very convex (or the other way around), there may be a > low > >> probability of finding the desired point. So a more direct solution > would be > >> preferred. > > > > > > And you also have to handle the case where neither is inside the other > (this > > random points method won't help you here). > > I suppose that case is still handled. I believe the correct algorithm > is something like: > > contains(A, B) (pseudocode): > if A and B intersect, then > return False > while True > Let a be a random point in A and b a random point in B > if a is in B and b is in A, then > continue > if a is in B and b is not in A, then > return B is inside of A > if a is not in B and b is in A, then > return A is inside of B > if a is not in B and b is not in A, then > return False (the sets are disjoint, because of the > intersection check above) > > But again, it is not hard to construct examples where the probability > of finding a point in the symmetric difference is low, meaning the > loop will take a long time. Perhaps instead of checking points in the > shape, you should check points on the boundary. If the intersection > check is correct, the first case (a in B and b in A) will be > impossible. > > Aaron Meurer > > > > > Aaron Meurer > >> > >> > >> Aaron Meurer > >> > >>> > >>> > >>> Szymon > >>> > >>> W dniu poniedziałek, 3 kwietnia 2017 23:53:03 UTC+2 użytkownik Bron > >>> Davies napisał: > >>>> > >>>> How can I tell if a circle is wholly inside a polygon? > >>>> geometry.intersection doesn't work in this scenario > >>> > >>> -- > >>> You received this message because you are subscribed to the Google > Groups > >>> "sympy" group. > >>> To unsubscribe from this group and stop receiving emails from it, send > an > >>> email to [email protected] <javascript:>. > >>> To post to this group, send email to [email protected] > <javascript:>. > >>> Visit this group at https://groups.google.com/group/sympy. > >>> To view this discussion on the web visit > >>> > https://groups.google.com/d/msgid/sympy/f782bdff-56b5-42af-815c-3901bd807b60%40googlegroups.com. > > > >>> For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "sympy" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/sympy. To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/561019bd-27c4-4a80-a02b-3d54b9fc957e%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
