Graham Scan Funktionsaufruf

[bekinect]

Hallo

Ich versuche einen Graham Scan für einen Vektor mit Koordinaten von Punkten in einer ebene zu programmieren.
Ich hab auch schon einen Code gefunden, den ich auf mein Programm abgewandelt habe. Der Originalcode https://www.eecis.udel.edu/~breech/pract/graham-scan.cc ist hier zu finden.
Ich hab den Code jetzt soweit abgewandelt, dass er in meinem Programm zu verwenden ist. Mein Problem ist, dass die sortierten Punkte anscheinend nicht übergeben werden. Ich rufe die Funktion GrahamScan auf, aber der Vektor, in dem die Punkte übergeben werden bleibt leer.
Ich hab einmal ein Beispielprogramm vorbereitet:

#include <iostream>
#include <stdlib.h>
#include <vector>
#include <array>
#include <fstream>
#include <string>
#include <math.h>
#include <algorithm>
#include <memory.h>
#include <stdio.h>
#include <assert.h>
#include <set>
#include <float.h>

#define CCW_LEFT_TURN 1
#define CCW_RIGHT_TURN -1
#define CCW_COLINEAR 0

using namespace std;

std::vector<std::array<double, 3>> chull;

double squareDistancePoints(const std::array<double, 3>& a, const std::array<double, 3>& b)
{
    assert(a.size() == b.size());
    double sum = 0;
    for(size_t i = 0; i < a.size(); ++i)
        sum += pow(b[i]-a[i], 2);
    return sum;
}

double Distance(const std::array<double, 3>& s1, const std::array<double, 3>& s2)
{
    assert(s1.size() == s2.size());
	double distance = 0;
	distance = sqrt(pow(s2[0]-s1[0], 2)+pow(s2[1]-s1[1],2));
	return distance;
}

int ccw(const std::array<double, 3>& s1, const std::array<double, 3>& s2, const std::array<double, 3>& origin)
{
	std::array<double, 3> v1, v2;
	int cp_z;

	v1[0] = (s1[0] - origin[0]); 
	v1[1] = (s1[1] - origin[1]);
	v2[0] = (s2[0] - origin[0]);
	v2[1] = (s2[1] - origin[1]);

	cp_z = v1[0] * v2[1] - v1[1] * v2[0];
	if(cp_z > 0)
		return CCW_LEFT_TURN;
	else if(cp_z < 0)
		return CCW_RIGHT_TURN;

	return CCW_COLINEAR;
}

bool compare_angle(const std::array<double, 3>& s1, const std::array<double, 3>& s2)
{
	int res;
	std::array<double, 3> p0;
	p0[0]=0;
	p0[1]=0;

	res = ccw(s1, s2, p0);

	if(res == CCW_LEFT_TURN)
		return true;
	else if(res == CCW_COLINEAR) {
		double da, db;
		da = Distance(p0, s1);
		db = Distance(p0, s2);
		if(da < db)
			return true;
	}

	return false;
}

void set_p0(std::vector<std::array<double, 3>> matrix)
{
	size_t i;
	for(i=1; i<matrix.size(); i++)
	{
		if(matrix[i][1] < matrix[0][1])
		{
			swap(matrix[0], matrix[1]);
		}
		else if(matrix[i][1] == matrix[0][1] && matrix[i][0] < matrix[0][0])
		{
			swap(matrix[0], matrix[i]);
		}
	}
}

void GrahamScan(std::vector<std::array<double, 3>> matrix, std::vector<std::array<double, 3>> chull)
{
    size_t i;
	bool done;
	std::array<double, 3> next2last, last;

	set_p0(matrix);

	sort(matrix.begin()+1, matrix.end(), compare_angle);

	chull.push_back(matrix[0]);
	chull.push_back(matrix[1]);

	for(i=2; i<matrix.size(); i++)
	{
		done = false;

		while(!done && chull.size() > 1) {
			last = chull.back();
			next2last = chull[chull.size()-2];

			if(ccw(last, matrix[i], next2last) != CCW_LEFT_TURN)
				chull.pop_back();
			else
				done = true;
		}

		chull.push_back(matrix[i]);
	}

	for(size_t i=0; i<chull.size(); i++)
	{
		cout << "Hull;" << ";" << chull[i][0] << ";" << chull[i][1] << ";" <<  endl;
	}

}

int main()
{
    std::vector<std::array<double, 3>> matrix;
    //std::vector<std::array<double, 3>> chull;

    double x_values[] = {0, 1, 2, 4, 0, 1, 3, 3};
    double y_values[] = {3, 1, 2, 4, 0, 2, 1, 3};

    int xsize=sizeof( x_values ) / sizeof( double );
    int ysize=sizeof( y_values ) / sizeof( double );

    if(xsize != ysize)
    {
        cout << "Error: Size Values must be same";
        return 0;
    }

    matrix.resize(xsize);

    for(int i = 0; i<xsize; i++)
    {
        matrix[i][0]=x_values[i];
        matrix[i][1]=y_values[i];
    }

    if(matrix.size()>2)
	{
		GrahamScan (matrix, chull);
	}

	for(size_t i=0; i<chull.size(); i++)
	{
	    cout << "Convexe Hull" << ";" << chull[i][0] << ";" << chull[i][1] << ";" <<  endl;
	}

   return 0;
}

Wenn ich in der main Funktin den Inhalt ausgeben lassen will ist der Vektor chull leer. Gebe ich den Vektor in der Funktion GrahamScan aus erhalte ich aber eine Ausgabe. Keine Ahnung was ich da falsch mache, da das in meiner Vorlage genau so gemacht wurde. Hat jemand einen Tipp für mich.

Gruß
Bernhard

[manni66]

An allen Stellen, an denen du keine Änderung erwartest, benutzt du Referenzen. Warum tust du das nicht auch an den anderen?

[bekinect]

Danke für den Hinweis. Keine Ahnung wieso ich das übersehen habe.