geometric.md

Geometric algorithms

Table of contents

• Polygons
  • Inscribed circle
• Closest pair of points
• Points generation
  • Random points generation
    • Random points in triangles
    • Random points in polygons
• Polyline algorithms
  • Ramer–Douglas–Peucker algorithm
• Drawing algorithms
  • Bresenham’s-type algorithms
    • Bresenham’s line algorithm
    • Bresenham’s circle algorithm

---

Polygons

Inscribed circle

🔗

• Confusion on Delaunay triangulation and largest inscribed circle – Stack Overflow
• Largest circle inside a non-convex polygon – Stack Overflow

---

Closest pair of points

Problem: in the given set of n ≥ 2 points in a metric space, find a pair of points with the smallest distance between them.

🔗

• Closest pair of points – Wikipedia

🎥

• E.Izzy. Divide and conquer algorithms – PWL NYC (2019)

📖

• Sec. 33.4: Finding the closest pair of points – T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein. Introduction to algorithms (2009)

---

Points generation

Random points generation

📖

• Sec. 1.5: G.Turk. Generating random points in triangles – A.S.Glassner. Graphics gems (1990)

Random points in triangles

Problem: given three points A, B and C that describe a triangle, pick a random point in it with uniform probability.

❔

• Uniform random point in triangle – Mathematics

Random points in polygons

Problem: given N points A1, A2, ..., AN that describe a polygon, pick a random point in it with uniform probability.

❔

• How to get a random point on the interior of an irregular polygon? – Stack Overflow

---

Polyline algorithms

Ramer–Douglas–Peucker algorithm

🔗

• Ramer–Douglas–Peucker algorithm – Wikipedia

---

Drawing algorithms

Bresenham’s-type algorithms

Bresenham’s line algorithm

🔗

• Bresenham’s line algorithm – Wikipedia

📄

• R.F.Sproull. Using program transformations to derive line-drawing algorithms – ACM Transactions on Graphics 1, 259 (1982)

Bresenham’s circle algorithm

🔗

• Midpoint circle algorithm – Wikipedia
• J.Kennedy. A fast Bresenham type algorithm for drawing circles