Search code examples
geometryconstraintscomputational-geometryarea

An algorithm for check if a dot(x,y) in inside an area?

Let's say that every black line in this picture can be described as an equation y = Ki*x + Mi where Ki is the i:th slope and Mi is the i:th bias of the straight line equation. I also know the dots of every corner of the lines.

The blue is my data. My problem here is that I want to pick a dot with the coordinates x,y and place it inside the area that the lines create, then I'm going to get a YES or NO back.

But I don't know how to do that. My question is: Is there an algorithm for this problem, or do I have to use a lot of if-statements to solve this kind of area issue?

enter image description here

Solution

  • Check that the sign of (y - Ki * x - Mi) is positive for all bottom edges and negative for all top edges.

    enter image description here

    For N sides, this is exactly N tests :-)

    If you don't know which are the bottom and top edges, you can test if the signs are the same as for any point known to be inside.