WPC-Aufgabe (Programmierwettbewerb)

Jester

Das erkennen sie vermutlich.

Wobei mir nicht klar ist, von welchem Ableitungsbegriff Du sprichst. Wenn ich die Linien senkrecht nach oben mache kannste den normalen Ableitungsbegriff nicht benutzen.

Ist ein Berührpunkt nicht sowieso auch ein Schnittpunkt?

edit: Wikipedia sagt: ja

Wikipedia schrieb:

Ein Schnittpunkt ist in der Mathematik ein gemeinsamer Punkt zweier Kurven. Haben beide Kurven in ihrem gemeinsamen Punkt die gleiche Tangentensteigung, so spricht man von Berührungspunkt.

Wikipedia schrieb:

Ein Schnittpunkt ist in der Mathematik ein gemeinsamer Punkt zweier Kurven. Haben beide Kurven in ihrem gemeinsamen Punkt die gleiche Tangentensteigung, so spricht man von Berührungspunkt.

klingt logisch

evilissimo

http://de.wikipedia.org/wiki/Diskussion:Schnittpunkt

Wikipedia Diskussion schrieb:

Er bezeichnet einen Punkt, in dem sich zwei oder mehrere gerade oder gebogene Linien überkreuzen.

Eine tangentiale Berührung wird im Allgemeinen nicht als Schnittpunkt bezeichnet.

Die scheinen sich da aber auch nicht so sicher zu sein, so wie es aussieht ^^

Jester

Aber
[(0,0), (2,2)]
[(1,1), (2,0)]
schneiden sich nach eurer Rechnung.

evilissimo

Jester schrieb:

Aber
[(0,0), (2,2)]
[(1,1), (2,0)]
schneiden sich nach eurer Rechnung.

Ich sag ja net das mein algo richtig ist. Ich hab nur das erwähnt was auf Wikipedia zu dem Thema noch gesagt wird.

Jester schrieb:

Wobei mir nicht klar ist, von welchem Ableitungsbegriff Du sprichst. Wenn ich die Linien senkrecht nach oben mache kannste den normalen Ableitungsbegriff nicht benutzen.

Die Funktion dieser Linie bildet auf eine 2dimensionale Ebene ab und nimmt Parameter t. Eine allgemeine Kurve halt, in diesem Fall zweidimensional, wovon man ohne Probleme den Vektor der partiellen Ableitungen bilden kann.

Ist ein Berührpunkt nicht sowieso auch ein Schnittpunkt?

edit: Wikipedia sagt: ja

Ich denke nicht, dass du das aus diesem Satz folgern kannst. Genausogut kann der Satz eine Gegenüberstellung von Schnitt- und Berührpunkt sein. Nimm dir mal ne Parabel x² und sieh dir die X-Achse an. Schneidet sie die Parabel? Ich würde sagen nein.

Jester schrieb:

Aber
[(0,0), (2,2)]
[(1,1), (2,0)]
schneiden sich nach eurer Rechnung.

Finde ich korrekt.

Jester

Optimizer schrieb:

Ich denke nicht, dass du das aus diesem Satz folgern kannst.

Da steht doch, was ein Schnittpunkt ist, nämlich ein gemeinsamer Punkt. Und ein Berührpunkt ist ein gemeinsamer Punkt der...

Ergo: Berührpunkt ist Schnittpunkt.

@Ableitung: Und ich kann Dir ohne Probleme zwei Parametrisierungen meiner Strecke mit unterschiedlichen Ableitungen angeben.
Was Du wahrscheinlich haben willst ist lineare Abhängigkeit des Gradienten... und nichtmal das ist hinreichend. Zusätzlich müßten wir noch Parametrisierungen ausschließen, deren Gradient 0 werden können. Aber sag, ist das nicht ein bißchen viel des Guten für so nen einachen Begriff?

Nach der einen Definition ist ein Berührpunkt ein Schnittpunkt, also geht das erste Beispiel schief. Nach der Definition aus der Diskussion ist ein Schnittpunkt ein Punkt in dem sich die Strecken kreuzen. Das tun sie im zweiten Beispiel aber nicht.

Ich kann doch nicht jedesmal Optimizer fragen, ob er das jetzt gerade als Schnittpunkt empfindet oder nicht.

evilissimo

Testest du es trotzdem noch ( aber dann nur mit kreuzenden Linien )?

BR

evilissimo

Jester

Ja, ich nehme die Endpunkte paarweise verschieden. Dann kann die Situation nicht auftreten. Ich hab mich die letzten Tage viel mit der Boardsuche auseinandergesetzt und bin daher nicht mit der Auswertung weitergekommen. Mal sehen, vielleicht setze ich mich nachher nochmal dran.

Jester

So, jetzt bin auch dazu gekommen, die zweite Aufgabe auszuwerten.

Eine Lösung muß leider ausgeschlossen werden.
Das Programm von Ness arbeitet fehlerhaft, bei diesem Beispiel wird kein Schnittpunkt erkannt:

Strecke1: (-21.8, -2.1) - (10.5956, -10.7854)
Strecke2: (-44.4, -35.5) - (21.6849, 18.6791)

Wer möchte kann sich mit folgendem Code die Situation in GNU Octave visualisieren. Es handelt sich auch nicht um einen Randfall oder sowas, wo man von numerischen Instabilitäten ausgehen könnte.

m1 = (-10.7854 - -2.1)/(10.5956 - -21.8)
m2 = (18.6791 - -35.5)/(21.6849 - -44.4)
c1 = -2.1 - m1*-21.8
c2 = -35.5 - m2*-44.4
t1 = linspace(-21.8, 10.5956,2)
t2 = linspace(-44.4, 21.6849,2)
y1 = c1+t1*m1
y2 = c2+t2*m2

plot(t1,y1)
hold on
plot(t2,y2)

Für den Geschwindigkeitstest habe ich folgenden Liniengenerator benutzt:

#include <set>
#include <cstdlib>
#include <cmath>
#include "wpc_pro.h"

class LineGenerator
{
public:
	std::vector<Line> getLines(size_t numLines)
	{
		alreadyUsedPoints.clear();
		std::vector<Line> lines;
		for(size_t i = 0; i < numLines; ++i)
		{
			lines.push_back(generateNewLine());
		}
		return lines;
	}
private:

	Line generateNewLine() {
		Point start = generateNewPoint();
		Point end = getNewEndPoint(start);
		return Line(start, end);
	}

	Point generateNewPoint()
	{
		Point p(0,0);
		do
		{
			p.x = getRandomValue();
			p.y = getRandomValue();
		} while(alreadyUsedPoints.find(p)!=alreadyUsedPoints.end());
		alreadyUsedPoints.insert(p);
		return p;
	}

	Point getNewEndPoint(const Point & p)
	{
		Point result(0,0);

		do
		{

			double angle = getRandomValue();

			double dx = sin(angle);
			double dy = cos(angle);

			double length = double(rand())/RAND_MAX;
			length = pow(length, 10);
			length *= 100;
			if(length < 0.2) length = 0.2;

			result.x = p.x+length*dx;
			result.y = p.y+length*dy;

		} while(alreadyUsedPoints.find(result)!=alreadyUsedPoints.end());
		alreadyUsedPoints.insert(result);

		return result;
	}

	double getRandomValue() {
		double value = std::rand();
		value /= RAND_MAX;
		value *= 1000;
		value -= 500;
		value = int(value);
		value /= 10;

		return value;

	}

	std::set<Point> alreadyUsedPoints;

};

Dieser lehnt doppelte Punkte ab. Das Prinzip ist folgendes: Es wird zunächst ein zufälliger Punkt gezogen. Anschließend ein Zufälliger Winkel und eine zufällige Länge. Die Strecke geht dann vom ersten Punkt in Richtung des Winkels soweit wie die Länge angibt. Die Länge ziehe ich als Zahl von 0 bis 1. Um kleine Längen stärker zu gewichten potenziere ich diese Länge danach mit Exponenten 10.

Die längste Strecke in den Testdaten hat zumeist eine Länge von 100, der Schnitt liegt bei etwa 10. Es gibt also deutlich mehr kurze Strecken als Lange.

Nach dem Geschwindigkeitstest ergibt sich folgendes Endergebnis:

1. Thomas001 time: 157.084s
2. Evilissimo time: 314.453s
3. Brutus time: 384.989s

Bei den Zeiten handelt es sich um die Gesamtzeit um folgendes Testprogramm zu absolvieren:

Der Code von Thomas001 geht bereits ab eine Eingabegröße von 100 in Führung und bleibt die gesamt Testlaufzeit über schneller als die anderen Einsendungen.

#include "wpc_pro.h"
#include <iostream>
#include <cstdlib>
#include <ctime>
#include "LineGenerator.h"
#include <utility>
#include <string>

using namespace std;

typedef unsigned long long u64;

u64 rdtsc() {
	__asm  { rdtsc }
}

namespace Thomas001
{
	size_t wpc_pro(std::vector<Line> const&);
}

namespace Ness
{
	size_t wpc_pro(std::vector<Line> const&);
}

namespace Evilissimo
{
	size_t wpc_pro(std::vector<Line> const&);
}

namespace Brutus
{
	size_t wpc_pro(std::vector<Line> const&);
}

typedef size_t (*wpc_pro_func)(std::vector<Line> const&);
std::vector<wpc_pro_func> functions;
std::vector<string> names;
std::vector<u64> times;

int main()
{

	double clockspeed = 2211e6;

	functions.push_back(Thomas001::wpc_pro);  names.push_back("Thomas001 "); times.push_back(0);
	//functions.push_back(Ness::wpc_pro);       names.push_back("Ness      "); times.push_back(0);
	functions.push_back(Evilissimo::wpc_pro); names.push_back("Evilissimo"); times.push_back(0);
	functions.push_back(Brutus::wpc_pro);     names.push_back("Brutus    "); times.push_back(0);

	srand(time(0));
	LineGenerator generator;

	size_t size = 100;
	while(size < 100000)
	{
		vector<Line> lines = generator.getLines(size);

		double length = 0.0;
		double minLength = lines[0].getLength();
		double maxLength = lines[0].getLength();

		for(vector<Line>::iterator it = lines.begin(); it != lines.end(); ++it)
		{
			double l = it->getLength();
			length += l;
			minLength = min(minLength, l);
			maxLength = max(maxLength, l);
		}

		cout << "\n\nSize: " << lines.size() << endl;
		cout << "minimal Length: " << minLength << endl;
		cout << "maximal Length: " << maxLength << endl;
		cout << "average Length: " << length/lines.size() << "\n" << endl;

		for(int i = 0; i< functions.size(); ++i)
		{
			u64 time = -rdtsc();
			size_t result = functions[i](lines);
			time += rdtsc();
			times[i] += time;
			cout << names[i] << " result: " << result << "\t time: " << time/clockspeed << "s" << endl;
		}

		size*=1.3;
	}

	cout << "Final result: " << endl;
	for(int i = 0; i< functions.size(); ++i)
	{
		cout << names[i] << "\t time: " << times[i]/clockspeed << "s" << endl;
	}

	cin.get();
	return 0;
}

Und hier noch der Siegercode:

#include "wpc_pro.h"
#include <vector>
#include <iostream>
#include <memory>
#include <algorithm>

namespace {
  bool intersect(const Line& l1,const Line& l2,Point& where)
  {
    const double C1=l1.getEnd().x-l1.getStart().x,
      C2=l2.getStart().x-l2.getEnd().x,
      C3=l2.getStart().x-l1.getStart().x,
      D1=l1.getEnd().y-l1.getStart().y,
      D2=l2.getStart().y-l2.getEnd().y,
      D3=l2.getStart().y-l1.getStart().y;

    const double det=C1*D2-C2*D1;
    if(det==0)
      return false;

    const double t1=(C3*D2-C2*D3)/det;
    const double t2=(C1*D3-C3*D1)/det;

    where=Point(C1*t1+l1.getStart().x,
		D1*t1+l1.getStart().y);

    return t1>=0 && t1<=1 && t2>=0 && t2<=1;
  }

  double distance(const Line& l,const Point p)
  {
    const double C1=l.getEnd().x-l.getStart().x,
      D1=l.getEnd().y-l.getStart().y;
    return ((p.x-l.getStart().x)*(-D1)+(p.y-l.getStart().y)*C1);
  }

  struct Node
  {
    Node* left;
    Node* right;
    const Line line;
    Node(const Line& l):left(0),right(0),line(l) { }
    size_t insert(const Line& l);
    size_t split_insert(const Line& l);
    size_t insert_right(const Line& l);
    size_t insert_left(const Line& l);
    ~Node() { delete left;delete right; }
  };

  size_t Node::split_insert(const Line& l)
  {
    Point where(0,0);
    size_t r=intersect(l,line,where);
    const double ds=distance(line,l.getStart()),de=distance(line,l.getEnd());
    if(ds>0)
      {
	r+=insert_right(Line(l.getStart(),where));
	if(de<0)
	  r+=insert_left(Line(where,l.getEnd()));
      }
    else if(ds<0)
      {
	r+=insert_left(Line(l.getStart(),where));
	if(de>0)
	  r+=insert_right(Line(where,l.getEnd()));
      }
    else if(de>0)
      r+=insert_right(Line(where,l.getEnd()));
    else if(de<0)
      r+=insert_left(Line(where,l.getEnd()));
    return r;
  }

  size_t Node::insert_right(const Line& l)
  {
    if(right)
      return right->insert(l);
    else
      {
	right=new Node(l);
	return 0;
      }
  }

  size_t Node::insert_left(const Line& l)
  {
    if(left)
      return left->insert(l);
    else
      {
	left=new Node(l);
	return 0;
      }
  }

  std::vector<Line> evil_lines;

  size_t Node::insert(const Line& l)
  {
    // use split_insert more often than neccessary to build the tree
    // to get all the intersections counted right
    const double ds=distance(line,l.getStart()),de=distance(line,l.getEnd());
    if(ds>0)
      if(de>0)
	return insert_right(l);
      else 
	return split_insert(l);
    else if(ds<0)
      if(de<0)
	return insert_left(l);
      else 
	return split_insert(l);
    else if(de!=0)
      return split_insert(l);
    else
      {
	evil_lines.push_back(l);
	return 0;
      }
  }
}

size_t wpc_pro(const std::vector<Line>& v)
{
  if(v.empty())
    return 0;

  evil_lines.clear();
  size_t r=0;
  std::auto_ptr<Node> tree(new Node(v.front()));
  for(std::vector<Line>::const_iterator i=v.begin()+1;i!=v.end();i++)
    r+=tree->insert(*i);

  // this is really slow, but will not happen ;)
  Point p(0,0);
  for(std::vector<Line>::iterator i=evil_lines.begin();i!=evil_lines.end();i++)
    for(std::vector<Line>::const_iterator j=v.begin();j!=v.end();j++)
      {
	// for good lines find() will always return end()
	// for evil lines find() will return end() if the line was
	// already checked, so it's safe to check intersection now, as
	// we won't get checked by this line ourself.
	if(std::find(i,evil_lines.end(),*j)==evil_lines.end())
	  r+=intersect(*i,*j,p);
      }
  return r;
}

Herzlichen Glückwunsch an den Sieger und alle anderen Teilnehmer!

zuguterletzt möchte ich mich nochmal für die lange Auswertungsdauer entschuldigen. Die Zeit war unangemessen lang, ich werde in Zukunft die Auswertung vor dem Stellen der Aufgabe besser vorbereiten. Ich hoffe, daß ihr trotzdem weiterhin Lust habt gelegentlich an einem WPC teilzunehmen.

MfG Jester

Herzlichen Glückwunsch evilissimo!!!!

Schade das nur so wenig mitgemacht haben. Und das obwohl Weihnachten war.

So,wie jeder der sich mein programm mal angesehen hat vielleicht gesehen hat baut das programm einen BSP tree.Also im Prinzip einen Binaerbaum,wo eine linie in einem Knoten gespeichert wird und rechter und linker unterbaum nur linien enthalten die rechts/links von der linie liegen.Daher hat man im besten fall logarithmische kosten zum durchsuchen nach schnittpunkten.
Also halten wir fest eine Strecke teilt die Ebene in 2 Halbebene und die Trennlinie ist die durch die Strecke verlaufende Gerade. Strecken die diese Gerade schneiden werden geteilt und es wird ggf. als Schnittpunkt gezaehlt (je nachdem ob es auf der Strecke liegt oder nur auf der verlaengerten Gerade.
Soweit so gut,ein fundamentales Problem sind allerdings Strecken die auf ein und der selben Gerade liegen. Hier kann man nicht sagen ob sie in den rechten oder linken unterbaum eingefuegt werden muessen. Fuegt man sie in nur einen Unterbaum ein, kann es passieren, dass eine andere Strecke auf der anderen Seite liegt und trotzdem genau bis zur trennenden Gerade verlaeuft (diese also beruehrt). Das waere dann aber ein Schnittpunkt mit der Strecke die nun genau im falschen Unterbaum eingefuegt wurde,er wuerde also nicht gezaehlt. Fuegt man die problematische Strecke in beide Unterbaeume ein, so wird eine andere Strecke an der Gerade geteilt und fuehrt zu 2 schnittpunkten,also wieder falsch.

Meine erste Loesung war es diese boesen Strecken gar nicht einzufuegen,sondern in einen array zu packen und dann extra zu pruefen. Das ist zwar langsam,aber sollte ein extrem seltener Sonderfall sein. So nun aber ein Gegenbeispiel wo dies nicht korrekt ist: Folgende einfuegereihenfolge:
1. eine Senkrechte Strecke sagen wir (0,-1)-(0,1)
2. eine waagerechte (1,0)-(2,0)
3. eine waagerechte (-2,0)-(-1,0)
4. eine waagerechte (-0.5,0)-(0.5,0)
so was passiert also? nach 1-3. hat man einen Baum mit 1. in der wurzel und 2.,3. als rechtes/linkes kind. Nun soll 4 eingefuegt werden. 4 schneidet 1. wird also geteilt,nun soll (-0.5,0)-(0,0) und (0,0)-(0.5,0) in 3 bzw 4 eingefuegt werden,die liegen beide auf der jeweils trennenden Gerade,also werden beide als boese Linien gespeichert und nicht eingefuegt. Nun wird zum schluss deren Schnitt geprueft, jede der boesen linien schneidet 1. also 2 extra schnittpunkte,also werden 3 gezaehlt obwohl nur einer da ist!

behoben kann das werden indem man z.b. durch eine exception signalisiert das eine boese linie aufgetreten ist,und dann alle linien und schnittpunkte die durch sie entstanden sind wieder entfernt werden oder so,dafuer hatte ich aber keine zeit mehr...

wann kommt denn die nächste aufgabe? ich möchte euch mal so richtig an die wand proggen.

Jester

Gibt's denn noch mehr Interessenten?

Ponto

Jester schrieb:

Gibt's denn noch mehr Interessenten?

Immer.

Brutus

Jop.

lohnt sich aber nur wenn volkard auch mitmacht.

Aufgabe: Programmiert Doom 4 und schickt die fertigen Programme an...

Soll ich das jetzt schreiben oder ist das zu schlecht.

PeterTheMaster

interesse ja, zeit weiss nicht.