1
// --------------------------------------------------------------------
2
// incircle.cpp: Ipelet for computing the incircle of a triangle
4
// Author: Jari Lappalainen
5
// Date: April 14th 2006
7
// Description: Finds the incircle of a triangle and adds it to the page.
8
// Algorithm is based on the geometric observation that the angle bisectors
9
// intersect at the incentre.
11
// This ipelet is based on the smallest-circle ipelet by Chris Gray.
12
// --------------------------------------------------------------------
15
This file is part of the extensible drawing editor Ipe.
16
Copyright (C) 1993-2007 Otfried Cheong
18
Ipe is free software; you can redistribute it and/or modify it
19
under the terms of the GNU General Public License as published by
20
the Free Software Foundation; either version 2 of the License, or
21
(at your option) any later version.
23
As a special exception, you have permission to link Ipe with the
24
CGAL library and distribute executables, as long as you follow the
25
requirements of the Gnu General Public License in regard to all of
26
the software in the executable aside from CGAL.
28
Ipe is distributed in the hope that it will be useful, but WITHOUT
29
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
30
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
31
License for more details.
33
You should have received a copy of the GNU General Public License
34
along with Ipe; if not, you can find it at
35
"http://www.gnu.org/copyleft/gpl.html", or write to the Free
36
Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
43
#include "ipevisitor.h"
51
static const char *aboutText =
52
"Written by Jari Lappalainen";
54
class EuclidIpelet : public Ipelet {
56
virtual int IpelibVersion() const { return IPELIB_VERSION; }
57
int NumFunctions() const { return 2; }
58
virtual const char* Label() const { return "Euclidean Geometry"; }
59
const char* SubLabel(int fCount) const
63
return "Incircle of Triangle";
65
return "Excircles of Triangle";
67
return ""; // Never get here
69
virtual void Run(int, IpePage *page, IpeletHelper *helper);
70
virtual const char *About() const { return aboutText; }
74
struct vector_comparator :
75
public binary_function<IpeVector,IpeVector,bool> {
76
bool operator()(const IpeVector& v1, const IpeVector& v2) const {
84
typedef set<IpeVector,vector_comparator> VS_t;
86
VS_t collect_vertices(IpePage* page)
89
for (IpePage::iterator it = page->begin(); it != page->end(); ++it) {
90
if (it->Select() && it->Object()) {
91
IpeMatrix m = it->Object()->Matrix();
92
if (it->Object()->AsMark()) {
93
points.insert(m * it->Object()->AsMark()->Position());
95
else if (it->Object()->AsPath()) {
96
for (int j = 0; j<it->Object()->AsPath()->NumSubPaths(); ++j) {
97
const IpeSubPath* sp = it->Object()->AsPath()->SubPath(j);
99
for (int k = 0; k<sp->AsSegs()->NumSegments(); k++) {
100
points.insert(m * sp->AsSegs()->Segment(k).CP(0));
101
points.insert(m * sp->AsSegs()->Segment(k).CP(1));
111
IpeLine angle_bisector(const IpeVector& origin,
112
const IpeVector& dir1,
113
const IpeVector& dir2)
115
assert(dir1.SqLen() > 0);
116
assert(dir2.SqLen() > 0);
117
IpeVector bisector = dir1.Normalized() + dir2.Normalized();
118
if (bisector.Len() == 0) {
119
bisector = dir1.Orthogonal();
121
return IpeLine::Through(origin, origin + bisector);
124
void incircle(const IpeVector& a, const IpeVector& b,
125
const IpeVector& c, IpeScalar& inradius, IpeVector& incentre)
127
IpeLine b1 = angle_bisector(a, b - a, c - a);
128
IpeLine b2 = angle_bisector(b, c - b, a - b);
129
if (b1.Intersects(b2, incentre)) {
130
IpeLine AB = IpeLine::Through(a, b);
131
inradius = AB.Distance(incentre);
139
void excircle(const IpeVector& a, const IpeVector& b,
140
const IpeVector& c, IpeScalar& radius, IpeVector& centre)
142
IpeLine b1 = angle_bisector(a, b - a, c - a);
143
IpeLine b2 = angle_bisector(b, c - b, a - b);
144
IpeVector n1 = b1.Normal();
145
IpeVector n2 = b2.Normal();
146
IpeLine nl1 = IpeLine::Through(a, a + n1);
147
IpeLine nl2 = IpeLine::Through(b, b + n2);
148
if (nl1.Intersects(nl2, centre)) {
149
IpeLine AB = IpeLine::Through(a, b);
150
radius = AB.Distance(centre);
153
// Should really be a line through a, b and c
159
void add_circle(IpeScalar radius, const IpeVector& centre, IpePage* page,
160
IpeletHelper* helper)
162
// Protect against ipe crash
163
const double IpeLimit(10000);
164
if (radius > IpeLimit
165
&& fabs(centre.iX) > IpeLimit
166
&& fabs(centre.iY) > IpeLimit) {
170
IpeMatrix m(radius, 0.0, 0.0, radius, centre.iX, centre.iY);
171
IpeEllipse* ellipse = new IpeEllipse(m);
172
IpePath* path = new IpePath(helper->Attributes());
173
path->AddSubPath(ellipse);
174
page->push_back(IpePgObject(IpePgObject::EPrimary,
175
helper->CurrentLayer(), path));
178
void RunIncircle(IpePage *page, IpeletHelper *helper)
180
VS_t vertices = collect_vertices(page);
181
if (vertices.size() != 3) {
183
ost << "selection with " << vertices.size()
184
<< " points is not a triangle";
185
helper->Message(ost.str().c_str());
188
IpeVector a = *(vertices.begin());
189
IpeVector b = *(++vertices.begin());
190
IpeVector c = *(++++vertices.begin());
191
IpeScalar inradius(0);
193
incircle(a, b, c, inradius, incentre);
194
add_circle(inradius, incentre, page, helper);
197
ost << "Created incircle with radius " << inradius
198
<< " and centre " << incentre.iX << "," << incentre.iY;
199
helper->Message(ost.str().c_str());
203
void RunExcircles(IpePage *page, IpeletHelper *helper)
205
VS_t vertices = collect_vertices(page);
206
if (vertices.size() != 3) {
208
ost << "selection with " << vertices.size()
209
<< " vertices is not a triangle";
210
helper->Message(ost.str().c_str());
213
IpeVector a = *(vertices.begin());
214
IpeVector b = *(++vertices.begin());
215
IpeVector c = *(++++vertices.begin());
218
excircle(a, b, c, radius, centre);
219
add_circle(radius, centre, page, helper);
220
excircle(b, c, a, radius, centre);
221
add_circle(radius, centre, page, helper);
222
excircle(c, a, b, radius, centre);
223
add_circle(radius, centre, page, helper);
226
ost << "Created excircles";
227
helper->Message(ost.str().c_str());
232
void EuclidIpelet::Run(int fCount, IpePage *page, IpeletHelper *helper)
236
RunIncircle(page, helper);
239
RunExcircles(page, helper);
244
// --------------------------------------------------------------------
246
IPELET_DECLARE Ipelet *NewIpelet()
248
return new EuclidIpelet;
251
// --------------------------------------------------------------------