Hello again.  I want to explain some basic geometric algorithms to solve a known problem which is Finding Intersection Polygon of two Convex Polygons. I know it is not a new problem, but it is a good example of using solutions of sub-problems to solve a more complex problem.  And I want to keep the main algorithm as simple as possible.

I won’t discover those basic algorithms from scratch but I will try to make some briefs about main ideas behind them. First, let me write the main algorithm to the problem in terms of simple geometric operations;

  1. Create an empty polygon as P
  2. Add all corners of Polygon1 that is inside Polygon2 to P
  3. Add all corners of Polygon2 that is inside Polygon1 to P
  4. Add all intersection points to P
  5. Order all points in the P counter-clockwise.

As you see the algorithm looks much simpler when you write it in terms of some basic geometric operation. Now it is time to implement those basic Geometric operations.  Those are:

  • GetIntersectionPoint: Finds intersection point of given line-segments.
  • GetIntersectionPoints: Finds intersection point of given line segment and a polygon
  • IsPointInsidePoly: Checks if a given point is inside a given convex polygon.

We can write a small Geo-Library to put those helper methods which is GeometryHelper. I add utility code as initial to deal with floating-point issues.  

And Before we start, it is better to write our own data types

Finding Intersection Point of two line segments

We can use Linear algebra to calculate the intersection point of two given line segment.

The equation of a line in a 2-D space is written as:

Line:   Ax+By = C

So, for given points (x1, y1) and (x2, y2), we can calculate A, B, C values:

A = y2-y1
B = x1-x2
C = A*x1+B*y1

After we calculate A, B, C values for two line segments intersection point can be calculated as follow;

Let’s Write the code for the function;

Check if a given point is inside a convex polygon

I took a simple solution which I like beyond many others from a web-site and adapt it to my project.

https://wrf.ecse.rpi.edu//Research/Short_Notes/pnpoly.html

You can check the site for its background. Since it is not my main purpose I won’t deep dive into it. In short,  it basically assumes a semi-infinite horizontal ray from the check-point and counts how many times it intersects with the polygon. (Jordan curve theorem)

Finding Intersection Points of a line segment and given convex polygon

This is so easy when we have  GetIntersectionPoint ready. We simply try line segment with each edge of the polygon and return the collection of intersection points.

One Important Tip

Some edge cases, such as two overlapping corners or intersection on a corner can cause some duplicates corner added to the polygon. We can easily get rid of these with such small utility function:

Ordering the corners of a polygon clockwise

After we find all the corners, all we need to order them to be able to draw it properly.  This can be done, by calculating the center point first and then sorting them against the arcTan values of between the center point, corner and a horizontal line.  You can see how I do this below;

We are ready to write the main algorithm

So since we have each geometric operation implemented, let’s write the method to get the intersection polygon:

To sum up, I hope it has not been a just another copy of widely spread code-blocks about geometric algorithms.  My main purpose is to point out a lean approach to develop a bigger algorithm in terms of well-written sub-algorithms.

Hope you enjoy it! 🙂

References 

[1] PNPOLY – Point Inclusion in Polygon Test – WR Franklin (WRF)
https://wrf.ecse.rpi.edu//Research/Short_Notes/pnpoly.html

[2] 2D Line Intersection in C# | WyrmTale articles 
http://www.wyrmtale.com/blog/2013/115/2d-line-intersection-in-c