Polygons and rectangles intersection

Detecting polygon intersections is a common task in game development and interactive computer graphics. In this post, I describe a polygon intersection algorithm, including how to determine whether a point lies inside a polygon. The examples are implemented using the popular game development engine Löve2D.

Polysec library

Polysec is a framework-agnostic Lua library for detecting intersections and collisions between polygons, circles and rectangles. It provides an efficient algorithm for polygonal intersection detection, making it suitable for the collision handling. While Polysec is independent of any specific framework, it is framework-agnostic.

Features

• Detect point belongs to polygon or rectangle.
• Detect collision of rectangles.
• Detect collision of polygons.
• Measure distance between two points.

Download the source code from GitHub.

Weiler-Athethon algorithm shortly

Under the hood Polysec uses the Weiler-Athethon algorithm to detect polygon intersections.

Algorithm Preconditions

Before applying the algorithm to a polygon, the following conditions must be met:

• Polygons must be oriented in a clockwise direction.
• Polygons must not be self-intersected (i.e., they should not be re-entrant).

Algorithm Steps

Given polygon A (clipping region) and polygon B (subject region) to be clipped, the algorithm proceeds as follows:

1. List the vertices of both polygon A and polygon B.
2. Classify each vertex of polygon B as either inside or outside of polygon A.
3. Identify all intersection points between the polygons and insert them into both vertex lists, ensuring they are at the intersection points.
4. Determine “inbound” intersections, where the vector from an intersection to the next vertex of polygon B originates inside the clipping region A.
5. Traverse the lists, following each intersection in a clockwise direction until returning to the starting position.

Handling no intersection cases

If no intersections are found, one of the following must be true:

• Polygon A is entirely inside Polygon B.
• Polygon B is entirely inside Polygon A.
• Polygons A and B do not overlap.

Usage

local polysec = require("init")
local polygon = polysec.polygon
local point = polysec.point

local square = polygon.new(
    point.new(100, 150),
    point.new(200, 150),
    point.new(200, 250),
    point.new(100, 250)
)
local triangle = polygon.new(
    point.new(125, 125),
    point.new(62.5, 225),
    point.new(25, 125)
)

-- If polygons are not overlapping, nil and false are returned. Otherwise
-- returns clipping polygon and true.
local clip, overlaps = polygon.overlaps(square, triangle)

print("Is overlapping: " .. tostring(overlaps))
if clip ~= nil then
    for i, p in ipairs(clip) do
        print("Point " .. i .. ": {x = " .. p.x .. ", y = " .. p.y .. "}")
    end
end
-- Output:
--[[
Is overlapping: true
Point 1: {x = 109.375, y = 150.0}
Point 2: {x = 100.0, y = 165.0}
Point 3: {x = 100, y = 150}
--]]

Orthogonal usage

local polysec = require("init")
local orthogonal = polysec.orthogonal
local point = polysec.point

local rect = orthogonal.rectangle.new(0, 0, 100, 100)
orthogonal.contain(rect, point.new(50, 50)) --> true
orthogonal.overlap(rect, orthogonal.rectangle.new(50, 50, 75, 75)) --> true

Running demos

Demos are written in Löve2D Framework. To run demos Löve2D should be installed on your machine.

Use relative paths for demos; this keeps the import path correct.

love ./demos/point-inside
love ./demos/polygons-intersection
love ./demos/rectangles-intersection

Tests

Unit-tests are performed using Laura testing framework. Linting is performed using luacheck.

Unit tests

laura .

Lint (code quality)

luacheck src test

Run everything with make software

make lint test

API

Types

• Point [number, number]
• Rectangle number[]
• Polygon number[]
• Circle number[]
• Shape Rectangle | Polygon | Circle | {kind: Kind}

Modules

point

• new(x: number, y: number): Point
  Creates a new point instance with x and y coordinates.
• distanceTo(p: Point, q: Point): number
  Computes the distance between two points.
• areEqual(p: Point, q: Point): number
  Checks that two points have same coordinates.

rectangle

• new(x1: number, y1: number, x2; number, y2: number): Rectangle
  
• new(p: Point, q: Point): Rectangle
  Creates a new rectangle instance.
• toList(rect: Rectangle): number
  Converts the rectangle to the array of numbers.

polygon

• new(...points: Point[]): Polygon
  Creates a new polygon instance.
• add(...points: Point[]): nil
  Adds point(s) to the polygon.
• toList(): number[]
  Converts polygon to the form of array [x1, y1, x2, y2, y3, y3, …, xN, yN].

circle

• new(x: number, y: number, r: number): Circle
  
• new(p: Point, r: number): Circle
  Creates a new circle instance.
• toList(circle: Circle): number
  Converts the circle to the array of numbers.

contian

• contain(s: Shape, p: Point): boolean
  Checks is the point inside a shape. For polygon using the winding number method.

overlap

• overlap(s: Shape, t: Shape): boolean, Shape?
  Checks overlapping of two shapes.

helpers

• closeTo(a: number, b: number): boolean
  Helper function for float equality comparison.
• isCircle(s: Shape): boolean
  Checks that shape is a circle.
• isPolygon(s: Shape): boolean
  Checks that shape is a polygon.
• isRectangle(s: Shape): boolean
  Checks that shape is a rectangle.

orthogonal

• rectangle: Rectamgle
  Same as rectangle
• overlap(s: Rectangle t: Rectangle): boolean
  Checks overlapping of two orthogonal rectangles.
• contain(r: Rectangle, p: Point): boolean
  Checks that point is inside orthogonal rectangle.

enum Constant

• Epslion: number
  A very small number, value is 1e-9.

enum Kind

• Rectangle = 0
• Polygon = 1
• Circle = 2

References

• Löve2D
• Weiler-Athethon algorithm

Feedback

For feedback, please check the contacts section. Before writing, please specify where you came from and who you are. Sometimes spammers go insane. Thank you in advance for your understanding.