How to Fill Orthogonal Polygons with Grid Points in CAD and Geometry

Problem:

There is a closed polygon perimeter. All vertexes are in a right angle (orthogonal) .
How to create a grid inside the polygon if it has 8 vertexes?

Solution:

A simple orthogonal polygon—a polygon where:

• All interior angles are either 90° or 270° (i.e., right angles or reflex right angles).
• It’s closed and has 8 vertices.
• You want to fill it with a uniform grid of points, for example for sprinkler layout, meshing, or tiling.

This problem sits at the intersection of computational geometry, grid rasterization, and polygon point-inclusion tests.

---

✅ Problem Setup

You are given:

• A list of 8 ordered vertices: [(x1, y1), (x2, y2), ..., (x8, y8)]
• All angles are orthogonal (90° or 270°), so the edges are axis-aligned (only horizontal or vertical).
• The polygon may be non-convex (like an L-shape or staircase).

Your goal:

• Place points at regular intervals (spacing s) inside the polygon.

---

✅ Step-by-Step Mathematical Approach

1. Bounding Box

Find the smallest rectangle that contains the polygon:

minX = min(x_i)
maxX = max(x_i)
minY = min(y_i)
maxY = max(y_i)

2. Grid Scanning

Scan all grid points in the bounding box:

For x in range(minX, maxX, spacing):
    For y in range(minY, maxY, spacing):
        If point (x, y) is inside the polygon:
            Add it to the grid

3. Point-in-Polygon Test

Use a ray casting or winding number algorithm:

Ray casting (for any polygon):

For a point (px, py), cast a ray to the right and count how many edges it crosses:

• If odd, point is inside
• If even, point is outside

For orthogonal polygons, this is faster because edges are axis-aligned.

Optimized scanline algorithm:

For each row y (a horizontal scanline), find x-intersections with polygon edges.

• Sort intersection points in pairs.
• Fill grid points between x1 and x2, x3 and x4, etc.

---

📘 Recommended Books

Here are books that discuss these methods:

1. Computational Geometry: Algorithms and Applications

• Authors: Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars
• Topics Covered:
  • Polygon triangulation
  • Point-in-polygon tests
  • Scanline and plane sweep algorithms
  • Grid-based spatial partitioning
• Use: Chapters on polygon algorithms and rasterization are very relevant.

2. Geometry and Topology for Mesh Generation

• Author: Herbert Edelsbrunner
• Focus: Tiling, grid generation, domain filling
• Useful if you’re working toward mesh/grid generation inside polygons.

3. Graphics Gems series

• Especially Graphics Gems I & II
• Has optimized point-in-polygon algorithms for axis-aligned shapes.

---

✅ Optional: Python Example of Grid Filling (Mathematical Illustration)

from shapely.geometry import Point, Polygon

# Define orthogonal polygon
corners = [(0,0), (6,0), (6,2), (4,2), (4,4), (2,4), (2,2), (0,2)]
poly = Polygon(corners)

spacing = 1
points_inside = []

minx, miny, maxx, maxy = poly.bounds

x = minx
while x <= maxx:
    y = miny
    while y <= maxy:
        pt = Point(x, y)
        if poly.contains(pt):
            points_inside.append((x, y))
        y += spacing
    x += spacing

---

✅ Summary of the Math:

Step	Concept	Math
Bounding box	min/max(x/y)	Simple min/max
Grid	x, y stepped by spacing	Loop from min to max
Inclusion test	Ray casting / scanline	Even-odd rule, integer crossings
Grid fill	Rasterization	Place points at (x,y)