static void
test_homo_move_ctor ()
{
    rw_info (0, __FILE__, __LINE__,
             "move constructor (homogenous tuples)");

    std::tuple<> et (std::tuple<> ()); _RWSTD_UNUSED (et);

    const int ci = std::rand ();

    std::tuple<int> it1 (ci);
    std::tuple<int> it2 (std::move (it1));
    test (__LINE__, it2, ci);

    std::tuple<const int> ct1 (ci);
    std::tuple<const int> ct2 = std::move (ct1);
    test (__LINE__, ct2, ci);

    std::tuple<std::tuple<int> > nt1 (it1);
    std::tuple<std::tuple<int> > nt2 = std::move (nt1);
    test (__LINE__, nt2, it1);

    std::tuple<long, const char*> pt1 (1234567890L, "string");
    std::tuple<long, const char*> pt2 (std::move (pt1));
    test (__LINE__, pt2, 1234567890L, (const char*) "string");

    const UserDefined ud (ci);
    std::tuple<UserDefined> ut1 (ud);
    UserDefined::reset ();
    std::tuple<UserDefined> ut2 (std::move (ut1));
    ++UserDefined::expect.move_ctor;
    test (__LINE__, ut2, ud);

    std::tuple<bool, char, int, double, void*, UserDefined>
        bt1 (true, 'a', ci, 3.14159, (void*) &ci, ud);
    ++UserDefined::expect.copy_ctor;
    std::tuple<bool, char, int, double, void*, UserDefined>
        bt2 (std::move (bt1));
    ++UserDefined::expect.move_ctor;
    test (__LINE__, bt2, true, 'a', ci, 3.14159, (void*) &ci, ud);
}

	void mark(cv::Mat& img, PPoint2d &p, unsigned char l) {
		int r = 10;
  //draw_circle(img, p, r, l);
  //	draw_circle(img, p[0], p[1], 10, l);
  //	draw_line(img, p[0]-r/2, p[1]-r/2, p[0]+r/2, p[1]+r/2, l);
  //	draw_line(img, p[0]-r/2, p[1]+r/2, p[0]+r/2, p[1]-r/2, l);
		double x = p.x();
		double y = p.y();
		cv::Point2d pt(x,y);
		cv::Point2d pt1(x - r / 2, y - r / 2);
		cv::Point2d pt2(x + r / 2, y + r / 2);
		cv::Point2d pt3(x - r / 2, y + r / 2);
		cv::Point2d pt4(x + r / 2, y - r / 2);

		cout << p << endl;
		if (x >= 0 && y >= 0 && x <= img.rows && y <= img.cols) {
			cv::circle(img, pt, 10, l);
			cv::line(img, pt1, pt2, l);
			cv::line(img, pt3, pt4, l);
		}
	}

void displayopencv::DisplayBspline(const mathtools::application::Bspline<2> &bspline, cv::Mat &img, const mathtools::affine::Frame<2>::Ptr frame, const cv::Scalar &color, const unsigned int &nb_pts)
{
	double inf = bspline.getInfBound(),
		   sup = bspline.getSupBound();
	
	Eigen::Vector2d prev = mathtools::affine::Point<2>(bspline(inf)).getCoords(frame);

	for(unsigned int i=1;i<nb_pts;i++)
	{
		double t = inf + (double)i*(sup-inf)/(double)(nb_pts-1);

		Eigen::Vector2d curr = mathtools::affine::Point<2>(bspline(t)).getCoords(frame);

		cv::Point pt1(prev.x(), prev.y()),
				  pt2(curr.x(), curr.y());
		
		prev=curr;

		cv::line(img,pt1,pt2,color);
	}
}

void check_are_mergable()
{
  Polycurve_conic_traits_2 traits;
  Polycurve_conic_traits_2::Construct_x_monotone_curve_2
    construct_x_monotone_curve_2 = traits.construct_x_monotone_curve_2_object();
  Polycurve_conic_traits_2::Are_mergeable_2  are_mergeable_2 =
    traits.are_mergeable_2_object();

   //create a curve
  Rat_point_2 ps1(1, 10);
  Rat_point_2 pmid1(5, 4);
  Rat_point_2 pt1(10, 1);
  Conic_curve_2 c1(ps1, pmid1, pt1);

  Rat_point_2 ps2(10, 1);
  Rat_point_2 pmid2(15, 14);
  Rat_point_2 pt2(20, 20);
  Conic_curve_2 c2(ps2, pmid2, pt2);

  Rat_point_2 ps3(Rational(1,4), 4);
  Rat_point_2 pmid3(Rational(3,2), 2);
  Rat_point_2 pt3(2, Rational(1,3));
  Conic_curve_2 c3(ps3, pmid3, pt3);

  //construct x-monotone curve(compatible with polyline class)
   Polycurve_conic_traits_2::X_monotone_curve_2 polyline_xmc1 =
     construct_x_monotone_curve_2(c1);
   Polycurve_conic_traits_2::X_monotone_curve_2 polyline_xmc2 =
     construct_x_monotone_curve_2(c2);
   Polycurve_conic_traits_2::X_monotone_curve_2 polyline_xmc3 =
     construct_x_monotone_curve_2(c3);

  bool result = are_mergeable_2(polyline_xmc1, polyline_xmc2);
  std::cout << "Are_mergable:: Mergable x-monotone polycurves are Computed as: "
            << ((result)? "Mergable" : "Not-Mergable") << std::endl;

  result = are_mergeable_2(polyline_xmc1, polyline_xmc3);
  std::cout << "Are_mergable:: Non-Mergable x-monotone polycurves are Computed as: "
            << ((result)? "Mergable" : "Not-Mergable") << std::endl;
}

void FixtureGroup_Test::swap()
{
    FixtureGroup grp(m_doc);
    grp.setSize(QSize(4, 4));
    for (quint32 id = 0; id < 16; id++)
    {
        Fixture* fxi = new Fixture(m_doc);
        fxi->setChannels(1);
        m_doc->addFixture(fxi);
        grp.assignFixture(fxi->id());
    }
    QCOMPARE(grp.headList().size(), 16);

    QLCPoint pt1(0, 0);
    QLCPoint pt2(2, 1);
    QVERIFY(grp.headHash().contains(pt1) == true);
    QVERIFY(grp.headHash().contains(pt2) == true);
    QCOMPARE(grp.headHash()[pt1], GroupHead(0, 0));
    QCOMPARE(grp.headHash()[pt2], GroupHead(6, 0));

    // Switch places with two fixtures
    grp.swap(pt1, pt2);
    QVERIFY(grp.headHash().contains(pt1) == true);
    QVERIFY(grp.headHash().contains(pt2) == true);
    QCOMPARE(grp.headHash()[pt1], GroupHead(6, 0));
    QCOMPARE(grp.headHash()[pt2], GroupHead(0, 0));

    // Switch places with a fixture and an empty point
    pt2 = QLCPoint(500, 500);
    grp.swap(pt1, pt2);
    QVERIFY(grp.headHash().contains(pt1) == false);
    QVERIFY(grp.headHash().contains(pt2) == true);
    QCOMPARE(grp.headHash()[pt2], GroupHead(6, 0));

    // ...and back again
    grp.swap(pt1, pt2);
    QVERIFY(grp.headHash().contains(pt1) == true);
    QVERIFY(grp.headHash().contains(pt2) == false);
    QCOMPARE(grp.headHash()[pt1], GroupHead(6, 0));
}

void test_wait_for_either_of_four_futures_4()
{
    boost::packaged_task<int> pt(make_int_slowly);
    boost::unique_future<int> f1(pt.get_future());
    boost::packaged_task<int> pt2(make_int_slowly);
    boost::unique_future<int> f2(pt2.get_future());
    boost::packaged_task<int> pt3(make_int_slowly);
    boost::unique_future<int> f3(pt3.get_future());
    boost::packaged_task<int> pt4(make_int_slowly);
    boost::unique_future<int> f4(pt4.get_future());
    
    boost::thread(::cast_to_rval(pt4));
    
    unsigned const future=boost::wait_for_any(f1,f2,f3,f4);
    
    BOOST_CHECK(future==3);
    BOOST_CHECK(!f1.is_ready());
    BOOST_CHECK(!f2.is_ready());
    BOOST_CHECK(!f3.is_ready());
    BOOST_CHECK(f4.is_ready());
    BOOST_CHECK(f4.get()==42);
}

bool CCoordTransService::CoordTransDistanceEx (
	const DoublePair *pP1, const DoublePair *pP2, double &dX, double &dY)
{
	if (m_fIsInitialized) {
		try {
		CCSPoint pt1 (pP1 -> Width(), pP1 -> Height());
		CCSPoint pt2 (pP2 -> Width(), pP2 -> Height());
		W_DGMPoint outPt;

			THROW_FAILED_HRESULT(m_CTF -> DistancePoint(&pt1, &pt2, outPt.ppi()));
			THROW_FAILED_HRESULT(outPt -> get_X (&dX));
			THROW_FAILED_HRESULT(outPt -> get_Y (&dY));
			return true;

		} catch (_com_error &e) {
			ShowError (_COM_ERROR(e), IDS_CSSERRORCAPTION, g_cbCoordTransDistanceEx);
			return false;
		}
	}
	ShowError (TRIAS02_E_CSSNOTINITIALIZED, IDS_CSSERRORCAPTION, g_cbCoordTransDistanceEx);
	return false;
}

// forward the message to the appropriate item
bool wxListBox::MSWOnDraw(WXDRAWITEMSTRUCT *item)
{
    // only owner-drawn control should receive this message
    wxCHECK( ((m_windowStyle & wxLB_OWNERDRAW) == wxLB_OWNERDRAW), false );

    DRAWITEMSTRUCT *pStruct = (DRAWITEMSTRUCT *)item;

    // the item may be -1 for an empty listbox
    if ( pStruct->itemID == (UINT)-1 )
        return false;

    wxListBoxItem *pItem = (wxListBoxItem *)m_aItems[pStruct->itemID];

    wxDCTemp dc((WXHDC)pStruct->hDC);
    wxPoint pt1(pStruct->rcItem.left, pStruct->rcItem.top);
    wxPoint pt2(pStruct->rcItem.right, pStruct->rcItem.bottom);
    wxRect rect(pt1, pt2);

    return pItem->OnDrawItem(dc, rect,
                             (wxOwnerDrawn::wxODAction)pStruct->itemAction,
                             (wxOwnerDrawn::wxODStatus)pStruct->itemState);
}

void DrawResult(IplImage* image, windage::Matrix3 homography, CvScalar color = CV_RGB(255, 0, 0), int thickness = 1)
{
	windage::Vector3 pt1(0.0, 0.0, 1.0);
	windage::Vector3 pt2(TEMPLATE_WIDTH, 0.0, 1.0);
	windage::Vector3 pt3(TEMPLATE_WIDTH, TEMPLATE_HEIGHT, 1.0);
	windage::Vector3 pt4(0.0, TEMPLATE_HEIGHT, 1.0);

	windage::Vector3 outPoint1 = homography * pt1;
	windage::Vector3 outPoint2 = homography * pt2;
	windage::Vector3 outPoint3 = homography * pt3;
	windage::Vector3 outPoint4 = homography * pt4;

	outPoint1 /= outPoint1.z;
	outPoint2 /= outPoint2.z;
	outPoint3 /= outPoint3.z;
	outPoint4 /= outPoint4.z;

	cvLine(image, cvPoint((int)outPoint1.x, (int)outPoint1.y), cvPoint((int)outPoint2.x, (int)outPoint2.y), color, thickness);
	cvLine(image, cvPoint((int)outPoint2.x, (int)outPoint2.y), cvPoint((int)outPoint3.x, (int)outPoint3.y), color, thickness);		
	cvLine(image, cvPoint((int)outPoint3.x, (int)outPoint3.y), cvPoint((int)outPoint4.x, (int)outPoint4.y), color, thickness);
	cvLine(image, cvPoint((int)outPoint4.x, (int)outPoint4.y), cvPoint((int)outPoint1.x, (int)outPoint1.y), color, thickness);
}

void tst_QNetworkConfiguration::invalidPoint()
{
    QNetworkConfiguration pt;

    QVERIFY(pt.name().isEmpty());
    QVERIFY(!pt.isValid());
    QVERIFY(pt.type() == QNetworkConfiguration::Invalid);
    QVERIFY(!(pt.state() & QNetworkConfiguration::Defined));
    QVERIFY(!(pt.state() & QNetworkConfiguration::Discovered));
    QVERIFY(!(pt.state() & QNetworkConfiguration::Active));
    QVERIFY(!pt.isRoamingAvailable());

    QNetworkConfiguration pt2(pt);
    QVERIFY(pt2.name().isEmpty());
    QVERIFY(!pt2.isValid());
    QVERIFY(pt2.type() == QNetworkConfiguration::Invalid);
    QVERIFY(!(pt2.state() & QNetworkConfiguration::Defined));
    QVERIFY(!(pt2.state() & QNetworkConfiguration::Discovered));
    QVERIFY(!(pt2.state() & QNetworkConfiguration::Active));
    QVERIFY(!pt2.isRoamingAvailable());

}

TEST(NumLib, SpatialFunctionInterpolationSurface)
{
	// create geometry
	GeoLib::Point pt1(0.0, 0.0, 0.0);
	GeoLib::Point pt2(10.0, 0.0, 0.0);
	GeoLib::Point pt3(10.0, 10.0, 0.0);
	GeoLib::Point pt4(0.0, 10.0, 0.0);
	std::vector<GeoLib::Point*> pnts = {&pt1, &pt2, &pt3, &pt4};
	GeoLib::Polyline ply0(pnts);
	ply0.addPoint(0);
	ply0.addPoint(1);
	ply0.addPoint(2);
	ply0.addPoint(3);
	ply0.addPoint(0);
	std::unique_ptr<GeoLib::Surface>  sfc1(GeoLib::Surface::createSurface(ply0));

	// define a function
	const std::vector<std::size_t> vec_point_ids = {{0, 1, 2, 3}};
	const std::vector<double> vec_point_values = {{0., 100., 100., 0.}};
	NumLib::LinearInterpolationOnSurface interpolate(*sfc1, vec_point_ids, vec_point_values, std::numeric_limits<double>::max());

	// normal
	for (unsigned k=0; k<10; k++) {
		ASSERT_DOUBLE_EQ(k*10., interpolate(GeoLib::Point(k,0,0)));
		ASSERT_DOUBLE_EQ(k*10., interpolate(GeoLib::Point(k,5,0)));
		ASSERT_DOUBLE_EQ(k*10., interpolate(GeoLib::Point(k,10,0)));
	}

	// failure
	// x, y
	ASSERT_DOUBLE_EQ(std::numeric_limits<double>::max(), interpolate(GeoLib::Point(-1,-1,0)));
	ASSERT_DOUBLE_EQ(std::numeric_limits<double>::max(), interpolate(GeoLib::Point(11,-1,0)));
	ASSERT_DOUBLE_EQ(std::numeric_limits<double>::max(), interpolate(GeoLib::Point(11,11,0)));
	ASSERT_DOUBLE_EQ(std::numeric_limits<double>::max(), interpolate(GeoLib::Point(-1,11,0)));
	// z
	ASSERT_DOUBLE_EQ(std::numeric_limits<double>::max(), interpolate(GeoLib::Point(0,0,1)));
	ASSERT_DOUBLE_EQ(std::numeric_limits<double>::max(), interpolate(GeoLib::Point(0,0,-1)));
}

// Move the image: call from OnMouseMove. Pt is in window client coordinates if window
// is non-NULL, or in screen coordinates if NULL.
bool wxGenericDragImage::Move(const wxPoint& pt)
{
    wxASSERT_MSG( (m_windowDC != NULL), wxT("No window DC in wxGenericDragImage::Move()") );

    wxPoint pt2(pt);
    if (m_fullScreen)
        pt2 = m_window->ClientToScreen(pt);

    // Erase at old position, then show at the current position
    wxPoint oldPos = m_position;

    bool eraseOldImage = (m_isDirty && m_isShown);

    if (m_isShown)
        RedrawImage(oldPos - m_offset, pt2 - m_offset, eraseOldImage, true);

    m_position = pt2;

    if (m_isShown)
        m_isDirty = true;

    return true;
}

bool MgCmdDrawRect::touchEnded(const MgMotion* sender)
{
    Point2d pt1(m_startPt);
    Point2d pt2(snapPoint(sender));
    MgBaseRect* shape = (MgBaseRect*)dynshape()->shape();
    
    if (shape->getFlag(kMgSquare)) {
        float len = (float)mgMax(fabs(pt2.x - pt1.x), fabs(pt2.y - pt1.y));
        Box2d rect(m_startPt, 2.f * len, 0);
        pt1 = rect.leftTop();
        pt2 = rect.rightBottom();
    }
    shape->setRect(pt1, pt2);
    dynshape()->shape()->update();

    float minDist = mgDisplayMmToModel(5, sender);

    if (shape->getWidth() > minDist && shape->getHeight() > minDist) {
        addRectShape(sender);
    }

    return _touchEnded(sender);
}

void plotLinesToPainter(QPainter& painter,
			const Numpy1DObj& x1, const Numpy1DObj& y1,
			const Numpy1DObj& x2, const Numpy1DObj& y2,
			const QRectF* clip, bool autoexpand)
{
  const int maxsize = min(x1.dim, x2.dim, y1.dim, y2.dim);

  // if autoexpand, expand rectangle by line width
  QRectF clipcopy;
  if ( clip != 0 && autoexpand )
    {
      const qreal lw = painter.pen().widthF();
      qreal x1, y1, x2, y2;
      clip->getCoords(&x1, &y1, &x2, &y2);
      clipcopy.setCoords(x1, y1, x2, y2);
      clipcopy.adjust(-lw, -lw, lw, lw);
    }

  if( maxsize != 0 )
    {
      QVector<QLineF> lines;
      for(int i = 0; i < maxsize; ++i)
	{
	  QPointF pt1(x1(i), y1(i));
	  QPointF pt2(x2(i), y2(i));
	  if( clip != 0 )
	    {
	      if( clipLine(clipcopy, pt1, pt2) )
		lines << QLineF(pt1, pt2);
	    }
	  else
	    lines << QLineF(pt1, pt2);
	}

      painter.drawLines(lines);
    }
}

static void
test_lt ()
{
    rw_info (0, __FILE__, __LINE__, "operator<");

    std::tuple<> nt1, nt2;
    TEST (!(nt1 < nt1));
    TEST (!(nt1 < nt2));

    std::tuple<int> it1 (1), it2 (2);
    TEST (!(it1 < it1));
    TEST (it1 < it2);

    UserDefined ud1 (1), ud2 (2);
    std::tuple<UserDefined> ut1 (ud1), ut2 (ud2);
    TEST (!(ut1 < ut1));
    TEST (ut1 < ut2);

    std::tuple<long, const char*> pt1 (1234L, "string");
    TEST (!(pt1 < pt1));
    std::tuple<long, const char*> pt2 (1235L, "string");
    TEST (pt1 < pt2);
    std::tuple<long, const char*> pt3 (1234L, "strings");
    TEST (pt1 < pt3);

    std::tuple<bool, char, int, double, void*, UserDefined>
        bt1 (true, 'a', 255, 3.14159, &nt1, ud1),
        bt2 (true, 'a', 256, 3.14159, &nt1, ud1),
        bt3 (true, 'a', 255, 3.14159, &nt1, ud2);
    rw_assert (!(bt1 < bt1), __FILE__, __LINE__,
               "bt1 < bt1, got true, expected false");
    rw_assert (bt1 < bt2, __FILE__, __LINE__,
               "bt1 < bt2, got false, expected true");
    rw_assert (bt1 < bt3, __FILE__, __LINE__,
               "bt1 < bt3, got false, expected true");
}

TEST_F(CreatePolygonTreesTest, P0AndP1AndP2)
{
	GeoLib::SimplePolygonTree *pt0(new GeoLib::SimplePolygonTree(_p0, nullptr));
	GeoLib::SimplePolygonTree *pt1(new GeoLib::SimplePolygonTree(_p1, nullptr));
	GeoLib::SimplePolygonTree *pt2(new GeoLib::SimplePolygonTree(_p2, nullptr));

	std::list<GeoLib::SimplePolygonTree*> pt_list;
	pt_list.push_back(pt0);
	pt_list.push_back(pt1);
	pt_list.push_back(pt2);
	ASSERT_EQ(3u, pt_list.size());

	ASSERT_FALSE(_p0->isPolylineInPolygon(*_p1));
	ASSERT_FALSE(_p0->isPolylineInPolygon(*_p2));
	ASSERT_FALSE(_p1->isPolylineInPolygon(*_p0));
	ASSERT_FALSE(_p1->isPolylineInPolygon(*_p2));
	ASSERT_TRUE(_p2->isPolylineInPolygon(*_p0));
	ASSERT_TRUE(_p2->isPolylineInPolygon(*_p1));

	createPolygonTrees(pt_list);
	ASSERT_EQ(1u, pt_list.size());
	ASSERT_EQ(2u, (*(pt_list.begin()))->getNChilds());
	std::for_each(pt_list.begin(), pt_list.end(), std::default_delete<GeoLib::SimplePolygonTree>());
}

Cube::Cube(){
    geoType = CUBE_GEO;
    p = new Poly();
    Point pt1(0,0,0);
    Point pt2(0,0,10);
    Point pt3(10,0,10);
    Point pt4(10,0,0);
    Point pt5(10,10,0);
    Point pt6(10,10,10);
    Point pt7(0,10,10);
    Point pt8(0,10,0);

    p->addFace(pt1, pt2, pt7, pt8); // bottom
    p->addFace(pt3, pt4, pt5, pt6); // right
    p->addFace(pt1, pt2, pt3, pt4); // front 
    p->addFace(pt5, pt6, pt7, pt8); // top
    p->addFace(pt1, pt4, pt5, pt8); // left
    p->addFace(pt2, pt3, pt6, pt7); // back 

    p->computeNormals();
    this->addPoly(p); // this adds it to scene
    p->bound();
    this->bound();
}

void createBlock()
{
	AcDbBlockTableRecord* pBTR = new AcDbBlockTableRecord();
	pBTR->setName(DYNBLKSAMP_BLOCKNAME);
	AcDbSymbolTable* pBT = NULL;
	acdbHostApplicationServices()->workingDatabase()->getBlockTable(pBT, AcDb::kForWrite);
	pBT->add(pBTR);
	pBT->close();	
	
	
	AcGePoint3d pt1(0.0, 0.0, 0.0);
	AcGePoint3d pt2(2.0, 0.0, 0.0);
	AcDbLine* pLine = new AcDbLine(pt1, pt2);
	pBTR->appendAcDbEntity(pLine);
	pLine->close();

	pt1 = pt2;
	pt2.y = 2.0;
	pLine = new AcDbLine(pt1, pt2);
	pBTR->appendAcDbEntity(pLine);
	pLine->close();

	pt1 = pt2;
	pt2.x = 0.0;
	pLine = new AcDbLine(pt1, pt2);
	pBTR->appendAcDbEntity(pLine);
	pLine->close();

	pt1 = pt2;
	pt2.y = 0.0;
	pLine = new AcDbLine(pt1, pt2);
	pBTR->appendAcDbEntity(pLine);
	pLine->close();
	
	pBTR->close();
}

void CBCGPTransferFunction::Calculate(CArray<double, double>& output) const
{
	output.RemoveAll();

	int size = (int)m_Points.GetSize();
	if (size == 0)
	{
		return;
	}

	int count = (int)fabs((m_InputValueMax - m_InputValueMin) / m_InputValueStep) + 1;
	if (count == 1)
	{
		return;
	}

	output.SetSize(count);

	XPoint pt(m_Points[0]);
	if (m_InputValueMin < pt.m_Point)
	{
		for (int i = 0; i <= GetIndex(pt.m_Point); i++)
		{
			output[i] = pt.m_Value;
		}
	}

	if (size > 1)
	{
		pt = m_Points[size - 1];
	}

	if (pt.m_Point < m_InputValueMax)
	{
		for (int i = GetIndex(pt.m_Point); i < count; i++)
		{
			output[i] = pt.m_Value;
		}
	}

	// linear
	size = (int)m_Points.GetSize ();
	if (size < 2)
	{
		return;
	}

	for(long k = size - 1; k >= 1; k--)
	{
		CArray<double, double> points;

		XPoint pt1(m_Points[k - 1]);
		XPoint pt2(m_Points[k]);

		int index1 = GetIndex(pt1.m_Point);
		int index2 = GetIndex(pt2.m_Point);
		double dY = (pt2.m_Value - pt1.m_Value) / (double)(index2 - index1);
		double value = pt1.m_Value;
		for(int i = index1; i <= index2; i++)
		{
			points.Add(bcg_clamp(value, m_OutputValueMin, m_OutputValueMax));
			value += dY;
		}

		if(points.GetSize() <= 2)
		{
			continue;
		}

		int kInsert = index1;
		for(int kk = 0; kk <= points.GetSize() - 1; kk++)
		{
			output[kInsert++] = points[kk];
		}
	}
}

void Engine::update_world(double start_time, double delta_time)
{
	frame_stop = start_time + delta_time;

	double start = stopwatch();
	
	bucVec keys;
	bucVec new_keys;
	bucVec obsolete_keys;
	

	//Update the hashboxes for all dynamic objects
	for(dyn_iterator dyn_it = wr->begin_dyn();dyn_it != wr->end_dyn(); ++dyn_it){
	
		reaper::object::phys::ObjectAccessor &phys_acc = dyn_it->get_physics();
		
		const double len = length(phys_acc.vel)*delta_time;

		const double ext1 = phys_acc.radius + len + 
			 phys_acc.max_acc * delta_time* delta_time / 2;
		
		const double ext2 = ext1 - 2* len;

		const Point &pos = dyn_it->get_pos(); 
		
		Point pt1( pos + norm(phys_acc.vel)*ext1 );
		Point pt2( pos - norm(phys_acc.vel)*ext2 );

		const Point p1(min(pt1.x,pt2.x),min(pt1.y,pt2.y), min(pt1.z,pt2.z) );
		const Point p2(max(pt1.x,pt2.x), max(pt1.y,pt2.y), max(pt1.z,pt2.z) );

		the_grid.calc_key(p1,p2,keys);		
		
		bucVec& current_k = old_keys[dyn_it->get_id()];
				
		for(int i = 0;i < keys.size(); ++i){
			bucVec::const_iterator p = 
				find(current_k.begin(), current_k.end(), keys[i] );
			
			if(p == current_k.end() )
				new_keys.push_back(keys[i]);
		}
		
		for(int i = 0;i < current_k.size(); ++i){
			bucVec::const_iterator p2 = 
				find(keys.begin(), keys.end(), current_k[i] );
			
			if(p2 == keys.end() )
				obsolete_keys.push_back(keys[i]);
		}

		for(int i = 0;i < new_keys.size();++i){
			collision_table.insert(dyn_it->get_id(),new_keys[i]);
			const set<int>& ids = collision_table.get_ids(new_keys[i]);
			for(std::set<int>::const_iterator j = ids.begin();j != ids.end(); ++j){
				int res = close_pairs.increase(dyn_it->get_id(),*j);
				if(res == 1){
					Pair* pr;
					SillyPtr si = wr->lookup_si(*j);
					StaticPtr st = wr->lookup_st(*j);
					DynamicPtr dyn = wr->lookup_dyn(*j);
					ShotPtr sh = wr->lookup_shot(*j);
					if( si.valid() ){
						pr = new SillyDynPair(si,*dyn_it);
					}
					else if( st.valid() )
						pr = new StaticDynPair(st,*dyn_it);
					else if( dyn.valid() )
						pr = new DynDynPair(dyn,*dyn_it);
					else if( sh.valid() )
						pr = new ShotDynPair(sh,*dyn_it);
					pr->calc_lower_bound();
					prio_queue.insert(pr);
				}
			}
		}
		
		
		
		for(int i = 0;i < obsolete_keys.size();++i){
			collision_table.remove(dyn_it->get_id(),obsolete_keys[i]);
			const set<int> ids = collision_table.get_ids(new_keys[i]);
			for(std::set<int>::const_iterator j = ids.begin();j != ids.end(); ++j){
				close_pairs.decrease(dyn_it->get_id(),*j);
			}
		}

		

		new_keys.clear();
		obsolete_keys.clear();

	}

	double mid = stopwatch();
	
	if(!prio_queue.empty()) {
		while( !prio_queue.empty() && prio_queue.top()->get_lower_bound() < frame_stop ) {
			
			//Now check if we want to simulate a collision between objects                                 
//.........这里部分代码省略.........