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 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}
--]]

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, number, number, number]
• Polygon Point[]

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.

rectangle

• new(x1: number, y1: number, x2; number, y2: number): Rectangle
  
• new(p: Point, q: Point): Rectangle
  Creates a new rectangle instance.
• contains(rect: Rectangle, point: Point): boolean
  Checks is the point inside a rectangle.
• overlaps(rect1: Rectangle, rect2: Rectangle): boolean
  Checks two axis-aligned rectangles for the collision.
• 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].
• contains(a: Polygon, p: Point): boolean
  Check if a point is inside a polygon a using the winding number method. Point is inside if the winding number is nonzero.
• intersects(p1: Point, p2: Point, q1: Point, q2: Point): Point|nil
  Compute the intersection of two line segments {p1, p2} and {q1, q2}. If segments are parallel or incongruent, it returns nil.
• overlaps(a: Polygon, b: Polygon): Polygon|nil, boolean
  Checks that two polygons are overlapping each other. If polygons do not overlap nil and false, they are returned; otherwise, clipped polygons and true are returned.

constant

• Epslion: number
  A very small number.

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.