README
¶
martinez-go
Martinez-Rueda polygon clipping algorithm for golang.
Follows https://github.com/w8r/martinez and https://github.com/21re/rust-geo-booleanop as reference.
Usage
package main
import (
"fmt"
"github.com/akayami/martinez-go"
)
func main() {
type Point = martinez_go.Point
subject := [][][]Point{{{
Point{0, 0},
Point{0, 10},
Point{10, 10},
Point{10, 0},
Point{0, 0},
}}}
clipping := [][][]Point{{{
Point{5, 5},
Point{5, 15},
Point{15, 15},
Point{15, 5},
Point{5, 5},
}}}
res := martinez_go.Compute(subject, clipping, martinez_go.Intersection)
fmt.Println(res)
}
go run ./main.go
[[[{5 5} {10 5} {10 10} {5 10} {5 5}]]]
Authors
Based on
- A Javascript implementation
- A new algorithm for computing Boolean operations on polygons (2008, 2013) by Francisco Martinez, Antonio Jesus Rueda, Francisco Ramon Feito (and its C++ code)
Documentation
¶
Index ¶
- Constants
- Variables
- func CompareBBoxes(subject, clipping [][][]Point, sbbox, cbbox [4]float64, operation int) [][][]Point
- func CompareEvents(e1, e2 *SweepEvent) int
- func CompareSegments(le1, le2 *SweepEvent) int
- func Compute(subject, clipping [][][]Point, operation int) [][][]Point
- func ComputeFields(event, prev *SweepEvent, operation int)
- func DetermineResultTransition(event *SweepEvent, operation int) int
- func DivideSegment(se *SweepEvent, p Point, queue TinyQueue)
- func Equals(p1, p2 Point) bool
- func InResult(event *SweepEvent, operation int) bool
- func NextPos(pos int, resultEvents []*SweepEvent, processed map[int]bool, origPos int) int
- func OrbPolygonToPolygon(polygon orb.Polygon) [][]Point
- func Orient2d(p0, p1, p2 Point) float64
- func PossibleIntersection(se1, se2 *SweepEvent, queue TinyQueue) int
- func SignedArea(p0, p1, p2 Point) int
- func SpecialCases(e1, e2 *SweepEvent, p1, p2 Point) int
- func TrivialOperation(subject, clipping [][][]Point, operation int) [][][]Point
- type Comparator
- type CompareSeg
- type Contour
- type Key
- type Node
- type NodePrinter
- type Point
- type RangeVisitor
- type SplayTree
- func (tree *SplayTree) Add(key Key, value Value) *Node
- func (tree *SplayTree) At(index int) *Node
- func (tree *SplayTree) Clear()
- func (tree *SplayTree) Contains(key Key) bool
- func (tree *SplayTree) Find(key Key) *Node
- func (tree *SplayTree) FindStatic(key Key) (*Node, bool)
- func (tree *SplayTree) ForEach(visitor Visitor)
- func (tree *SplayTree) Insert(node *Node) *Node
- func (tree *SplayTree) Keys() []Key
- func (tree *SplayTree) Max() (Key, bool)
- func (tree *SplayTree) MaxNode(t *Node) *Node
- func (tree *SplayTree) Min() (Key, bool)
- func (tree *SplayTree) MinNode(t *Node) *Node
- func (tree *SplayTree) Next(d *Node) *Node
- func (tree *SplayTree) Pop() (Key, Value, bool)
- func (tree *SplayTree) Prev(d *Node) *Node
- func (tree *SplayTree) Range(low, high Key, fn RangeVisitor)
- func (tree *SplayTree) Remove(key Key)
- func (tree *SplayTree) ToList() []*Node
- func (tree *SplayTree) Values() []Value
- type SweepEvent
- type SweepEventComparator
- type TinyQueue
- type TinyQueueAI
- type TinyQueueDefault
- type Value
- type Visitor
Constants ¶
const ( Intersection = iota Union Difference XOR )
Operation types
const ( Normal = iota SameTransition DifferentTransition NonContributing )
Edge types
Variables ¶
var EMPTY = [][][]Point{}
EMPTY slice to represent an empty result
Functions ¶
func CompareBBoxes ¶
func CompareBBoxes(subject, clipping [][][]Point, sbbox, cbbox [4]float64, operation int) [][][]Point
CompareBBoxes compares bounding boxes for trivial solutions.
func CompareEvents ¶
func CompareEvents(e1, e2 *SweepEvent) int
func CompareSegments ¶
func CompareSegments(le1, le2 *SweepEvent) int
CompareSegments compares two SweepEvent instances and returns an integer indicating their order.
func ComputeFields ¶
func ComputeFields(event, prev *SweepEvent, operation int)
ComputeFields computes various fields for a SweepEvent.
func DetermineResultTransition ¶
func DetermineResultTransition(event *SweepEvent, operation int) int
DetermineResultTransition determines the result transition for a SweepEvent.
func DivideSegment ¶
func DivideSegment(se *SweepEvent, p Point, queue TinyQueue)
DivideSegment divides a SweepEvent at a point and updates the queue.
func InResult ¶
func InResult(event *SweepEvent, operation int) bool
InResult determines if a SweepEvent is in the result of the Boolean operation.
func OrbPolygonToPolygon ¶
func PossibleIntersection ¶
func PossibleIntersection(se1, se2 *SweepEvent, queue TinyQueue) int
PossibleIntersection checks for a possible intersection between two sweep events.
func SignedArea ¶
SignedArea determines the orientation of the triangle formed by three points. It returns -1 for counterclockwise, 1 for clockwise, and 0 for collinear points.
func SpecialCases ¶
func SpecialCases(e1, e2 *SweepEvent, p1, p2 Point) int
func TrivialOperation ¶
TrivialOperation checks for trivial cases based on the operation type.
Types ¶
type CompareSeg ¶
type CompareSeg func(le1, le2 *SweepEvent) int
type Contour ¶
Contour represents a contour with a series of points, holes, and other properties.
func ConnectEdges ¶
func ConnectEdges(sortedEvents []*SweepEvent) []*Contour
ConnectEdges connects edges to form contours.
func InitializeContourFromContext ¶
func InitializeContourFromContext(event *SweepEvent, contours []*Contour, contourId int) *Contour
func NewContour ¶
NewContour creates and initializes a new Contour instance.
func (*Contour) IsExterior ¶
IsExterior checks if the contour is an exterior contour.
type Key ¶
type Key *SweepEvent // Assuming Key is of type int for simplicity; adjust as needed.
Key Define basic types for Key and Value
type Node ¶
type Node struct {
Key *SweepEvent
Value any
Left *Node
Right *Node
Next *Node
}
Node structure
func NewSplayTreeNode ¶
func NewSplayTreeNode(key *SweepEvent) *Node
type NodePrinter ¶
NodePrinter function type for printing nodes
type Point ¶
type Point struct {
X, Y float64
}
Point represents a 2D point with X and Y coordinates.
func OrbPointToPoint ¶
func SegmentIntersection ¶
type RangeVisitor ¶
type SplayTree ¶
type SplayTree struct {
Root *Node
Size int
Comparator Comparator
}
SplayTree structure
func NewSplayTree ¶
func NewSplayTree(comparator Comparator) *SplayTree
NewTree creates a new instance of SplayTree with a given comparator
func (*SplayTree) Add ¶
Add inserts a key and its associated data into the tree if the key does not already exist. It returns the new root of the tree after insertion.
func (*SplayTree) At ¶
At returns the node at the given index in an in-order traversal of the tree. If the index is out of bounds, it returns nil.
func (*SplayTree) Find ¶
Find searches for a node by key and splays the tree. If the node is found, it becomes the new root of the tree. If the node is not found, the last accessed node becomes the new root.
func (*SplayTree) FindStatic ¶
FindStatic searches for a node by key without splaying.
func (*SplayTree) ForEach ¶
ForEach traverses the tree in-order and applies the visitor function to each node.
func (*SplayTree) MaxNode ¶
MaxNode returns the node with the largest key starting from the given node.
func (*SplayTree) Min ¶
Min returns the smallest key in the tree or zero value if the tree is empty.
func (*SplayTree) MinNode ¶
MinNode returns the node with the smallest key starting from the given node.
func (*SplayTree) Range ¶
func (tree *SplayTree) Range(low, high Key, fn RangeVisitor)
Range performs an in-order traversal of the tree within a key range from low to high. If the visitor function returns true, the traversal stops.
func (*SplayTree) Remove ¶
Remove is a public method that removes a node with the given key from the tree, if it exists.
type SweepEvent ¶
type SweepEvent struct {
Point Point
Left bool
OtherEvent *SweepEvent
IsSubject bool
Type int
InOut bool
OtherInOut bool
PrevInResult *SweepEvent
ResultTransition int
OtherPos int
OutputContourId int
IsExteriorRing bool
ContourId int
}
func NewSweepEvent ¶
func NewSweepEvent(point Point, left bool, otherEvent *SweepEvent, isSubject bool, edgeType int) *SweepEvent
func OrderEvents ¶
func OrderEvents(sortedEvents []*SweepEvent) []*SweepEvent
func SubdivideSegments ¶
func SubdivideSegments(eventQueue TinyQueue, subject, clipping [][][]Point, sbbox, cbbox *[4]float64, operation int) []*SweepEvent
Subdivide processes the event queue for the sweep line algorithm.
func (*SweepEvent) Clone ¶
func (e *SweepEvent) Clone() *SweepEvent
func (*SweepEvent) InResult ¶
func (e *SweepEvent) InResult() bool
func (*SweepEvent) IsAbove ¶
func (e *SweepEvent) IsAbove(p Point) bool
func (*SweepEvent) IsBelow ¶
func (e *SweepEvent) IsBelow(p Point) bool
func (*SweepEvent) IsVertical ¶
func (e *SweepEvent) IsVertical() bool
type SweepEventComparator ¶
type SweepEventComparator func(e1, e2 *SweepEvent) int
type TinyQueue ¶
type TinyQueue interface {
Len() int
Push(*SweepEvent)
Pop() *SweepEvent
Peek() *SweepEvent
}
TinyQueueDefault represents a priority queue with an underlying slice.
type TinyQueueAI ¶
type TinyQueueAI struct {
// contains filtered or unexported fields
}
func NewTinyQueueDefault ¶
func NewTinyQueueDefault(data []*SweepEvent, compare func(a, b *SweepEvent) int) *TinyQueueAI
func (*TinyQueueAI) Len ¶
func (tq *TinyQueueAI) Len() int
func (*TinyQueueAI) Peek ¶
func (tq *TinyQueueAI) Peek() *SweepEvent
func (*TinyQueueAI) Pop ¶
func (tq *TinyQueueAI) Pop() *SweepEvent
func (*TinyQueueAI) Push ¶
func (tq *TinyQueueAI) Push(item *SweepEvent)
type TinyQueueDefault ¶
type TinyQueueDefault struct {
// contains filtered or unexported fields
}
TinyQueueDefault represents a priority queue with an underlying slice.
func NewTinyQueueDefault2 ¶
func NewTinyQueueDefault2(data []*SweepEvent, compare SweepEventComparator) *TinyQueueDefault
NewTinyQueueDefault creates a new instance of TinyQueueDefault It takes an optional slice of data and a compare function.
func (*TinyQueueDefault) Len ¶
func (tq *TinyQueueDefault) Len() int
func (*TinyQueueDefault) Peek ¶
func (tq *TinyQueueDefault) Peek() *SweepEvent
Peek returns the top item from the queue without removing it.
func (*TinyQueueDefault) Pop ¶
func (tq *TinyQueueDefault) Pop() *SweepEvent
Pop removes and returns the top item from the queue.
func (*TinyQueueDefault) Push ¶
func (tq *TinyQueueDefault) Push(item *SweepEvent)
Push adds an item to the queue.
Source Files
Directories