Polygon and Circle intersection

[Bron Davies]

How can I tell if a circle is wholly inside a polygon?  geometry.intersection doesn't work in this scenario

[szymon.m...@gmail.com]

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.

Szymon

[Aaron Meurer]

On Tue, Apr 4, 2017 at 5:12 AM <szymon.m...@gmail.com> 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. 

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 sympy+un...@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
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.

[Aaron Meurer]

On Tue, Apr 4, 2017 at 6:45 PM Aaron Meurer <asme...@gmail.com> wrote:

On Tue, Apr 4, 2017 at 5:12 AM <szymon.m...@gmail.com> 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). 

Aaron Meurer 

[Aaron Meurer]

On Tue, Apr 4, 2017 at 6:48 PM, Aaron Meurer <asme...@gmail.com> wrote:
>
> On Tue, Apr 4, 2017 at 6:45 PM Aaron Meurer <asme...@gmail.com> wrote:
>>
>> On Tue, Apr 4, 2017 at 5:12 AM <szymon.m...@gmail.com> 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

[szymon.m...@gmail.com]

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.

[Chris Smith]

>>> diamond

RegularPolygon(Point2D(0, 0), 1, 4, 0)

>>> diamond.encloses(Circle((0,0), S.Half))  # circle in diamond

True

>>> diamond.encloses(Circle((0,0), S.One))  # circle circumscribes diamond

False

>>> diamond.encloses(Circle((S.Half, 0), S.One)) # circle intersects on right of diamond

False

>>> diamond.encloses(Circle((5, 0), S.One)) # circle outside of diamond

False

(The test of circle point inclusion and poly-ellipse intersection can be seen in the entity.py file in the encloses function.

The reverse, ellipse-polygon intersection, was not defined, however, and I remedy that in a PR.)