lua - Manhattan Voronoi Diagram: Resolving Ties When Sites Are on the Same Diagonal - Stack Overflow

admin管理员组

文章数量:1123054

I'm implementing a Manhattan Voronoi diagram in Love2D, where regions are divided based on the Manhattan distance from a set of given sites. However, I'm encountering an issue when two or more sites are located on the same diagonal. In such cases, some grid cells are marked as 'tie' regions and displayed as black areas, which I want to avoid.

I understand that the problem occurs because the Manhattan distances to these sites are equal for certain points on the grid. Here's my current findClosestSite function:

function findClosestSite(x, y, sites)
    local minDistance = math.huge
    local closestSite = nil
    local isTie = false

    for _, site in ipairs(sites) do
        local distance = math.abs(x - site[1]) + math.abs(y - site[2])
        if distance < minDistance then
            minDistance = distance
            closestSite = site
            isTie = false
        elseif distance == minDistance then
            isTie = true
        end
    end

    return closestSite, isTie
end

In the case of a tie, I currently mark the cell as black. I'd like to resolve ties by prioritizing one of the sites.

How can I modify my function to handle ties in a robust way, or are there better approaches for resolving this issue in Manhattan Voronoi diagram?

本文标签： luaManhattan Voronoi Diagram Resolving Ties When Sites Are on the Same DiagonalStack Overflow