62 lines
1.8 KiB
Go
62 lines
1.8 KiB
Go
package delaunay
|
||
|
||
import (
|
||
"lab.zaar.be/thefish/alchemyst-go/engine/types"
|
||
"lab.zaar.be/thefish/alchemyst-go/util/kruskals"
|
||
)
|
||
//FIXME ПЕРЕПИСАТЬ К ЕБЕНЯМ ДЕЛОНЕ. Это пиздец и си с крестами головного мозга. Надо сделать по-человечески.
|
||
|
||
func GetTriangles(coords []types.Coords, w, h int) []types.Edge {
|
||
d := &Delaunay{}
|
||
edges := d.Init(100, 100).Insert(coords).GetEdges()
|
||
output := make([]types.Edge, 0)
|
||
for _, e := range edges{
|
||
output = append(output, types.Edge{From: e.Nodes[0].Coords, To: e.Nodes[1].Coords})
|
||
}
|
||
return output
|
||
}
|
||
|
||
func GetMst(coords []types.Coords, w, h, negativeWeight int) []types.Edge {
|
||
|
||
d := &Delaunay{}
|
||
|
||
edges := d.Init(w, h).Insert(coords).GetEdges()
|
||
|
||
//MST
|
||
//fixme гребаный костыль
|
||
nodeMap := make(map[int]int, 0)
|
||
idx := 0
|
||
nodeList := make(map[int]Node)
|
||
for _, e := range edges{
|
||
if _, ok := nodeMap[e.Nodes[0].Id]; !ok{
|
||
nodeMap[e.Nodes[0].Id] = idx
|
||
nodeList[idx] = e.Nodes[0]
|
||
idx++
|
||
}
|
||
if _, ok := nodeMap[e.Nodes[1].Id]; !ok{
|
||
nodeMap[e.Nodes[1].Id] = idx
|
||
nodeList[idx] = e.Nodes[1]
|
||
idx++
|
||
}
|
||
}
|
||
//graph := make([]kruskals.WeightedEdge, len(edges))
|
||
graph := make([]kruskals.WeightedEdge, 0)
|
||
for _, e := range edges{
|
||
//graph[i] = kruskals.SimpleWeightedEdge{e.Nodes[0].Id, e.Nodes[1].Id, int(e.Nodes[0].Coords.DistanceTo(e.Nodes[1].Coords))}
|
||
graph = append(
|
||
graph,
|
||
kruskals.SimpleWeightedEdge{
|
||
F: nodeMap[e.Nodes[0].Id],
|
||
T: nodeMap[e.Nodes[1].Id],
|
||
W: negativeWeight - int(e.Nodes[0].Coords.DistanceTo(e.Nodes[1].Coords))},
|
||
)
|
||
}
|
||
|
||
result := kruskals.MinimumSpanningTree(graph)
|
||
output := make([]types.Edge, 0)
|
||
for _, we := range result{
|
||
output = append(output, types.Edge{From: nodeList[we.From()].Coords, To: nodeList[we.To()].Coords})
|
||
}
|
||
return output
|
||
}
|