<commit_before>package spatial

import (
	"container/list"
	"log"
)

// Polygon is a data type for storing simple polygons: One outer ring and an arbitrary number of inner rings.
type Polygon []Line

func (p Polygon) ClipToBBox(nw, se Point) []Geom {
	// Is outer ring fully inside?
	oNW, oSE := p[0].BBox()
	if oNW.X() >= nw.X() && oNW.Y() >= nw.Y() && oSE.X() <= se.X() && oSE.Y() <= se.Y() {
		geom, _ := NewGeom(p)
		return []Geom{geom}
	}

	// TODO: inner ring handling
	clipLn := NewLinesFromSegments(BBoxBorders(nw, se))[0]

	// clockwise ordering first
	// subjLns := orderableLine{ln: p[0]}
	// sort.Sort(subjLns)

	var (
		subjLL = list.New()
		clipLL = list.New()
	)

	// convert subj and clip slices into linked lists
	for _, subjPt := range p[0] {
		log.Printf("subj: %v", subjPt)
		subjLL.PushBack(refPoint{pt: subjPt})
	}
	for _, clipPt := range clipLn {
		clipLL.PushBack(clipPt)
	}

	// build intersections
	for subjPt := subjLL.Front(); subjPt != nil; subjPt = subjPt.Next() {
		subjSeg := Segment{subjPt.Value.(refPoint).pt, nextElemOrWrap(subjLL, subjPt).Value.(refPoint).pt}
		for clipPt := clipLL.Front(); clipPt != nil; clipPt = clipPt.Next() {
			clipSeg := Segment{clipPt.Value.(Point), nextElemOrWrap(clipLL, clipPt).Value.(Point)}
			if intsct, isIntsct := subjSeg.Intersection(clipSeg); isIntsct {
				log.Printf("intersection: %v (%v %v)", intsct, subjSeg, clipSeg)
				clipRef := clipLL.InsertAfter(intsct, clipPt)
				clipPt = clipPt.Next()

				log.Println(nil, subjPt, intsct, clipRef)
				if existingElem := hasPointElement(subjLL, refPoint{pt: intsct}); existingElem == nil {
					log.Println(existingElem, subjPt, intsct, clipRef)
					subjLL.InsertAfter(refPoint{
						pt:      intsct,
						clipRef: clipRef,
					}, subjPt)
				} else {
					log.Println("hipp")
					existingElem.Value = refPoint{
						pt:      intsct,
						clipRef: clipRef,
					}
				}

				if subjPt.Next() != nil {
					subjPt = subjPt.Next()
				}
			}
		}
	}

	for subjPt := subjLL.Front(); subjPt != nil; subjPt = subjPt.Next() {
		log.Printf("subj pt: %v", subjPt)
	}

	var (
		lines       []Line
		startIntsct *list.Element
	)
	for subjPt := subjLL.Front(); ; subjPt = nextElemOrWrap(subjLL, subjPt) {
		log.Printf("Processing %v", subjPt.Value.(refPoint))
		if subjPt == nil || (startIntsct != nil && subjPt == startIntsct) {
			break
		}
		// entering intersection
		if !subjPt.Value.(refPoint).pt.InPolygon(Polygon{clipLn}) && nextElemOrWrap(subjLL, subjPt).Value.(refPoint).pt.InPolygon(Polygon{clipLn}) {
			if startIntsct == nil {
				startIntsct = subjPt
			}

			log.Printf("entering")
			var (
				nln Line

				startingPt = nextElemOrWrap(subjLL, subjPt).Value.(refPoint)
			)
			log.Printf("stop at: %v", startingPt)
			nln = append(nln, startingPt.pt)

			// walk the subject line until there is a leaving intersection
			for subjPt = nextElemOrWrap(subjLL, subjPt); ; subjPt = nextElemOrWrap(subjLL, subjPt) {
				log.Printf("walking subject: %v", subjPt)
				// don't duplicate points
				if len(nln) == 0 || nln[len(nln)-1] != subjPt.Value.(refPoint).pt {
					log.Printf("app.")
					nln = append(nln, subjPt.Value.(refPoint).pt)
				}

				if len(nln) > 1 && !nextElemOrWrap(subjLL, subjPt).Value.(refPoint).pt.InPolygon(Polygon{clipLn}) {
					log.Printf("breche, next pt: %v", nextElemOrWrap(subjLL, subjPt).Value.(refPoint).pt.InPolygon(Polygon{clipLn}))
					break
				}
				// if subjPt.Next() == nil {
				// 	// prevent applying Next()
				// 	break
				// }
			}
			log.Printf("ref: %v", subjPt)
			log.Printf("stop clip iter at: %v", startingPt)
			// walk the clip line until starting intersection is reached
			for clipPt := subjPt.Value.(refPoint).clipRef; ; clipPt = nextElemOrWrap(clipLL, clipPt) {
				log.Printf("%v %p", clipPt, clipPt)
				if clipPt == startingPt.clipRef {
					log.Println("ref reached")
					break
				}
				log.Printf("clip ref %p", clipPt)

				// don't duplicate points
				if len(nln) == 0 || nln[len(nln)-1] != clipPt.Value.(Point) {
					nln = append(nln, clipPt.Value.(Point))
				}
			}
			if len(nln) != 0 {
				log.Printf("appending: %v", nln)
				lines = append(lines, nln)
			}
		}
	}

	var geoms []Geom
	for _, ln := range lines {
		ng, _ := NewGeom(Polygon{ln})
		geoms = append(geoms, ng)
	}
	return geoms
}

func PolygonsFromLines(ls []Line) []Polygon {
	var mlines []Line
	for lni := range ls {
		var merged bool<commit_msg>lib/spatial: polygon, clipping documentation, removed logs<commit_after>package spatial

import "container/list"

// Polygon is a data type for storing simple polygons: One outer ring and an arbitrary number of inner rings.
type Polygon []Line

func (p Polygon) ClipToBBox(nw, se Point) []Geom {
	// Is outer ring fully inside?
	oNW, oSE := p[0].BBox()
	if oNW.X() >= nw.X() && oNW.Y() >= nw.Y() && oSE.X() <= se.X() && oSE.Y() <= se.Y() {
		geom, _ := NewGeom(p)
		return []Geom{geom}
	}

	// This clipping method uses Weiler-Atherton Polygon Clipping
	// It is implemented with in a two-pass manner.
	// Step 1: All edges (subject and clipping) are traversed and intersections are added.
	// Step 2: Starting with an incoming intersection, all edges of the subject polygon are
	//         iterated and until the clipping region is exited, those edges are collected.
	//         After this the clipping polygon is traversed until the original entering
	//         intersection is reached.
	//         This is repeated until the starting intersection is reached.

	// TODO: inner ring handling
	clipLn := NewLinesFromSegments(BBoxBorders(nw, se))[0]

	var (
		subjLL = list.New()
		clipLL = list.New()
	)

	// convert subj and clip slices into linked lists
	for _, subjPt := range p[0] {
		subjLL.PushBack(refPoint{pt: subjPt})
	}
	for _, clipPt := range clipLn {
		clipLL.PushBack(clipPt)
	}

	// build intersections
	for subjPt := subjLL.Front(); subjPt != nil; subjPt = subjPt.Next() {
		subjSeg := Segment{subjPt.Value.(refPoint).pt, nextElemOrWrap(subjLL, subjPt).Value.(refPoint).pt}
		for clipPt := clipLL.Front(); clipPt != nil; clipPt = clipPt.Next() {
			clipSeg := Segment{clipPt.Value.(Point), nextElemOrWrap(clipLL, clipPt).Value.(Point)}
			if intsct, isIntsct := subjSeg.Intersection(clipSeg); isIntsct {
				clipRef := clipLL.InsertAfter(intsct, clipPt)
				clipPt = clipPt.Next()

				if existingElem := hasPointElement(subjLL, refPoint{pt: intsct}); existingElem == nil {
					subjLL.InsertAfter(refPoint{
						pt:      intsct,
						clipRef: clipRef,
					}, subjPt)
				} else {
					existingElem.Value = refPoint{
						pt:      intsct,
						clipRef: clipRef,
					}
				}

				if subjPt.Next() != nil {
					subjPt = subjPt.Next()
				}
			}
		}
	}

	var (
		lines       []Line
		startIntsct *list.Element
	)
	for subjPt := subjLL.Front(); ; subjPt = nextElemOrWrap(subjLL, subjPt) {
		if subjPt == nil || (startIntsct != nil && subjPt == startIntsct) {
			break
		}
		// entering intersection
		if !subjPt.Value.(refPoint).pt.InPolygon(Polygon{clipLn}) && nextElemOrWrap(subjLL, subjPt).Value.(refPoint).pt.InPolygon(Polygon{clipLn}) {
			if startIntsct == nil {
				startIntsct = subjPt
			}

			var (
				nln        Line
				startingPt = nextElemOrWrap(subjLL, subjPt).Value.(refPoint)
			)
			nln = append(nln, startingPt.pt)

			// walk the subject line until there is a leaving intersection
			for subjPt = nextElemOrWrap(subjLL, subjPt); ; subjPt = nextElemOrWrap(subjLL, subjPt) {
				// don't duplicate points
				if len(nln) == 0 || nln[len(nln)-1] != subjPt.Value.(refPoint).pt {
					nln = append(nln, subjPt.Value.(refPoint).pt)
				}

				if len(nln) > 1 && !nextElemOrWrap(subjLL, subjPt).Value.(refPoint).pt.InPolygon(Polygon{clipLn}) {
					break
				}
			}
			// walk the clip line until starting intersection is reached
			for clipPt := subjPt.Value.(refPoint).clipRef; ; clipPt = nextElemOrWrap(clipLL, clipPt) {
				if clipPt == startingPt.clipRef {
					break
				}

				// don't duplicate points
				if len(nln) == 0 || nln[len(nln)-1] != clipPt.Value.(Point) {
					nln = append(nln, clipPt.Value.(Point))
				}
			}
			if len(nln) != 0 {
				lines = append(lines, nln)
			}
		}
	}

	var geoms []Geom
	for _, ln := range lines {
		ng, _ := NewGeom(Polygon{ln})
		geoms = append(geoms, ng)
	}
	return geoms
}

func PolygonsFromLines(ls []Line) []Polygon {
	var mlines []Line
	for lni := range ls {
		var merged bool
{'fraction_non_alphanumeric': 0.14722388059701494, 'fraction_numerical': 0.002507462686567164, 'mean_word_length': 3.1547619047619047, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6850023', 'n_tokens_mistral': 3582, 'n_tokens_neox': 3113, 'n_words': 729}