Intersection of Convex Polygons Algorithm


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

javafx

Database Operations in JavaFX

By Onur Baskirt / Apr 1, 2016 / 56 Comments
Before started this section, please check the first article and learn How to Start JAVAFX! http://www.swtestacademy.com/getting-started-with-javafx/ At first, part of JavaFX tutorial series, we created a sample JavaFX project, designed the draft version of the UI and set up an...
extentreports

How to Write Smart XPath Locators

By Onur Baskirt / Sep 24, 2017 / 5 Comments
Hi all, in this tutorial, I will describe you how to write smart and non-brittle XPath locators. When we write our test scripts, we generally prefer to use id, name, class, etc. these kinds of locators. However, sometimes we could not...
extentreports

How to Write Effective CSS Locators

By Onur Baskirt / Oct 1, 2017 / 0 Comments
Hi all, in this tutorial, I will describe you how to write effective CSS locators to interrogate web elements for your automation projects. As a rule of thumb, your interrogation strategy should be in below order: First try to use...
rest assured

REST API Testing with Rest Assured

By Onur Baskirt / Mar 8, 2016 / 32 Comments
Outline In this post, I will explain what is API and API testing, what is the difference between SOAP and REST services, and how to test REST APIs with Rest Assured Library. What is API? API stands for Application Programming...
javafx

Getting Started with JavaFX

By Onur Baskirt / Mar 25, 2016 / 0 Comments
When I started to work in my current position, one of my task is to do manual operations for campaign products  every week. After the second week, I thought that I have to automate this task using a GUI based...
extentreports

Selenium-1: Quick Start to Automation with Selenium WebDriver & JAVA & JUnit & Maven & IntelliJ

By Onur Baskirt / Sep 8, 2015 / 26 Comments
Outline Selenium Webdriver is the most popular open source web test automation framework across the wide range of browsers and platforms. In this tutorial, you will learn how to do web test automation with Selenium Webdriver and the related tools....
extentreports

Selenium-11: Execute JavaScript with JavascriptExecutor

By Onur Baskirt / Jan 27, 2016 / 15 Comments
Outline Sometimes we cannot handle some conditions or problems with Webdriver, web controls don't react well against selenium commands. In this kind of situations, we use Javascript. It is useful for custom synchronizations, hide or show the web elements, change...
page object model

Page Object Model with C#

By Ege Aksoz / Jun 18, 2017 / 8 Comments
In the previous tutorial, we’ve taken the initial steps and entered the world of automated testing. We also wrote our first automated test. From this point on, since we are not just going to write one test, we need to...
extentreports

How to Select a Date From DatePicker Using Selenium

By Onur Baskirt / Aug 13, 2016 / 6 Comments
When you need to automate a airway, hotel, or similar websites you need to deal with Datepickers and some times it is a little bit cumbersome to select a specific date on the Datepicker or calendar.  In this post, I...

Getting Started with RobotFramework on Windows

By Onur Baskirt / Apr 25, 2016 / 12 Comments
What is RobotFramework? RobotFramework is a GENERIC test automation framework for acceptance testing and acceptance test-driven development (ATTD). What it means that you can do web, mobile, desktop and other test automation activities with related test libraries. These libraries can...
By | 2017-10-20T20:15:09+00:00 May 18th, 2017|Algorithms|0 Comments

About the Author:

Sinan Oz
Sinan Oz is an experienced IT professional who has a big passion on software science and algorithms since he attended International Olympiads in Informatics in his early ages. He finished Istanbul Technical University Computer Engineering Department. He worked at Garanti Technology, one of the biggest technology centres in the country for about 5 years. After that, he started Kariyer.net and takes some serious projects as a Lead Architect and he promoted as a Software Development Manager. Currently, he is working at Movie Star Planet Kopenhagen office as a Senior Backend Game Developer.

Leave A Comment