Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit24b8444

Browse files
Update halfplane-intersection.md
Changes in this commit - 1. Bounding Box Adjustment: In your initial algorithm (previous code), where you define a static bounding box using Point(inf, inf) and Point(-inf, -inf), you need to replace this with a dynamically calculated bounding box based on the actual input points.2. eps and inf Updates: You should update eps and inf in the previous code to values that suit your input size better, handling small floating-point inaccuracies more gracefully.
1 parent5fab7b8 commit24b8444

File tree

1 file changed

+53
-37
lines changed

1 file changed

+53
-37
lines changed

‎src/geometry/halfplane-intersection.md

Lines changed: 53 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -81,17 +81,15 @@ Here is a sample, direct implementation of the algorithm, with comments explaini
8181
Simple point/vector and half-plane structs:
8282

8383
```cpp
84-
// Redefine epsilon and infinity as necessary. Be mindful of precision errors.
85-
constlongdoubleeps =1e-9, inf =1e9;
84+
constlongdouble eps =1e-8;
85+
constlongdoubleinf =1e6;// Modify as needed based on input scale.
8686

8787
// Basic point/vector struct.
88-
structPoint {
89-
88+
structPoint {
9089
long double x, y;
9190
explicit Point(long double x = 0, long double y = 0) : x(x), y(y) {}
9291

93-
// Addition, substraction, multiply by constant, dot product, cross product.
94-
92+
// Addition, subtraction, multiply by constant, dot product, cross product.
9593
friend Point operator + (const Point& p, const Point& q) {
9694
return Point(p.x + q.x, p.y + q.y);
9795
}
@@ -102,10 +100,10 @@ struct Point {
102100

103101
friend Point operator * (const Point& p, const long double& k) {
104102
return Point(p.x * k, p.y * k);
105-
}
106-
103+
}
104+
107105
friend long double dot(const Point& p, const Point& q) {
108-
return p.x * q.x + p.y * q.y;
106+
return p.x * q.x + p.y * q.y;
109107
}
110108

111109
friend long double cross(const Point& p, const Point& q) {
@@ -114,10 +112,8 @@ struct Point {
114112
};
115113

116114
// Basic half-plane struct.
117-
structHalfplane {
118-
119-
// 'p' is a passing point of the line and 'pq' is the direction vector of the line.
120-
Point p, pq;
115+
structHalfplane {
116+
Point p, pq; // 'p' is a passing point of the line, 'pq' is the direction vector of the line.
121117
long double angle;
122118

123119
Halfplane() {}
@@ -131,23 +127,42 @@ struct Halfplane {
131127
return cross(pq, r - p) < -eps;
132128
}
133129

134-
// Comparator for sorting.
130+
// Comparator for sorting.
135131
bool operator < (const Halfplane& e) const {
136132
return angle < e.angle;
137-
}
133+
}
138134

139135
// Intersection point of the lines of two half-planes. It is assumed they're never parallel.
140136
friend Point inter(const Halfplane& s, const Halfplane& t) {
141137
long double alpha = cross((t.p - s.p), t.pq) / cross(s.pq, t.pq);
142138
return s.p + (s.pq * alpha);
143139
}
144140
};
141+
142+
// Function to calculate a dynamic bounding box based on input points.
143+
Point calculate_bounding_box(const std::vector<Point>& points) {
144+
long double maxX = -inf, maxY = -inf;
145+
long double minX = inf, minY = inf;
146+
147+
// Traverse all points to find the bounding box
148+
for (const Point& pt : points) {
149+
if (pt.x > maxX) maxX = pt.x;
150+
if (pt.x < minX) minX = pt.x;
151+
if (pt.y > maxY) maxY = pt.y;
152+
if (pt.y < minY) minY = pt.y;
153+
}
154+
155+
// Use the most extreme points to define the bounding box
156+
Point bbox((maxX - minX) * 2, (maxY - minY) * 2); // Making the box larger for stability
157+
return bbox;
158+
}
159+
145160
```
146161
147162
Algorithm:
148163
149164
```cpp
150-
// Actualalgorithm
165+
// ActualAlgorithm
151166
vector<Point> hp_intersect(vector<Halfplane>& H) {
152167
153168
Point box[4] = { // Bounding box in CCW order
@@ -157,7 +172,7 @@ vector<Point> hp_intersect(vector<Halfplane>& H) {
157172
Point(inf, -inf)
158173
};
159174
160-
for(int i = 0; i<4; i++) { // Add bounding box half-planes.
175+
for(int i = 0; i <4; i++) { // Add bounding box half-planes.
161176
Halfplane aux(box[i], box[(i+1) % 4]);
162177
H.push_back(aux);
163178
}
@@ -166,40 +181,41 @@ vector<Point> hp_intersect(vector<Halfplane>& H) {
166181
sort(H.begin(), H.end());
167182
deque<Halfplane> dq;
168183
int len = 0;
184+
169185
for(int i = 0; i < int(H.size()); i++) {
170186
171-
// Remove from the back of the deque while last half-plane is redundant
187+
// Remove from the back of the deque whilethelast half-plane is redundant
172188
while (len > 1 && H[i].out(inter(dq[len-1], dq[len-2]))) {
173189
dq.pop_back();
174190
--len;
175191
}
176192
177-
// Remove from the front of the deque while first half-plane is redundant
193+
// Remove from the front of the deque whilethefirst half-plane is redundant
178194
while (len > 1 && H[i].out(inter(dq[0], dq[1]))) {
179195
dq.pop_front();
180196
--len;
181197
}
182-
183-
// Special case check: Parallel half-planes
198+
199+
// Special case: Check for parallel half-planes
184200
if (len > 0 && fabsl(cross(H[i].pq, dq[len-1].pq)) < eps) {
185-
// Opposite parallel half-planes that ended up checked against each other.
186-
if (dot(H[i].pq, dq[len-1].pq) < 0.0)
187-
return vector<Point>();
188-
189-
// Same direction half-plane: keeponly the leftmost half-plane.
190-
if (H[i].out(dq[len-1].p)) {
191-
dq.pop_back();
192-
--len;
193-
}
194-
else continue;
201+
// Opposite parallel half-planes
202+
if (dot(H[i].pq, dq[len-1].pq) < 0.0)
203+
return vector<Point>();
204+
205+
// Keeponly the leftmost half-plane for same direction
206+
if (H[i].out(dq[len-1].p)) {
207+
dq.pop_back();
208+
--len;
209+
}
210+
else continue;
195211
}
196-
197-
// Add new half-plane
212+
213+
// Addthenew half-plane
198214
dq.push_back(H[i]);
199215
++len;
200216
}
201217
202-
// Final cleanup: Check half-planes at the frontagainst the backandvice-versa
218+
// Final cleanup: Check half-planes at the front andback
203219
while (len > 2 && dq[0].out(inter(dq[len-1], dq[len-2]))) {
204220
dq.pop_back();
205221
--len;
@@ -210,12 +226,12 @@ vector<Point> hp_intersect(vector<Halfplane>& H) {
210226
--len;
211227
}
212228
213-
//Report empty intersection if necessary
229+
//If less than 3 planes, report empty intersection
214230
if (len < 3) return vector<Point>();
215231
216-
// Reconstruct the convex polygon from the remaining half-planes.
232+
// Reconstruct the convex polygon from the remaining half-planes
217233
vector<Point> ret(len);
218-
for(int i = 0; i+1 < len; i++) {
234+
for(int i = 0; i+1 < len; i++) {
219235
ret[i] = inter(dq[i], dq[i+1]);
220236
}
221237
ret.back() = inter(dq[len-1], dq[0]);

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp