search

bakkemo / elm-collision

Efficient collision detection for Elm
BSD 3-Clause "New" or "Revised" License
10 stars 4 forks source link

Test point in polygon #1

Closed vilterp closed 9 years ago

vilterp commented 9 years ago

Hi, cool lib! Can this be easily used to test whether a point is in a polygon? Would like to use for this: https://github.com/vilterp/elm-diagrams/issues/22

bakkemo commented 9 years ago

Yes. Thinking of the point as its own polygon, then the point of the polygon furthest in any direction is just the point itself. so your Mink would be (Pt, Identity). Conceptually, consider the Minkowski difference when the point is in the polygon, it's sharing a point with a point in the polygon, thus it MUST be the origin in the minkowski sum. Thus the since it's IN the polygon, the Minkowski sum contains the origin. Make sense?

bakkemo commented 9 years ago

Yup, as long as the polygon is convex, or broken up into convex pieces.

On Mon, Apr 20, 2015 at 5:56 PM, Pete Vilter notifications@github.com wrote:

Hi, cool lib! Can this be easily used to test whether a point is in a polygon? Would like to use for this: vilterp/elm-diagrams#22 https://github.com/vilterp/elm-diagrams/issues/22

— Reply to this email directly or view it on GitHub https://github.com/bakkemo/elm-collision/issues/1.

vilterp commented 9 years ago

Cool. Might be useful to have that as a helper function for those not read up on Minkowski stuff such as myself.

Also, out of curiosity, how much harder is it to do this for non-convex polygons? A completely different algorithm I assume?

bakkemo commented 9 years ago

I added a note at the end of the readme about it. On the second point, You might be able to use the separating axis theorem (SAT) for your concave shapes, but I've only seen it used after triangulation. Also, SAT performs poorly the more verticies you have (probably another reason for pre-tesselation). My advice would be to triangulate your polygons and use GJK.

On Tue, Apr 21, 2015 at 12:05 AM, Pete Vilter notifications@github.com wrote:

Cool. Might be useful to have that as a helper function for those not read up on Minkowski stuff such as myself.

Also, out of curiosity, how much harder is it to do this for non-convex polygons? A completely different algorithm I assume?

— Reply to this email directly or view it on GitHub https://github.com/bakkemo/elm-collision/issues/1#issuecomment-94660513.