Circular Dependency (Voronoi Halfedge)

403 views Asked by At

I know, "circular dependency is a bad design", but I think in this case it's warranted.

When building a voronoi diagram, the cells are divided into what are called "half edges", this allows you to traverse the diagram in handy ways.

Anyway, in order to instantiate a halfedge, I have to specify the mirror, or twin of the halfedge.

This is funky in any language, but in Kotlin it's even more annoying because I have to use a nullable var instead of a val, like I would prefer.

Right now I'm doing this funkiness, which I don't like;

val mirrorEdge: HalfEdge
    get() = halfEdge!!

private var halfEdge: HalfEdge? = null

fun setMirror(halfEdge: HalfEdge) {
    this.halfEdge = halfEdge
}

//elsewhere

newEdge.setMirror(newEdge2)
newEdge2.setMirror(newEdge)

A halfedge mirror can never be null, and should be immutable, but I don't see how to communicate that intention in my code.

1

There are 1 answers

0
mfulton26 On BEST ANSWER

Without seeing the full definition of HalfEdge this might not work but consider the following:

interface HalfEdge {
    val mirrorHalf: HalfEdge
}

class HalfEdges {
    private inner class First : HalfEdge {
        override val mirrorHalf: HalfEdge
            get() = second
    }

    private inner class Second : HalfEdge {
        override val mirrorHalf: HalfEdge
            get() = first
    }

    val first: HalfEdge = First()
    val second: HalfEdge = Second()

    operator fun component1() = first
    operator fun component2() = second
}

Usage:

val (newEdge, newEdge2) = HalfEdges()
check(newEdge == newEdge2.mirrorHalf)
check(newEdge.mirrorHalf == newEdge2)

You have to create both halves at the same time and although you may never keep a reference to it directly both half edges maintain a reference to their whole edge container so that they can access one another. The above implementation could easily be adapted to pass in data to the two half edges and/or associate data with the whole edge.

This same principle could also be implemented with a parent "Graph" or "Network" class with an internal, bi-directional map of which edges mirror one another.