0

I am trying to display map with Voronoi styled map tiles.

It is on 2d array, I set some steps to achieve it:

  1. Divide 2d array map into equal sized squares (tile).
int map_width = 100, map_height = 100,
tile_size = 10;
vector<vector<int>> tile_map; // size 10x10
  1. Uniformly distribute site(or central) points in tiles
vector<pair<int,int>> sites
for (int y = 0; y < tile_map.size(); y++)
 for (int x = 0; x < tile_map[y].size(); x++)
sites.push_back({x*tile_size+(rand()%tile_size(),y*tile_size+(rand()%tile_size()});

  1. Link site points to other sites in adjacent tiles.
  2. Draw perpendicular line of lines formed in step 3.
  3. Intersecting point of perpendicular lines is the vertex of voronoi styled polygon.

Here I am stuck with step 4 and 5.

Is there a way to find perpendicular line with 2 given points?

Or is there a better way to design voronoi diagram in c++?enter image description here

2
  • A little unrelated, but if you have a fixed size of your map that is known at compile-time, and it's not excessively large, then you could use std::array instead of std::vector, as std::array<std::array<int, 10>, 10> tile_map;. Otherwise, if the size is getting a bit large, or the size is not known until run-time, then initialize the vectors with their size in the definition: std::vector<std::vector<int>> tile_map(tile_size, std::vector<int>(tile_size)); Jul 9, 2022 at 7:28
  • You should use sites.emplace_back() to avoid making a copy. Jul 9, 2022 at 11:04

1 Answer 1

0

Given 2 points (x1, y1) and (x2, y2) gives you a dx = x2 - x1 and dy = y2 - y1 and a parametric equation for the line line(t) = (x1 + t * dx, y1 + t * dy).

Constructing a perpendicular line from that is easy. Find the midpoint and rotate the slope by 90°:

cx = (x1 + x2) / 2;
cy = (y1 + y2) / 2;
p(t) = (cx + t * dy, cy + t * dx)

Finding the intersection of 2 such lines is easy too:

p1(t1) = (cx1 + t1 * dy1, cy1 + t1 * dx1)
p2(t2) = (cx2 + t2 * dy2, cy2 + t2 * dx2)

The 2 lines intersect when p1(t1) = p2(t2). That gives you 2 equations and 2 unknowns:

cx1 + t1 * dy1 == cx2 + t2 * dy2
cy1 + t1 * dx1 == cy2 + t2 * dx2

Solve for either t1 or t2 and calculate p1(t1) or p2(t2) at that point.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.