Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <set>
- #include <math.h>
- using namespace std;
- struct Point {
- double x;
- double y;
- Point() : x(0), y(0) {}
- Point(double _x, double _y) : x(_x), y(_y) {}
- };
- struct Arc;
- struct Segment;
- struct Event {
- double x;
- Point point;
- Arc *arc;
- bool valid;
- Event(double _x, Point _point, Arc *_arc)
- : x(_x), point(_point), arc(_arc), valid(true) {}
- };
- struct Arc {
- Point point;
- Arc *previous;
- Arc *next;
- Event *event;
- Segment *s0;
- Segment *s1;
- explicit Arc(Point _point, Arc *_prev = nullptr, Arc *_next = nullptr)
- : point(_point), previous(_prev), next(_next), event(nullptr), s0(nullptr), s1(nullptr) {}
- };
- vector<Segment*> output;
- struct Segment {
- Point start;
- Point end;
- bool done;
- explicit Segment(Point _start): start(_start), end(0,0), done(false) {
- output.push_back(this);
- }
- // Set the end point and mark as "done."
- void finish(Point _end) {
- if (done) {
- return;
- }
- end = _end;
- done = true;
- }
- };
- // "Greater than" comparison, for reverse sorting in priority queue.
- struct gt {
- bool operator () (Point left, Point right) {
- return left.x==right.x ? left.y>right.y : left.x>right.x;
- }
- bool operator()(Event *left, Event *right) {
- return left->x > right->x;
- }
- };
- Arc *root = nullptr;
- // Bounding box coordinates.
- double X0 = 0;
- double X1 = 0;
- double Y0 = 0;
- double Y1 = 0;
- priority_queue<Point, vector<Point>, gt> points; // site events
- priority_queue<Event*, vector<Event*>, gt> events; // circle events
- // Where do two parabolas intersect?
- Point intersection(Point first, Point second, double l)
- {
- Point res;
- Point tmp_point = first;
- double z0 = 2*(first.x - l);
- double z1 = 2*(second.x - l);
- if (first.x == second.x)
- res.y = (first.y + second.y) / 2;
- else if (second.x == l)
- res.y = second.y;
- else if (first.x == l) {
- res.y = first.y;
- tmp_point = second;
- } else {
- // Use the quadratic formula.
- double a = 1/z0 - 1/z1;
- double b = -2*(first.y/z0 - second.y/z1);
- double c = (first.y*first.y + first.x*first.x - l*l)/z0
- - (second.y*second.y + second.x*second.x - l*l)/z1;
- res.y = ( -b - sqrt(b*b - 4*a*c) ) / (2*a);
- }
- // Plug back into one of the parabola equations.
- res.x = (tmp_point.x*tmp_point.x + (tmp_point.y-res.y)*(tmp_point.y-res.y) - l*l)/(2*tmp_point.x-2*l);
- return res;
- }
- // Will a new parabola at point p intersect with arc i?
- bool intersect(Point point, Arc *arc, Point *result)
- {
- if (arc->point.x == point.x) return false;
- double a,b;
- if (arc->previous) // Get the intersection of arc->prev, arc.
- a = intersection(arc->previous->point, arc->point, point.x).y;
- if (arc->next) // Get the intersection of arc->next, arc.
- b = intersection(arc->point, arc->next->point, point.x).y;
- if ((!arc->previous || a <= point.y) && (!arc->next || point.y <= b)) {
- result->y = point.y;
- result->x = (arc->point.x*arc->point.x + (arc->point.y-result->y)*(arc->point.y-result->y) - point.x*point.x)
- / (2*arc->point.x - 2*point.x);
- return true;
- }
- return false;
- }
- // Find the rightmost point on the circle through a,b,c.
- bool circle(Point a, Point b, Point c, double *x, Point *o)
- {
- // Check that bc is a "right turn" from ab.
- if ((b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y) > 0)
- return false;
- // Algorithm from O'Rourke 2ed p. 189.
- double A = b.x - a.x, B = b.y - a.y,
- C = c.x - a.x, D = c.y - a.y,
- E = A*(a.x+b.x) + B*(a.y+b.y),
- F = C*(a.x+c.x) + D*(a.y+c.y),
- G = 2*(A*(c.y-b.y) - B*(c.x-b.x));
- if (G == 0) return false; // Points are co-linear.
- // Point o is the center of the circle.
- o->x = (D*E-B*F)/G;
- o->y = (A*F-C*E)/G;
- // o.x plus radius equals max x coordinate.
- *x = o->x + sqrt( pow(a.x - o->x, 2) + pow(a.y - o->y, 2) );
- return true;
- }
- // Look for a new circle event for arc i.
- void check_circle_event(Arc *i, double x0)
- {
- // Invalidate any old event.
- if (i->event && i->event->x != x0)
- i->event->valid = false;
- i->event = NULL;
- if (!i->previous || !i->next)
- return;
- double x;
- Point o;
- if (circle(i->previous->point, i->point, i->next->point, &x,&o) && x > x0) {
- // Create new event.
- i->event = new Event(x, o, i);
- events.push(i->event);
- }
- }
- void front_insert(Point tmp_point)
- {
- if (!root) {
- root = new Arc(tmp_point);
- return;
- }
- for (Arc *arc = root; arc; arc = arc->next) {
- Point z;
- Point zz;
- if (intersect(tmp_point,arc,&z)) {
- // New parabola intersects arc arc. If necessary, duplicate arc.
- if (arc->next && !intersect(tmp_point,arc->next, &zz)) {
- arc->next->previous = new Arc(arc->point,arc,arc->next);
- arc->next = arc->next->previous;
- }
- else arc->next = new Arc(arc->point,arc);
- arc->next->s1 = arc->s1;
- // Add tmp_point between arc and arc->next.
- arc->next->previous = new Arc(tmp_point,arc,arc->next);
- arc->next = arc->next->previous;
- arc = arc->next; // Now arc points to the new arc.
- // Add new half-edges connected to arc's endpoints.
- arc->previous->s1 = arc->s0 = new Segment(z);
- arc->next->s0 = arc->s1 = new Segment(z);
- // Check for new circle events around the new arc:
- check_circle_event(arc, tmp_point.x);
- check_circle_event(arc->previous, tmp_point.x);
- check_circle_event(arc->next, tmp_point.x);
- return;
- }
- }
- // Special case: If tmp_point never intersects an arc, append it to the list.
- Arc *i;
- for (i = root; i->next; i=i->next) ; // Find the last node.
- i->next = new Arc(tmp_point,i);
- // Insert segment between tmp_point and i
- Point start;
- start.x = X0;
- start.y = (i->next->point.y + i->point.y) / 2;
- i->s1 = i->next->s0 = new Segment(start);
- }
- void process_point() {
- Point tmp_point = points.top();
- points.pop();
- front_insert(tmp_point);
- }
- void process_event()
- {
- // Get the next event from the queue.
- Event *e = events.top();
- events.pop();
- if (e->valid) {
- // Start a new edge.
- Segment *s = new Segment(e->point);
- // Remove the associated arc from the front.
- Arc *a = e->arc;
- if (a->previous) {
- a->previous->next = a->next;
- a->previous->s1 = s;
- }
- if (a->next) {
- a->next->previous = a->previous;
- a->next->s0 = s;
- }
- // Finish the edges before and after a.
- if (a->s0) a->s0->finish(e->point);
- if (a->s1) a->s1->finish(e->point);
- // Recheck circle events on either side of p:
- if (a->previous) check_circle_event(a->previous, e->x);
- if (a->next) check_circle_event(a->next, e->x);
- }
- delete e;
- }
- void finish_edges()
- {
- // Advance the sweep line so no parabolas can cross the bounding box.
- double l = X1 + (X1-X0) + (Y1-Y0);
- // Extend each remaining segment to the new parabola intersections.
- for (Arc *i = root; i->next; i = i->next)
- if (i->s1)
- i->s1->finish(intersection(i->point, i->next->point, l*2));
- }
- void print_output()
- {
- // Bounding box coordinates.
- cout << X0 << " "<< X1 << " " << Y0 << " " << Y1 << endl;
- // Each output segment in four-column format.
- vector<Segment*>::iterator i;
- for (i = output.begin(); i != output.end(); i++) {
- Point p0 = (*i)->start;
- Point p1 = (*i)->end;
- cout << p0.x << " " << p0.y << " " << p1.x << " " << p1.y << endl;
- }
- }
- int main()
- {
- // Read points from input.
- Point p;
- while (cin >> p.x >> p.y) {
- if(p.x == -100) {
- break;
- }
- points.push(p);
- // Keep track of bounding box size.
- if (p.x < X0) X0 = p.x;
- if (p.y < Y0) Y0 = p.y;
- if (p.x > X1) X1 = p.x;
- if (p.y > Y1) Y1 = p.y;
- }
- // Add 20% margins to the bounding box.
- double dx = (X1-X0+1)/5.0; double dy = (Y1-Y0+1)/5.0;
- X0 -= dx; X1 += dx; Y0 -= dy; Y1 += dy;
- // Process the queues; select the top element with smaller x coordinate.
- while (!points.empty())
- if (!events.empty() && events.top()->x <= points.top().x)
- process_event();
- else
- process_point();
- // After all points are processed, do the remaining circle events.
- while (!events.empty())
- process_event();
- finish_edges(); // Clean up dangling edges.
- print_output(); // Output the voronoi diagram.
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement