After a long absence, I returned to continue playing CheckIO tasks by a notification mail. The UI had been optimized a lot and the tasks were still as interesting as the before.
Inside Block required checking whether a given point is inside a polygon or not. After some research on google, I found a practical method.
Given a polygon and a point ‘p’, find if ‘p’ lies inside the polygon or not. The points lying on the border are considered inside.
We can check whether the point is inside or outside by following three simple steps:
I do think this approach is simple enough with only one question need to be solved
Given two line segments (p1, q1) and (p2, q2), find if the given line segments intersect with each other.
Before we discuss the solution, let us define the notion of orientation. Orientation of an ordered triplet of points in the plane can be
The following diagram shows different possible orientations of (a, b, c)
Two segments (p1,q1) and (p2,q2) intersect if and only if one of the following two conditions is verified
Examples of General Case:
Examples of Special Case:
I really thought everything would go smoothly according to the method described above, but an unexpected error showed to me. Considering the following situation:
The line intersects with the point that connects two segments. This leads the programme considers the there are two intersections and determines the point is outside of the polygon.
To deal with this problem, we could think the line is a half-divider that cut the segment that it intersects into two halves. So every time it intersects a segment, we can double the length of this segment to solve this problem
I didn’t put the code in the post because I think you can solve it after knowing this method. In case you really want to directly read the code, here is the link for my checkio solutions repo. Please give me a star if you like it.