Check of point inside/outside polygon

[H. S. Teoh via Digitalmars-d-learn]

On Tue, Jul 26, 2016 at 01:32:00PM +0000, Suliman via Digitalmars-d-learn wrote:
> Ideally I need algorithm that can return bool if one polygon
> overlapped/intersected by another. But I do not know math.

Are you talking about triangles, or general polygons?  Are the polygons
convex or arbitrary?  Depending on what kind of polygon it is, the
solution may be more or less complex.  If you're dealing with convex
polygons (including triangles -- though you can probably simplify things
a bit more for triangles), take a look at this:

	http://www.iro.umontreal.ca/~plante/compGeom/algorithm.html

If your polygons are non-convex, the solution will be quite complicated
and may not have good performance. You might want to consider various
algorithms for decomposing such polygons into convex pieces for easier
handling.


> After some googling I found topic on SO[1] about point inside/outside
> polygon. It's not directly what I need, but as temporal solution would
> be enough.
[...]

This approach may not be as straightforward as you think.  Consider two
equilateral triangles inscribed inside a regular hexagon (i.e., "David's
Star", or the 6/3 star polygon).  Neither of the triangles's vertices
lie inside the other triangle, yet the two triangles do intersect each
other. You may say, test the centers of the polygons too, however, it's
easy to come up with other pairs of polygons where the respective
centers don't lie in the other polygon but the two polygons nevertheless
still intersect.  You need a general algorithm for finding the
intersection; point-sampling generally is not good enough.


T

-- 
Gone Chopin. Bach in a minuet.