Download the PHP package ifsnop/martinez-rueda-php without Composer

Martinez Rueda PHP

Robust and tested library for boolean operations on polygons (union, intersection, difference, xor) in PHP.

Some improvements over other libraries: This one is tested (see end-to-end directory) and optimized to use polygons with large amount of vertex (ie, binary search when doing intersections between segments).

This library can use arrays with polygons, geojson strings or geojson files directly.

Índice

1. Arquitectura general
2. Clases principales
3. Flujo de procesamiento
4. API pública
5. Ejemplos de uso
6. Optimizaciones implementadas
7. Mejoras sugeridas
8. Profilig
9. Testing A. Tutorials and Notes

Arquitectura general

La librería implementa un pipeline de tres fases para las operaciones booleanas:

Clases principales

Algorithm (final)

Clase estática central. Contiene toda la lógica de alto nivel y las operaciones públicas.

Polygon (final)

Representa un polígono como una lista de regiones (anillos), donde cada región es un array de objetos Point.

PolySegments (final)

Contenedor intermedio entre fases. Almacena segmentos, flag isInverted y el bounding box precalculado (bounds).

Segment (final)

Un segmento orientado entre dos Point. Contiene:

• myFill: relleno respecto al polígono propio (Fill->above, Fill->below).
• otherFill: relleno respecto al otro polígono (solo en fase combinada).
• minX/maxX/minY/maxY/len2: bounding box y longitud² cacheados para rechazo temprano en intersecciones.

Point (final)

Coordenada 2D con métodos estáticos de geometría:

Fill (final)

Par de booleanos (above, below) que indica si el espacio a cada lado de un segmento está dentro del polígono.

EventList / StatusList (final)

Estructuras de datos basadas en Skip List (trait SkipListCore). EventList mantiene la cola de eventos de barrido ordenada; StatusList mantiene el estado activo de segmentos durante el barrido.

GJTools (final)

Utilidades para importar y normalizar GeoJSON:

Flujo de procesamiento

Operación binaria típica

Barrido de línea (Intersecter)

El núcleo del algoritmo es un barrido de línea (sweep line) de izquierda a derecha:

1. Se crean eventos START y END para cada extremo de segmento.
2. Los eventos se procesan en orden lexicográfico (x, luego y) desde EventList.
3. Al procesar un START: se buscan vecinos en StatusList y se calculan intersecciones con el segmento de arriba y de abajo. Si hay intersección, se divide el segmento afectado.
4. Al procesar un END: se eliminan de StatusList y se emite el segmento con su Fill calculado.

Ensamblado de anillos (segmentChainer)

Usa un índice hash head → id y tail → id para encadenar segmentos en O(1) por inserción. Incluye simplificación colineal en los puntos de empalme para eliminar vértices redundantes.

API pública

Operaciones binarias

Operaciones n-arias

API de bajo nivel (para pipelines manuales)

Importación GeoJSON

Construcción manual de polígonos

Ejemplos de uso

Ejemplo 1: Unión de dos rectángulos

Ejemplo 2: Diferencia (recorte)

Ejemplo 3: Unión de múltiples polígonos

Ejemplo 4: Desde GeoJSON

Ejemplo 5: Pipeline manual (máximo control)

Optimizaciones implementadas

1. Skip List para EventList y StatusList

En lugar de listas enlazadas simples (O(n) por búsqueda), se usa una Skip List con altura aleatoria hasta 32 niveles. Esto reduce búsquedas e inserciones a O(log n) amortizado, crítico en el barrido de línea donde estas operaciones son el cuello de botella.

2. Índices hash para segmentChainer

El ensamblado de anillos usa tablas hash ($headIndex, $tailIndex) indexadas por clave de punto cuantizada. El coste de buscar si un punto ya existe en alguna cadena es O(1) en lugar de O(n).

3. Bounding box cacheada en Segment

Cada Segment precalcula y almacena minX, maxX, minY, maxY y len2 al crearse (y al recalcularse tras división). El rechazo temprano por AABB en checkIntersection evita calcular la intersección algebraica entre la gran mayoría de pares de segmentos no solapantes.

4. Bounds de PolySegments y cortocircuito geométrico

PolySegments almacena el bounding box del conjunto de segmentos. Las operaciones unionSegments, intersectSegments, xorSegments y differenceSegments comprueban primero si los bounds se solapan:

• Union/XOR sin solape: concatena segmentos directamente sin intersección.
• Intersection sin solape: devuelve vacío inmediatamente.
• Difference sin solape: devuelve el operando izquierdo directamente.

5. Reducción balanceada para unionMany

reduceBalanced combina los polígonos en un árbol binario en lugar de linealmente, reduciendo el número de operaciones de O(n) a O(log n) niveles de combinación, con mejor comportamiento de memoria.

6. Ordenación por posición antes de la reducción

Antes de la reducción, los segmentos se ordenan por la coordenada X mínima de su bounding box. Esto tiende a emparejar polígonos espacialmente cercanos primero, maximizando los cortocircuitos geométricos del punto 4.

7. Simplificación colineal en el ensamblado

Al encadenar segmentos, appendChainIdx y el caso de extensión en segmentChainer eliminan vértices intermedios cuando tres puntos consecutivos son colineales. Esto reduce el número de vértices del resultado sin pérdida de precisión.

8. Cuantización de puntos para las claves hash

pointKey() cuantiza las coordenadas multiplicando por 1/TOLERANCE y redondeando. Así, dos puntos dentro de la tolerancia producen la misma clave, evitando cadenas huérfanas por errores de punto flotante.

9. Back-pointer snode en Node

Cada Node de evento guarda una referencia directa al SkipNode que lo contiene. El borrado de un evento es O(altura del nodo) sin necesidad de buscar, evitando cierres (closures) por nodo y reduciendo presión sobre el GC.

10. Splitting de anillos auto-tocados

splitSelfTouchingRegions detecta y divide anillos que se auto-intersectan en un punto (figura en "8"), garantizando que el polígono final solo contenga ciclos simples válidos.

Mejoras sugeridas

Las mejoras detalladas, con propuestas de implementación, se encuentran en el documento IMPROVEMENTS.md.

Resumen

Profiling

• check that xdebug module is available and loaded: php -m | grep xdebug
• launch php with xdebug enabled: php \ -dxdebug.mode=profile \ -dxdebug.start_with_request=yes \ -dxdebug.output_dir=xdebug-profiler/ \ tests.php

Testing

Some tests inside tests.php, extended coverage with PHPUnit:

• php tests.php
• ./vendor/bin/phpunit tests/
• ./vendor/phpstan/phpstan/phpstan --error-format=raw

Tutorials and notes

• Interactive tutorial Polygon Clipping (Part 1)
• Interactive tutorial Polygon Clipping (Part 2)
• Notes on the Martinez-Rueda Polygon Clipping algorithm
• Let's build! Boolean operations of polygonsPart 1 - IntroductionPart 2 - Intersections

Resources

• To understand the algorithm, you can go here
• Based somewhat on the F. Martinez (2008) algorithm:
  • Website
  • A new algorithm for computing Boolean operations on polygons 2009 Research GateScience Direct
  • A simple algorithm for Boolean operations on polygons 2013

History

• This library is a port for PHP of pypolybool
• Previoulsy, was a port for JS of polybooljs
• Help from a .NET port