0
$\begingroup$

When the line segments that form closed shape is given how to check whether the given point lies inside the diagram or not

for example enter image description here AB ,BC ,CD,DE,EA are the line segments given and i know the co-ordinates of endpoints each line segment . Now how to find whether a given point is inside the diagram or not ?

My approach: By using ray casting or winding number for checking whether the point is inside or not . But i am struck at "how to find the vertices of polygon"

$\endgroup$
1
  • $\begingroup$ This link and this one seem relevant. But it appears to me that your problem isn't with using ray casting or winding numbers, but how to convert a set of line segments to a polygon. Is this correct? $\endgroup$
    – Jens
    May 6 '18 at 1:03
0
$\begingroup$

You need to find the equations of your segments, and try parallel lines.

If a point is inside a triangle every line parallel to a side of triangle and passing through that point will intersect the other two sides at points between vertices.

On the other hand for a point outside the triangle one of the lines parallel to the three sides do not intersect the triangle at all.

Same is true for the pentagon.

$\endgroup$
6
  • $\begingroup$ The above only seems to work for convex polygons. $\endgroup$
    – Jens
    May 6 '18 at 0:45
  • $\begingroup$ That is what I meant, you need to check each triangle and the pentagon which are convex. $\endgroup$ May 6 '18 at 1:46
  • $\begingroup$ The above methld won't work for every case ... Sometimes the diagram may be concave also $\endgroup$
    – user1608
    May 6 '18 at 5:50
  • $\begingroup$ I agree we have to divide the region into conves subregions and work with each section separately. $\endgroup$ May 6 '18 at 8:39
  • $\begingroup$ i think this method is more complicated to implement and have more time complexity. I am searching for efficient algorithm $\endgroup$
    – user1608
    May 6 '18 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.