main.go

package main

import (
	"fmt"
)

type point struct {
	x, y uint32
}

func (p point) String() string {
	return fmt.Sprintf("%dx%d", p.x, p.y)
}

type rectangle struct {
	min, max point
}

func (r rectangle) String() string {
	return fmt.Sprintf("rectangle{%v %v}", r.min, r.max)
}

func (r rectangle) Center() point {
	return point{
		x: r.min.x + r.Width()/2,
		y: r.min.y + r.Height()/2,
	}
}


func (r rectangle) Width() uint32 {
	return r.max.x - r.min.x
}

func (r rectangle) Height() uint32 {
	return r.max.y - r.min.y
}

type partition struct {
	rectangle
	points   []point
	children []*partition
}

func (p partition) Empty() bool {
	return len(p.points) == 0
}


func (p *partition) SplitV(width uint32) int {
	edge := p.min.x + width

	p.children = nil

	var left, right partition

	for _, pt := range p.points {
		if pt.x > edge {
			right.points = append(right.points, pt)
		} else {
			left.points = append(left.points, pt)
		}
	}

	if len(left.points) > 0 {
		left.rectangle = rectangle{
			min: p.min,
			max: point{
				x: p.max.x - edge,
				y: p.max.y,
			},
		}
		p.children = append(p.children, &left)
	}

	if len(right.points) > 0 {
		right.rectangle = rectangle{
			min: point{
				x: p.min.x + edge,
				y: p.min.y,
			},
			max: p.max,
		}

		p.children = append(p.children, &left)
	}

	return len(p.children)
}

func (p *partition) String() string {
	return fmt.Sprintf("partition{%v %v %v}(%d)", p.min, p.Center(), p.max, len(p.points))
}

func main() {
	p := &partition{
		rectangle: rectangle{
			min: point{0, 0},
			max: point{100, 100},
		},
		points: []point{{10, 10}, {90, 90}},
	}
	
	fmt.Println(p)
	
	p.SplitV(p.Width()/2)

	fmt.Println(p.children)
}