3

The polygon may or may not be convex. We can assume that the edges of the square align with X and Y axis.

Calculating the intersection [A simple algorithm for polygon intersection]1 is an over-kill, as I only need to know whether they intersect (Yes or No).

Community
  • 1
  • 1
Shen Li
  • 411
  • 3
  • 14
  • Look at the Sutherland-Hodgman polygon clipping algorithm - it may give you some idea... If you are left with no vertices at the end - it means that the whole polygon is outside the clipping area, which in your case is the square: https://www.youtube.com/watch?v=Euuw72Ymu0M – SomethingSomething May 19 '15 at 21:08
  • I actually meant to say that you can do a "reduction" and convert your problem to polygon clipping problem - in which we want to remove the polygon parts that are outside the clipping area. So in your case, you can treat the square as the clipping area and the polygon as the polygon. If you finally stay with no vertices - your all polygon is outside the clipping area. If you finally have a group of some vertices, it means that some parts of the polygon are internal to the clipping area, so in your case it will mean that there is an intersection – SomethingSomething May 19 '15 at 21:11
  • By _intersect_, do you mean at least one edge of the square crosses at least one edge of the polygon? If the square completely contains the polygon (or vice versa) without an actual edge crossing, would you consider that an intersection? – Adrian McCarthy May 19 '15 at 22:48
  • I apologize about the confusing definition. I should have mentioned that by intersect I actually mean overlap. If there exists any point that is within both the polygon and the square, they are considered intersected. – Shen Li May 20 '15 at 00:51

2 Answers2

2

I am not sure that it is the best known algorithm (actually I am more sure that there are better and known ones), but I am sure this solution should work.

The idea is to do a "reduction" of the problem into a problem of polygon clipping into a clipping area (i.e. convert the problem into a different one and solve it with an algorithm that solves the new problem). Do the reduction such that:

  • If you finally got some parts of the polygon left inside the clipping area - then there is an intersection
  • If you finally have an empty set of polygon-vertices - i.e. you got nothing inside the clipping area - then there is no intersection

The Sutherland-Hodgman algorithm for polygon clipping does that - If the polygon crosses the clipping area - it will finally supply you a list of vertices that represent the clipped polygon. If the polygon is totally outside the clipping area (i.e. no intersection) - then it will finally supply you an empty list, as actually there is no part of the polygon that can be drawn inside the clipping area.

You can find explanation about the Sutherland-Hodgman algorithm for clipping polygons here: https://www.youtube.com/watch?v=Euuw72Ymu0M

SomethingSomething
  • 11,491
  • 17
  • 68
  • 126
1

You could just iterate over the edges of your polygon and check whether one of them intersect your square. If one does then you are done. Otherwise just test whether either 1) the center of the square belongs to the polygon 2) an arbitrary point in the polygon belongs to the square or 3) none of 1) and 2) hold. In case 1) and 2) they do overlap, in case 3) they don't.

vib
  • 2,254
  • 2
  • 18
  • 36
  • Thanks for the simple and effective algorithm. I am planning to use this as a subroutine for a quad-tree. In the context of a quad-tree, is it possible to further speed-up the algorithm? – Shen Li May 20 '15 at 13:56
  • How do you represent your polygon in the quad-tree exactly ? – vib May 20 '15 at 14:23
  • Thanks @vib There will be some loss of precision. I plan to use a quad-tree of height h to represent the polygon, such that all tiles at level h that intersect with the polygon will be kept, and other tiles will be discarded. There will also be some pruning. For example, if the tile of some internal node in the quad-tree is completely covered by the polygon, then there is no need to further go deeper through this node. – Shen Li May 20 '15 at 17:41