WireRouting/lib/include/Astar.h

#pragma once

#ifdef _WIN32
#ifdef WIREROUTINGDLL_EXPORTS			// VisualStudio DLL 项目模板会将 <PROJECTNAME>_EXPORTS 添加到定义预处理器宏。
#define ASTAR_API __declspec(dllexport) // _WIN32
#else
#define ASTAR_API __declspec(dllimport)
#endif
#else
#define ASTAR_API
#endif

#include "BranchTree.h"

#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <iostream>
#include <fstream>
#include <sstream>
#include <cassert>

using namespace std;

struct ASTAR_API DSU
{
	int f[N];
	void init(int cnt);
	int getrt(int x);
	void merge(int x, int y);
};

struct ASTAR_API Node
{
	int xs, turncnt;
	double dis;
	bool operator<(Node B) const;
	Node();
	Node(int xs1, int turnc, double dis1);
};

// 用于搜索路径的数据结构，每种类型的线束会分配到一个
struct ASTAR_API Astar
{
	ClipSet *pclipSet;					// 指向卡箍集合
	BranchTree *pbranchTree;			// 指向分支树
	P points[MAXPointNum];				// 点的信息，包括卡箍点，分支点和端点
	P start, goal, start_dir, goal_dir; // 起点终点以及方向
	int S, T;							// 起点和终点的标号
	map<int, vector<int>> edge;
	// 存储每个点附近不碰撞的其他点，避免重复调用kdtree和bvh
	map<P, pair<int, int>> nearClip; // 因为端点处不能分叉，所以标记端点连接到的最近卡箍

	int searchNum;							 // 搜索次数，用于调试
	int pre[MAXPointNum], vis[MAXPointNum];	 // pre存储一个点的上一个点，vis存储一个点是否被访问过
	int st[MAXPointNum], block[MAXPointNum]; // st是临时栈，block标记的点不能被通过
	int pnum;								 // 卡箍点总数
	int tnum;								 // 所有点总数
	Path path;								 // 路径结果
	double bend_r, l;						 // 弯曲半径，总长度
	Node dis[MAXPointNum];					 // 存储距离信息
	priority_queue<Node> pq;				 // 优先队列
	double preBranchPointPos[MAXPointNum];	 // 若前一个点是1类型（同进异出）分支点，存储其最优位置

	Astar();

	void addBranchTree(BranchTree *pbranchTree);

	// 初始化
	void init();

	// 添加一个卡箍点
	void add_clip(P &p, P &d);

	void add_clip(Clip &cp);

	// 添加一个分支点
	void add_branchPoint(BranchPoint &bp);

	/*
	inline double cost(P &p1,P &p2){
		if(bvh.iscollect(p1,p2))return 1e9;
		//return distan(p1,p2);
		return angelAndLength(p1,p2);
	}
	*/

	Path search_pair(P &start, P &goal, P &start_dir, P &goal_dir, double dia);

	Path search_pair(P &start, P &goal, double dia);

	Path search_pair(Bund &bd);

	void searchForPreProcess();

	void search();
};

extern ASTAR_API Astar astar;